Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2017 | OriginalPaper | Buchkapitel

Liquid Price of Anarchy

verfasst von : Yossi Azar, Michal Feldman, Nick Gravin, Alan Roytman

Erschienen in: Algorithmic Game Theory

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Incorporating budget constraints into the analysis of auctions has become increasingly important, as they model practical settings more accurately. The social welfare function, which is the standard measure of efficiency in auctions, is inadequate for settings with budgets, since there may be a large disconnect between the value a bidder derives from obtaining an item and what can be liquidated from her. The Liquid Welfare objective function has been suggested as a natural alternative for settings with budgets. Simple auctions, like simultaneous item auctions, are evaluated by their performance at equilibrium using the Price of Anarchy (PoA) measure – the ratio of the objective function value of the optimal outcome to the worst equilibrium. Accordingly, we evaluate the performance of simultaneous item auctions in budgeted settings by the Liquid Price of Anarchy (LPoA) measure – the ratio of the optimal Liquid Welfare to the Liquid Welfare obtained in the worst equilibrium.
For pure Nash equilibria of simultaneous first price auctions, we obtain a bound of 2 on the LPoA for additive buyers. Our results easily extend to the larger class of fractionally-subadditive valuations. Next we show that the LPoA of mixed Nash equilibria for first price auctions with additive bidders is bounded by a constant. Our proofs are robust, and can be extended to achieve similar bounds for Bayesian Nash equilibria. To derive our results, we develop a new technique in which some bidders deviate (surprisingly) toward a non-optimal solution. In particular, this technique goes beyond the smoothness-based approach.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Nächstes Kapitel Tight Welfare Guarantees for Pure Nash Equilibria of the Uniform Price Auction
Fußnoten
1
The difference is also pointed out in the literature on the design of truthful combinatorial auctions [20, 21].
 
2
In particular, there are tight PoA bounds of \(\frac{e}{e-1}\) for submodular bidders, and 2 for subadditive bidders.
 
3
Valuation \(v\) is fractionally-subadditive or equivalently XOS if there is a set of additive valuations \(A = \{a_1,\ldots ,a_\ell \}\) such that \(v_{i}(S) = \max _{a\in A} a(S)\) for every \(S \subseteq [m]\). XOS is a super class of submodular and additive valuations.
 
