Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2017 | OriginalPaper | Chapter

Liquid Price of Anarchy

Authors : Yossi Azar, Michal Feldman, Nick Gravin, Alan Roytman

Published in: Algorithmic Game Theory

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
next chapter Tight Welfare Guarantees for Pure Nash Equilibria of the Uniform Price Auction
Footnotes
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.
 
Literature
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.
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)
Metadata
Title
Liquid Price of Anarchy
Authors
Yossi Azar
Michal Feldman
Nick Gravin
Alan Roytman
Copyright Year
2017
Book
Algorithmic Game Theory

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

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

Copyright Year: 2017

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

Premium Partner

    Image Credits