Finance:Budget-additive valuation

From HandWiki

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 
  2. ↑ Mehta, Aranyak (2013-10-16). "Online Matching and Ad Allocation" (in en). Foundations and Trends in Theoretical Computer Science 8 (4): 265–368. doi:10.1561/0400000057. ISSN 1551-305X. https://www.nowpublishers.com/article/Details/TCS-057. 
  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. https://doi.org/10.1145/1284320.1284321. 
  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) 4698: pp. 253–264, doi:10.1007/978-3-540-75520-3_24, ISBN 978-3-540-75519-7, http://dx.doi.org/10.1007/978-3-540-75520-3_24, retrieved 2020-09-03 
  5. ↑ Andelman, Nir; Mansour, Yishay (2004). "Auctions with Budget Constraints". in Hagerup, Torben; Katajainen, Jyrki (in en). Algorithm Theory - SWAT 2004. Lecture Notes in Computer Science. 3111. Berlin, Heidelberg: Springer. pp. 26–38. doi:10.1007/978-3-540-27810-8_4. ISBN 978-3-540-27810-8. https://link.springer.com/chapter/10.1007/978-3-540-27810-8_4. 
  6. ↑ Buchfuhrer, Dave; Dughmi, Shaddin; Fu, Hu; Kleinberg, Robert; Mossel, Elchanan; Papadimitriou, Christos; Schapira, Michael; Singer, Yaron et al. (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 et al. (in en). Automata, Languages and Programming. Lecture Notes in Computer Science. 5125. Berlin, Heidelberg: Springer. pp. 186–197. doi:10.1007/978-3-540-70575-8_16. ISBN 978-3-540-70575-8. https://link.springer.com/chapter/10.1007/978-3-540-70575-8_16. 
  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. http://dx.doi.org/10.1109/focs.2008.47. 
  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. et al. (in en). Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. 5171. Berlin, Heidelberg: Springer. pp. 247–253. doi:10.1007/978-3-540-85363-3_20. ISBN 978-3-540-85363-3. https://link.springer.com/chapter/10.1007/978-3-540-85363-3_20. 
  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. http://dx.doi.org/10.1145/3284177. 
  12. ↑ Feldman, Michal; Gravin, Nick; Lucier, Brendan (2016-01-01). "Combinatorial Walrasian Equilibrium". SIAM Journal on Computing 45 (1): 29–48. doi:10.1137/13094339X. ISSN 0097-5397. https://epubs.siam.org/doi/abs/10.1137/13094339X. 
  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. https://doi.org/10.1145/2764468.2764515. 
  14. ↑ Garg, Jugal; Hoefer, Martin; Bei, Xiaohui; Mehlhorn, Kurt (2016) (in en). Computing equilibria in markets with budget-additive utilities. Leibniz International Proceedings in Informatics (LIPIcs). 57. pp. 8:1–8:14. doi:10.4230/LIPIcs.ESA.2016.8. ISBN 9783959770156. https://dr.ntu.edu.sg//handle/10356/89959. 
  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. doi:10.1145/3033274.3085109. ISBN 978-1-4503-4527-9. http://dx.doi.org/10.1145/3033274.3085109. 

See also



Retrieved from "https://handwiki.org/wiki/index.php?title=Finance:Budget-additive_valuation&oldid=3420340"