Budget-additive valuation

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 v_j.
• 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]}

Relation to other kinds of valuations

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.

References

1. 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, arXiv: 1707.04428 , doi: 10.1137/1.9781611975031.150 , hdl: 11858/00-001M-0000-002D-E7D6-2 , ISBN   978-1-61197-503-1, S2CID   1282865
2. Mehta, Aranyak (2013-10-16). "Online Matching and Ad Allocation" . Foundations and Trends in Theoretical Computer Science. 8 (4): 265–368. doi:10.1561/0400000057. ISSN   1551-305X.
3. Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh; Vazirani, Vijay (2007-10-01). "AdWords and generalized online matching" . Journal of the ACM. 54 (5): 22–es. doi:10.1145/1284320.1284321. ISSN   0004-5411. S2CID   8481313.
4. 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
5. Andelman, Nir; Mansour, Yishay (2004). "Auctions with Budget Constraints". In Hagerup, Torben; Katajainen, Jyrki (eds.). Algorithm Theory - SWAT 2004. Lecture Notes in Computer Science. Vol. 3111. Berlin, Heidelberg: Springer. pp. 26–38. doi:10.1007/978-3-540-27810-8_4. ISBN   978-3-540-27810-8.
6. 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
7. 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.
8. Chakrabarty, Deeparnab; Goel, Gagan (2008-10-01). "On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP". 2008 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE. pp. 687–696. doi:10.1109/focs.2008.47. ISBN   978-0-7695-3436-7.
9. 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.
10. Srinivasan, Aravind (2008). "Budgeted Allocations in the Full-Information Setting". In Goel, Ashish; Jansen, Klaus; Rolim, José D. P.; Rubinfeld, Ronitt (eds.). Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. Vol. 5171. Berlin, Heidelberg: Springer. pp. 247–253. doi:10.1007/978-3-540-85363-3_20. ISBN   978-3-540-85363-3.
11. Devanur, Nikhil R.; Jain, Kamal; Sivan, Balasubramanian; Wilkens, Christopher A. (2019-01-12). "Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems". Journal of the ACM. 66 (1): 1–41. arXiv: 1903.03944 . doi:10.1145/3284177. ISSN   0004-5411. S2CID   59337566.
12. Feldman, Michal; Gravin, Nick; Lucier, Brendan (2016-01-01). "Combinatorial Walrasian Equilibrium". SIAM Journal on Computing. 45 (1): 29–48. arXiv: 1304.2244 . doi:10.1137/13094339X. ISSN   0097-5397.
13. Roughgarden, Tim; Talgam-Cohen, Inbal (2015-06-15). "Why Prices Need Algorithms". Proceedings of the Sixteenth ACM Conference on Economics and Computation. EC '15. Portland, Oregon, USA: Association for Computing Machinery. pp. 19–36. doi:10.1145/2764468.2764515. ISBN   978-1-4503-3410-5. S2CID   229372470.
14. Garg, Jugal; Hoefer, Martin; Bei, Xiaohui; Mehlhorn, Kurt (2016). Computing equilibria in markets with budget-additive utilities. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 57. pp. 8:1–8:14. doi: 10.4230/LIPIcs.ESA.2016.8 . ISBN   9783959770156. S2CID   564953.
15. 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.

See also

• Utility functions on indivisible goods