Ocenění aditivní k rozpočtu - Budget-additive valuation - Wikipedia

v ekonomika, a ocenění aditivní k rozpočtu je druh a užitková funkce. Odpovídá osobě, která, když dostane sadu položek, je vyhodnotí následujícím způsobem:[1]

  • Pro každou položku j, existuje pevná hodnota protij.
  • K dispozici je také pevný rozpočet B.
  • Hodnota sady položek je minimum mezi B a součet hodnot položek v sadě.

Ocenění aditivní na rozpočet jsou užitečná při výzkumu internetová reklama,[2][3][4] kombinatorické aukce,[5][6] přidělení zdrojů,[7][8][9][10][11] a tržní rovnováha.[12][13][14][15]

Vztah k jiným druhům ocenění

Každý aditivní ocenění je zvláštní případ ocenění aditivní k rozpočtu, ve kterém je rozpočet nekonečný. Každé ocenění s přidanou hodnotou rozpočtu je a submodulární ocenění.

Reference

  1. ^ Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt (leden 2018), „Aproximace Nash Social Welfare with Budget-Additive Valuations“, Sborník z dvacátého devátého výročního sympozia ACM-SIAM o diskrétních algoritmech, Společnost pro průmyslovou a aplikovanou matematiku, s. 2326–2340, doi:10.1137/1.9781611975031.150, ISBN  978-1-61197-503-1, S2CID  1282865
  2. ^ Mehta, Aranyak (16. 10. 2013). „Přiřazování online a přidělování reklam“. Základy a trendy v teoretické informatice. 8 (4): 265–368. doi:10.1561/0400000057. ISSN  1551-305X.
  3. ^ Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh; Vazirani, Vijay (01.10.2007). „AdWords a všeobecné online shody“. Deník ACM. 54 (5): 22 – es. doi:10.1145/1284320.1284321. ISSN  0004-5411.
  4. ^ Buchbinder, Niv; Jain, Kamal; Naor, Joseph (Seffi), „Online primární a duální algoritmy pro maximalizaci výnosů z aukcí reklam“, Algoritmy - ESA 2007, Berlín, Heidelberg: Springer Berlin Heidelberg, s. 253–264, ISBN  978-3-540-75519-7, vyvoláno 2020-09-03
  5. ^ Andelman, Nir; Mansour, Yishay (2004). Hagerup, Torben; Katajainen, Jyrki (eds.). „Aukce s omezenými rozpočty“. Teorie algoritmů - SWAT 2004. Přednášky z informatiky. Berlin, Heidelberg: Springer: 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 (01.01.2010), „Nepřibližitelnost pro kombinatorické aukce založené na VCG“, Sborník z výročního symposia ACM-SIAM o diskrétních algoritmech za rok 2010„Proceedings, Society for Industrial and Applied Mathematics, s. 518–536, doi:10.1137/1.9781611973075.45, ISBN  978-0-89871-701-3, vyvoláno 2020-09-03
  7. ^ Azar, Yossi; Birnbaum, Benjamin; Karlin, Anna R .; Mathieu, Claire; Nguyen, C. Thach (2008). Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M .; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). „Vylepšené aproximační algoritmy pro rozpočtové alokace“. Automaty, jazyky a programování. Přednášky z informatiky. Berlin, Heidelberg: Springer: 186–197. doi:10.1007/978-3-540-70575-8_16. ISBN  978-3-540-70575-8.
  8. ^ Chakrabarty, Deeparnab; Goel, Gagan (01.10.2008). „O přibližnosti rozpočtových alokací a vylepšených dolních mezích pro submodulární maximalizaci blahobytu a mezeru“. 2008 49. výroční sympozium IEEE o základech informatiky. IEEE. doi:10.1109 / focs.2008.47. ISBN  978-0-7695-3436-7.
  9. ^ Kalaitzis, Christos (2015-12-21). „Vylepšená záruka přiblížení pro problém maximálního rozpočtového přidělení“. Sborník z dvacátého sedmého výročního sympozia ACM-SIAM o diskrétních algoritmech. Philadelphia, PA: Společnost pro průmyslovou a aplikovanou matematiku. doi:10.1137 / 1.9781611974331.ch74. ISBN  978-1-61197-433-1.
  10. ^ Srinivasan, Aravind (2008). Goel, Ashish; Jansen, Klaus; Rolim, José D. P .; Rubinfeld, Ronitt (eds.). „Rozpočtové alokace v nastavení úplných informací“. Aproximace, randomizace a kombinatorická optimalizace. Algoritmy a techniky. Přednášky z informatiky. Berlin, Heidelberg: Springer: 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. (01.01.2019). „Téměř optimální online algoritmy a algoritmy rychlé aproximace pro problémy s alokací zdrojů“. Deník ACM. 66 (1): 1–41. doi:10.1145/3284177. ISSN  0004-5411.
  12. ^ Feldman, Michal; Gravin, Nick; Lucier, Brendan (01.01.2016). „Combinatorial Walrasian Equilibrium“. SIAM Journal on Computing. 45 (1): 29–48. doi:10.1137 / 13094339X. ISSN  0097-5397.
  13. ^ Roughgarden, Tim; Talgam-Cohen, Inbal (2015-06-15). „Proč ceny potřebují algoritmy“. Sborník příspěvků ze šestnácté konference ACM o ekonomii a výpočtu. ES '15. Portland, Oregon, USA: Sdružení pro výpočetní techniku: 19–36. doi:10.1145/2764468.2764515. ISBN  978-1-4503-3410-5.
  14. ^ Garg, Jugal; Hoefer, Martin; Bei, Xiaohui; Mehlhorn, Kurt (2016). „Výpočet rovnováhy na trzích s nástroji s přidanou hodnotou rozpočtu“. doi:10.4230 / LIPIcs.ESA.2016.8. Citovat deník vyžaduje | deník = (Pomoc)
  15. ^ Cole, Richard; Devanur, Nikhil; Gkatzelis, Vasilis; Jain, Kamal; Mai, Tung; Vazirani, Vijay V .; Yazdanbod, Sadra (2017-06-20). „Konvexní programová dualita, Fisherovy trhy a sociální péče Nash“. Sborník konferencí ACM o ekonomii a výpočtu z roku 2017. New York, NY, USA: ACM. doi:10.1145/3033274.3085109. ISBN  978-1-4503-4527-9.

Viz také