Literatur
1.
Anari, N., Goel, G., Nikzad, A.: Mechanism design for crowdsourcing: an optimal 1–1/e competitive budget-feasible mechanism for large markets. In: FOCS, pp. 266–275 (2014)
2.
Ausubel, L.M.: An efficient ascending-bid auction for multiple objects. Am. Econ. Rev. 94(5), 1452–1475 (2004)CrossRef
3.
Azar, Y., Feldman, M., Gravin, N., Roytman, A.: Liquid price of anarchy. CoRR abs/1511.01132 (2015)
4.
Bei, X., Chen, N., Gravin, N., Lu, P.: Budget feasible mechanism design: From prior-free to bayesian. In: STOC, pp. 449–458 (2012)
5.
Benoit, J.P., Krishna, V.: Multiple-object auctions with budget constrained bidders. Rev. Econ. Stud. 68(1), 155–179 (2001)MathSciNetCrossRef
6.
Bhattacharya, S., Conitzer, V., Munagala, K., Xia, L.: Incentive compatible budget elicitation in multi-unit auctions. In: SODA, pp. 554–572 (2010)
7.
Bhawalkar, K., Roughgarden, T.: Welfare guarantees for combinatorial auctions with item bidding. In: SODA, pp. 700–709 (2011)
8.
9.
Borgs, C., Chayes, J., Immorlica, N., Mahdian, M., Saberi, A.: Multi-unit auctions with budget-constrained bidders. In: EC, pp. 44–51 (2005)
10.
Cai, Y., Papadimitriou, C.: Simultaneous Bayesian auctions and computational complexity. In: EC, pp. 895–910 (2014)
11.
12.
13.
Chawla, S., Malec, D., Malekian, A.: Bayesian mechanism design for budget-constrained agents. In: EC, pp. 253–262 (2011)
14.
Che, Y.K., Gale, I.: Standard auctions with financially constrained bidders. Rev. Econ. Stud. 65(1), 1–21 (1998)MathSciNetCrossRef
15.
Chen, N., Gravin, N., Lu, P.: On the approximability of budget feasible mechanisms. In: SODA, pp. 685–699 (2011)
16.
Christodoulou, G., Kovács, A., Schapira, M.: Bayesian combinatorial auctions. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 820–832. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-70575-8_​67CrossRef
17.
Christodoulou, G., Kovács, A., Sgouritsa, A., Tang, B.: Tight bounds for the price of anarchy of simultaneous first price auctions. CoRR abs/1312.2371 (2013)
18.
Christodoulou, G., Sgouritsa, A., Tang, B.: On the efficiency of the proportional allocation mechanism for divisible resources. In: Hoefer, M. (ed.) SAGT 2015. LNCS, vol. 9347, pp. 165–177. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48433-3_​13CrossRef
19.
Dobzinski, S., Fu, H., Kleinberg, R.: On the complexity of computing an equilibrium in combinatorial auctions. In: SODA, pp. 110–122 (2015)
20.
Dobzinski, S., Lavi, R., Nisan, N.: Multi-unit auctions with budget limits. In: FOCS, pp. 260–269 (2008)
21.
Dobzinski, S., Leme, R.P.: Efficiency guarantees in auctions with budgets. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 392–404. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-43948-7_​33CrossRef
22.
Dobzinski, S., Papadimitriou, C., Singer, Y.: Mechanisms for complement-free procurement. In: EC, pp. 273–282 (2011)
23.
Dughmi, S., Eden, A., Feldman, M., Fiat, A., Leonardi, S.: Lottery pricing equilibria. In: EC, pp. 401–418 (2016)
24.
Dütting, P., Henzinger, M., Starnberger, M.: Valuation compressions in VCG-based combinatorial auctions. In: Chen, Y., Immorlica, N. (eds.) WINE 2013. LNCS, vol. 8289, pp. 146–159. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-45046-4_​13CrossRef
25.
Feldman, M., Fu, H., Gravin, N., Lucier, B.: Simultaneous auctions are (almost) efficient. In: STOC, pp. 201–210 (2013)
26.
Feldman, M., Gravin, N., Lucier, B.: Combinatorial walrasian equilibrium. In: STOC, pp. 61–70 (2013)
27.
Hartline, J., Hoy, D., Taggart, S.: Price of anarchy for auction revenue. In: EC, pp. 693–710 (2014)
28.
Hassidim, A., Kaplan, H., Mansour, Y., Nisan, N.: Non-price equilibria in markets of discrete goods. In: EC, pp. 295–296 (2011)
29.
30.
Laffont, J.J., Robert, J.: Optimal auction with financially constrained buyers. Econ. Lett. 52(2), 181–186 (1996)CrossRef
31.
Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55(2), 270–296 (2006)MathSciNetCrossRef
32.
Lu, P., Xiao, T.: Improved efficiency guarantees in auctions with budgets. In: EC, pp. 397–413 (2015)
33.
Malakhov, A., Vohra, R.V.: Optimal auctions for asymmetrically budget constrained bidders. Rev. Econ. Des. 12(4), 245–257 (2008)MathSciNetMATH
34.
Pai, M., Vohra, R.V.: Optimal auctions with financially constrained bidders. Discussion papers, Northwestern University, Center for Mathematical Studies in Economics and Management Science, August 2008
35.
Roughgarden, T.: Intrinsic robustness of the price of anarchy. In: STOC, pp. 513–522 (2009)
36.
Roughgarden, T., Tardos, E.: Introduction to the inefficiency of equilibria. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V. (eds.) Algorithmic Game Theory. Cambridge University Press, New York (2007)MATH
37.
Singer, Y.: Budget feasible mechanisms. In: FOCS, pp. 765–774 (2010)
38.
Syrgkanis, V., Tardos, E.: Composable and efficient mechanisms. In: STOC, pp. 211–220 (2013)
Metadaten
Titel
Liquid Price of Anarchy
verfasst von
Yossi Azar
Michal Feldman
Nick Gravin
Alan Roytman
Copyright-Jahr
2017
Buch
Algorithmic Game Theory

Print ISBN: 978-3-319-66699-0

Electronic ISBN: 978-3-319-66700-3

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-66700-3_1

Premium Partner

    Bildnachweise