In economics, a budget-additive valuation is a kind of a utility function. It corresponds to a person that, when given a set of items, evaluates them in the following way:[1]
- For each item j, there is a fixed value vj.
- There is also a fixed budget B.
- The value of the set of items is the minimum between B and the sum of values of items in the set.
Budget-additive valuations are useful in the research of online advertising,[2][3][4] combinatorial auctions,[5][6] resource allocation,[7][8][9][10][11] and market equilibrium.[12][13][14][15]
Every additive valuation is a special case of a budget-additive valuation, in which the budget is infinite. Every budget-additive valuation is a submodular valuation.
Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt (January 2018), "Approximating the Nash Social Welfare with Budget-Additive Valuations", Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, pp. 2326–2340, doi:10.1137/1.9781611975031.150, hdl:11858/00-001M-0000-002D-E7D6-2, ISBN 978-1-61197-503-1, S2CID 1282865
Buchbinder, Niv; Jain, Kamal; Naor, Joseph (Seffi) (2007), "Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue", Algorithms – ESA 2007, Lecture Notes in Computer Science, vol. 4698, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 253–264, doi:10.1007/978-3-540-75520-3_24, ISBN 978-3-540-75519-7, retrieved 2020-09-03
Buchfuhrer, Dave; Dughmi, Shaddin; Fu, Hu; Kleinberg, Robert; Mossel, Elchanan; Papadimitriou, Christos; Schapira, Michael; Singer, Yaron; Umans, Chris (2010-01-17), "Inapproximability for VCG-Based Combinatorial Auctions", Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 518–536, doi:10.1137/1.9781611973075.45, ISBN 978-0-89871-701-3
Azar, Yossi; Birnbaum, Benjamin; Karlin, Anna R.; Mathieu, Claire; Nguyen, C. Thach (2008). "Improved Approximation Algorithms for Budgeted Allocations". In Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 5125. Berlin, Heidelberg: Springer. pp. 186–197. doi:10.1007/978-3-540-70575-8_16. ISBN 978-3-540-70575-8.
Kalaitzis, Christos (2015-12-21). "An Improved Approximation Guarantee for the Maximum Budgeted Allocation Problem". Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics. pp. 1048–1066. doi:10.1137/1.9781611974331.ch74. ISBN 978-1-61197-433-1.
Cole, Richard; Devanur, Nikhil; Gkatzelis, Vasilis; Jain, Kamal; Mai, Tung; Vazirani, Vijay V.; Yazdanbod, Sadra (2017-06-20). "Convex Program Duality, Fisher Markets, and Nash Social Welfare". Proceedings of the 2017 ACM Conference on Economics and Computation. New York, NY, USA: ACM. pp. 459–460. arXiv:1609.06654. doi:10.1145/3033274.3085109. ISBN 978-1-4503-4527-9. S2CID 14525165.