nach oben

Theory of Computing Systems

Erschienen in:

01.10.2018

Tight Welfare Guarantees for Pure Nash Equilibria of the Uniform Price Auction

verfasst von: Georgios Birmpas, Evangelos Markakis, Orestis Telelis, Artem Tsikiridis

Erschienen in: Theory of Computing Systems | Ausgabe 7/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We revisit the inefficiency of the uniform price auction, one of the standard multi-unit auction formats, for allocating multiple units of a single good. In the uniform price auction, each bidder submits a sequence of non-increasing marginal bids, for each additional unit, i.e., a submodular curve. The per unit price is then set to be the highest losing bid. We focus on the pure Nash equilibria of such auctions, for bidders with submodular valuation functions. Our result is a tight upper and lower bound on the inefficiency of equilibria, showing that the Price of Anarchy is bounded by 2.1885. This resolves one of the open questions posed in previous works on multi-unit auctions. We also discuss implications of our bounds for an alternative, more practical form of the auction, employing a “uniform bidding” interface.

Vorheriger Artikel Guest Editorial: Special Issue on Algorithmic Game Theory

Nächster Artikel Online Random Sampling for Budgeted Settings

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

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

By Proposition 1, for every \(\ell \leqslant x_{i}(\mathbf {b}^{\prime })\): \(\ell \cdot (v_{i}(x_{i}(\mathbf {b}^{\prime }))/x_{i}(\mathbf {b}^{\prime }))\leqslant v_{i}(\ell )\).

The fact that this assumption can be made without loss of generality is instrumental in the proof of Lemma 3, which lies at the heart of our proof for the upper bound. Although we implicitly made this same assumption in our preliminary conference proceedings version of this work [3], a formal statement of this was omitted.

The following holds: \(\lambda ^{*}\cdot v_{i}(x_{i}(\mathbf {b})) + (1 - \lambda ^{*})\cdot \left ({\sum }_{j=x_{i}+ 1}^{x_{i}^{*}}m_{ij} \right )\cdot \left (1 + {\mathcal {W}}_{0}(-e^{-2}) \right ) = \frac {1 + {\mathcal {W}}_{0}(-e^{-2})}{2 + {\mathcal {W}}_{0}(-e^{-2})} \cdot v_{i}(x_{i}^{*}) \) .

Ausubel, L., Cramton, P.: Demand Reduction and Inefficiency in Multi-Unit Auctions. Technical report, University of Maryland (2002)

Bhawalkar, K., Roughgarden, T.: Welfare guarantees for combinatorial auctions with item bidding. In: Randall, D. (ed.) Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 700–709. SIAM (2011)

Birmpas, G., Markakis, E., Telelis, O., Tsikiridis, A.: Tight welfare guarantees for pure nash equilibria of the uniform price auction. In: Bilò, V., Flammini, M. (eds.) Algorithmic Game Theory - 10th International Symposium, SAGT 2017, volume 10504 of LNCS, pp. 16–28. Springer, Berlin (2017)

Christodoulou, G., Kovács, A., Schapira, M.: Bayesian Combinatorial Auctions. J. ACM 63(2), 11:1–11:19 (2016). Preliminary version appeared in ICALP(1) 2008:820–832MathSciNetCrossRefMATH

Christodoulou, G., Kovács, A., Sgouritsa, A., Tang, B.: Tight bounds for the price of anarchy of simultaneous first-price auctions. ACM Trans. Econ. Comput. 4(2), 9:1–9:33 (2016)MathSciNetCrossRef

Corless, R.M., Gonnet, G.H., Hare, D.E.G., Jeffrey, D.J., Knuth, D.E.: On the Lambert W function. Adv. Comput. Math. 5, 329–359 (1996)MathSciNetCrossRefMATH

de Keijzer, B, Markakis, E., Schäfer, G., Telelis, O.: Inefficiency of standard multi-unit auctions. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013, volume 8125 of LNCS, pp. 385–396. Springer, Berlin. Extended version available as arXiv:1303.1646 (2013)

Feldman, M., Fu, H., Gravin, N., Lucier, B.: Simultaneous auctions are (almost) efficient. In: Boneh, D., Roughgarden, T., Feigenbaum, T. (eds.) Proceedings of the 45th ACM Symposium on the Theory of Computing (STOC), pp. 201–210. ACM. Extended version available as arXiv:1209.4703(2013)

Friedman, M.: A Program for Monetary Stability. Fordham University Press, New York (1960)

10.

Hassidim, A., Kaplan, H., Mansour, Y., Nisan, N.: Non-price equilibria in markets of discrete goods. In: Shoham, Y., Chen, Y., Roughgarden, T. (eds.) Proceedings of the 12th ACM Conference on Electronic Commerce (ACM EC) 2011, pp. 295–296. ACM (2011)

11.

Koutsoupias, E, Papadimitriou, C.H.: Worst-case equilibria. Comput. Sci. Rev. 3(2), 65–69 (2009)CrossRefMATH

12.

Krishna, V.: Auction Theory. Academic, New York (2002)

13.

Markakis, E., Telelis, O.: Uniform price auctions: equilibria and efficiency. Theory Comput. Syst. 57(3), 549–575 (2015). Preliminary version appeared in SAGT 2012:227–238MathSciNetCrossRefMATH

14.

Milgrom, P.: Putting Auction Theory to Work. Cambridge University Press, Cambridge (2004)CrossRef

15.

Ockenfels, A., Reiley, D.H., Sadrieh, A.: Economics and Information Systems, volume 1 of Handbooks in Information Systems, chapter 12. Online Auctions, pp. 571–628. Emerald Group Publishing Limited (2006)

16.

Roughgarden, T.: Intrinsic robustness of the price of anarchy. J. ACM 62(5), 32:1–32:42 (2015). Preliminary version appeared in ACM STOC 2009:513–522MathSciNetCrossRefMATH

17.

Roughgarden, T.: The price of anarchy in games of incomplete information. ACM Trans. Econ. Comput. 31(1), 6:1–6:20 (2015). Preliminary version appeared in ACM EC 2012:862-879MathSciNet

18.

Roughgarden, T., Syrgkanis, V., Tardos, É.: The price of anarchy in auctions. J. Artif. Intell. Res. 59, 59–101 (2017)MathSciNetCrossRefMATH

19.

Syrgkanis, V., Tardos, É.: Composable and efficient mechanisms. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) Proceedings of the 45th ACM Sumposium on the Theory of Computing (STOC 2013), pp. 211–220. Extended version available as arXiv:1213.1325 (2013)

20.

Vickrey, W.: Counterspeculation, Auctions, and Competitive Sealed Tenders. J. Financ. Econ. 16(1), 8–37 (1961)MathSciNet

Titel: Tight Welfare Guarantees for Pure Nash Equilibria of the Uniform Price Auction
verfasst von: Georgios Birmpas
Evangelos Markakis
Orestis Telelis
Artem Tsikiridis
Publikationsdatum: 01.10.2018
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 7/2019
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-018-9889-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 7/2019

Guest Editorial: Special Issue on Algorithmic Game Theory

Tradeoffs Between Information and Ordinal Approximation for Bipartite Matching

A Logic for Document Spanners

Opinion Formation Games with Aggregation and Negative Influence

The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games

How Many Variables are Needed to Express an Existential Positive Query?