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:
Computing Equilibria with Partial Commitment Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Correlated and Coarse Equilibria of Single-Item Auctions

verfasst von : Michal Feldman, Brendan Lucier, Noam Nisan

Erschienen in: Web and Internet Economics

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

We study correlated equilibria and coarse equilibria of simple first-price single-item auctions in the simplest auction model of full information. Nash equilibria are known to always yield full efficiency and a revenue that is at least the second-highest value. We prove that the same is true for all correlated equilibria, even those in which agents overbid – i.e., bid above their values.
Coarse equilibria, in contrast, may yield lower efficiency and revenue. We show that the revenue can be as low as \(26\%\) of the second-highest value in a coarse equilibrium, even if agents are assumed not to overbid, and this is tight. We also show that when players do not overbid, the worst-case bound on social welfare at coarse equilibrium improves from \(63\%\) of the highest value to \(81\%\), and this bound is tight as well.

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
Vorheriges Kapitel Competitive Equilibria for Non-quasilinear Bidders in Combinatorial Auctions
Nächstes Kapitel Pricing to Maximize Revenue and Welfare Simultaneously in Large Markets
Fußnoten
1
Sometimes called “coarse correlated equilibria” [19] or “Hannan consistent” [10].
 
2
For example, while pure Nash equilibria of simultaneous first-price auctions are known to be fully efficient, mixed Nash equilibria may not [12].
 
3
This requires that the player with the highest value – Bob in our example – wins the tie; otherwise no pure equilibrium exists but arbitrarily close \(\epsilon \)-equilibria do.
 
4
Note, however, that in asymmetric Bayesian settings, even in (Bayesian) Nash equilibria, the winner is not necessarily the bidder with the highest valuation [13].
 
5
Ignoring \(O(\epsilon )\) terms, at equilibrium we have: For Alice: \(u_A = 0.02*1+0.02*0.9 = 0.038\) while deviating to 0 would yield utility 0.02, deviating to 0.1 yield utility 0.036, deviating to 0.5 yield utility 0.035, deviating to 0.8 yield utility 0.036, deviating to 0.9 yield utility 0.37 and deviating to 1 yield utility 0. For Bob we have \(u_B = 0.03*1.5 + 0.11 * 1.2 + 0.19 * 1.1 + 0.63 * 1 = 1.016\), but deviating to 1 would give utility 1, and deviating to anything below 1 would loose with probability of at least \(63\%\) leading to utility that is certainly less than 1.
 
6
In contrast, for multi-item simultaneous auctions, the \(1-1/e\) bound is tight for XOS valuations even without overbidding [3].
 
7
To get an auction with these parameters we need to specify when each of the players wins in a way that will achieve these values of \(\alpha \) and \(\beta \). The following parameters yield these utilities: Alice and Bob bid the same value of x distributed according to the same F that provided the lower bound: \(\alpha \) that is the solution of the equation \(2x-\log x-2=0\), \(v=1-\alpha \) and \(\beta =v\alpha \). Alice wins whenever \(x=0\) and Bob wins otherwise. Thus the probability that Alice wins is \(\alpha =F(0)\) and she pays nothing, indeed obtaining utility of \(\alpha \). Bob wins probability \(p=1-\alpha \) and pays the entire revenue obtaining net utility of \(pv-Revenue = (1-\alpha )(1-\alpha ) - (1-\alpha +\alpha \log \alpha )\) which for our \(\alpha \) is indeed \((1-\alpha )\alpha =\beta \).
 
Literatur
1.
Bhawalkar, K., Roughgarden, T.: Welfare guarantees for combinatorial auctions with item bidding. In: Proceedings of the 22nd annual ACM-SIAM Symposium on Discrete Algorithms (2011)
2.
Cai, Y., Papadimitriou, C.H.: Simultaneous Bayesian auctions and computational complexity. In: ACM Conference on Economics and Computation, EC 2014, Stanford, CA, USA, 8–12 June 2014, pp. 895–910 (2014)
3.
Christodoulou, G., Kovács, A., Schapira, M.: Bayesian combinatorial auctions. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming (2008)
4.
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)
5.
Daskalakis, C., Syrgkanis, V.: Learning in auctions: regret is hard, envy is easy. CoRR abs/1511.01411 (2015)
6.
Devanur, N.R., Morgenstern, J., Syrgkanis, V., Weinberg, S.M.: Simple auctions with simple strategies. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC 2015, Portland, OR, USA, 15–19 June 2015, pp. 305–322 (2015)
7.
Dobzinski, S., Fu, H., Kleinberg, R.D.: On the complexity of computing an equilibrium in combinatorial auctions. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, 4–6 January 2015, pp. 110–122 (2015)
8.
Dütting, P., Kesselheim, T., Tardos, É.: Mechanism with unique learnable equilibria. In: Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC 2014, pp. 877–894 (2014)
9.
Feldman, M., Fu, H., Gravin, N., Lucier, B.: Simultaneous auctions are (almost) efficient. In: Proceedings of the 45th annual ACM Symposium on Theory of Computing (2013)
10.
11.
12.
Hassidim, A., Kaplan, H., Mansour, Y., Nisan, N.: Non-price equilibria in markets of discrete goods. In: Proceedings of the 12th ACM Conference on Electronic Commerce (2011)
13.
Kaplan, T., Zamir, S.: Asymmetric first-price auctions with uniform distributions: analytic solutions to the general case. Econ. Theor. 50(2), 269–302 (2012)MathSciNetCrossRefMATH
14.
15.
Moulin, H., Gupta, S.S., Ray, I.: Coarse correlated equilibria in an abatement game. Working paper (2013)
16.
17.
Syrgkanis, V.: Efficiency of mechanisms in complex markets. Ph.D. thesis, Cornell University, 8 (2014)
18.
Syrgkanis, V., Tardos, E.: Composable and efficient mechanisms. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (2013)
19.
Young, H.P.: Strategic Learning and Its Limits. Oxford University Press, Oxford (2004)CrossRef
Metadaten
Titel
Correlated and Coarse Equilibria of Single-Item Auctions
verfasst von
Michal Feldman
Brendan Lucier
Noam Nisan
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Web and Internet Economics

Print ISBN: 978-3-662-54109-8

Electronic ISBN: 978-3-662-54110-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-54110-4_10