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 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]

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, doi:10.1137/1.9781611975031.150, 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, Berlin, Heidelberg: Springer Berlin Heidelberg, vol. 4698, 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. 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.