IDEAS home Printed from https://ideas.repec.org/a/eee/jetheo/v156y2015icp343-388.html
   My bibliography  Save this article

Bounding the inefficiency of outcomes in generalized second price auctions

Author

Listed:
  • Caragiannis, Ioannis
  • Kaklamanis, Christos
  • Kanellopoulos, Panagiotis
  • Kyropoulou, Maria
  • Lucier, Brendan
  • Paes Leme, Renato
  • Tardos, Éva

Abstract

The Generalized Second Price (GSP) auction is the primary auction used for monetizing the use of the Internet. It is well-known that truthtelling is not a dominant strategy in this auction and that inefficient equilibria can arise. Edelman et al. (2007) [11] and Varian (2007) [36] show that an efficient equilibrium always exists in the full information setting. Their results, however, do not extend to the case with uncertainty, where efficient equilibria might not exist.

Suggested Citation

  • Caragiannis, Ioannis & Kaklamanis, Christos & Kanellopoulos, Panagiotis & Kyropoulou, Maria & Lucier, Brendan & Paes Leme, Renato & Tardos, Éva, 2015. "Bounding the inefficiency of outcomes in generalized second price auctions," Journal of Economic Theory, Elsevier, vol. 156(C), pages 343-388.
    • Handle: RePEc:eee:jetheo:v:156:y:2015:i:c:p:343-388
    DOI: 10.1016/j.jet.2014.04.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0022053114000647
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jet.2014.04.010?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Benjamin Edelman & Michael Schwarz, 2010. "Optimal Auction Design and Equilibrium Selection in Sponsored Search Auctions," Harvard Business School Working Papers 10-054, Harvard Business School.
    2. Sergiu Hart & Andreu Mas-Colell, 2013. "A Simple Adaptive Procedure Leading To Correlated Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 2, pages 17-46, World Scientific Publishing Co. Pte. Ltd..
    3. Fudenberg, Drew & Levine, David K., 1999. "Conditional Universal Consistency," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 104-130, October.
    4. Philip J. Reny, 2011. "On the Existence of Monotone Pure‐Strategy Equilibria in Bayesian Games," Econometrica, Econometric Society, vol. 79(2), pages 499-553, March.
    5. Benjamin Edelman & Michael Schwarz, 2010. "Optimal Auction Design and Equilibrium Selection in Sponsored Search Auctions," American Economic Review, American Economic Association, vol. 100(2), pages 597-602, May.
    6. Gomes, Renato & Sweeney, Kane, 2014. "Bayes–Nash equilibria of the generalized second-price auction," Games and Economic Behavior, Elsevier, vol. 86(C), pages 421-437.
    7. D. Foster & R. Vohra, 2010. "Calibrated Learning and Correlated Equilibrium," Levine's Working Paper Archive 568, David K. Levine.
    8. Benjamin Edelman & Michael Ostrovsky & Michael Schwarz, 2007. "Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords," American Economic Review, American Economic Association, vol. 97(1), pages 242-259, March.
    9. Athey, Susan, 2001. "Single Crossing Properties and the Existence of Pure Strategy Equilibria in Games of Incomplete Information," Econometrica, Econometric Society, vol. 69(4), pages 861-889, July.
    10. Varian, Hal R., 2007. "Position auctions," International Journal of Industrial Organization, Elsevier, vol. 25(6), pages 1163-1178, December.
    11. Foster, Dean P. & Vohra, Rakesh V., 1997. "Calibrated Learning and Correlated Equilibrium," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 40-55, October.
    12. Cremer, Jacques & McLean, Richard P, 1988. "Full Extraction of the Surplus in Bayesian and Dominant Strategy Auctions," Econometrica, Econometric Society, vol. 56(6), pages 1247-1257, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dirk Bergemann & Marek Bojko & Paul Dutting & Renato Paes Leme & Haifeng Xu & Song Zuo, 2024. "Data-Driven Mechanism Design: Jointly Eliciting Preferences and Information," Papers 2412.16132, arXiv.org.
    2. Patrick Hummel, 2018. "Hybrid mechanisms for Vickrey–Clarke–Groves and generalized second-price bids," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(1), pages 331-350, March.
    3. Paul Dütting & Thomas Kesselheim & Éva Tardos, 2021. "Algorithms as Mechanisms: The Price of Anarchy of Relax and Round," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 317-335, February.
    4. Paul Dütting & Felix Fischer & David C. Parkes, 2019. "Expressiveness and Robustness of First-Price Position Auctions," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 196-211, February.
    5. Dütting, Paul & Fischer, Felix & Parkes, David C., 2019. "Expressiveness and robustness of first-price position auctions," LSE Research Online Documents on Economics 85877, London School of Economics and Political Science, LSE Library.
    6. Blume, Lawrence & Easley, David & Kleinberg, Jon & Kleinberg, Robert & Tardos, Éva, 2015. "Introduction to computer science and economic theory," Journal of Economic Theory, Elsevier, vol. 156(C), pages 1-13.
    7. Thomas W. L. Norman, 2021. "Evolutionary stability in the generalized second-price auction," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 71(1), pages 235-250, February.
    8. Amir Ban & Ron Lavi, 2021. "Option values in sequential auctions with time-varying valuations," International Journal of Game Theory, Springer;Game Theory Society, vol. 50(1), pages 75-104, March.
    9. Alison Watts, 2018. "Generalized Second Price Auctions over a Network," Games, MDPI, vol. 9(3), pages 1-11, September.
    10. Yoav Kolumbus & Joe Halpern & 'Eva Tardos, 2024. "Paying to Do Better: Games with Payments between Learning Agents," Papers 2405.20880, arXiv.org, revised Feb 2025.
    11. Thành Nguyen & Karthik Kannan, 2021. "Welfare Implications in Intermediary Networks," Information Systems Research, INFORMS, vol. 32(2), pages 378-393, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hummel, Patrick, 2016. "Position auctions with dynamic resizing," International Journal of Industrial Organization, Elsevier, vol. 45(C), pages 38-46.
    2. Che, Yeon-Koo & Choi, Syngjoo & Kim, Jinwoo, 2017. "An experimental study of sponsored-search auctions," Games and Economic Behavior, Elsevier, vol. 102(C), pages 20-43.
    3. Tom Johnston & Michael Savery & Alex Scott & Bassel Tarbush, 2023. "Game Connectivity and Adaptive Dynamics," Papers 2309.10609, arXiv.org, revised Oct 2024.
    4. Ehud Lehrer & Eilon Solan, 2007. "Learning to play partially-specified equilibrium," Levine's Working Paper Archive 122247000000001436, David K. Levine.
    5. Kalai, Ehud & Lehrer, Ehud & Smorodinsky, Rann, 1999. "Calibrated Forecasting and Merging," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 151-169, October.
    6. Karl Schlag & Andriy Zapechelnyuk, 2009. "Decision Making in Uncertain and Changing Environments," Discussion Papers 19, Kyiv School of Economics.
    7. Francesco Decarolis & Maris Goldmanis & Antonio Penta, 2020. "Marketing Agencies and Collusive Bidding in Online Ad Auctions," Management Science, INFORMS, vol. 66(10), pages 4433-4454, October.
    8. Eddie Dekel & Yossi Feinberg, 2006. "Non-Bayesian Testing of a Stochastic Prediction," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 73(4), pages 893-906.
    9. Avi Goldfarb, 2014. "What is Different About Online Advertising?," Review of Industrial Organization, Springer;The Industrial Organization Society, vol. 44(2), pages 115-129, March.
    10. Mannor, Shie & Shimkin, Nahum, 2008. "Regret minimization in repeated matrix games with variable stage duration," Games and Economic Behavior, Elsevier, vol. 63(1), pages 227-258, May.
    11. Estrella Alonso & Joaquín Sánchez-Soriano & Juan Tejada, 2020. "Mixed Mechanisms for Auctioning Ranked Items," Mathematics, MDPI, vol. 8(12), pages 1-26, December.
    12. repec:osf:socarx:ymzrd_v1 is not listed on IDEAS
    13. Burkhard C. Schipper, 2022. "Strategic Teaching and Learning in Games," American Economic Journal: Microeconomics, American Economic Association, vol. 14(3), pages 321-352, August.
    14. Friedman, Daniel & Rabanal, Jean Paul & Rud, Olga A. & Zhao, Shuchen, 2022. "On the empirical relevance of correlated equilibrium," Journal of Economic Theory, Elsevier, vol. 205(C).
    15. Arifovic, Jasmina & Boitnott, Joshua F. & Duffy, John, 2019. "Learning correlated equilibria: An evolutionary approach," Journal of Economic Behavior & Organization, Elsevier, vol. 157(C), pages 171-190.
    16. Feinberg, Yossi & Dekel, Eddie, 2004. "A True Expert Knows which Question Should Be Asked," Research Papers 1856, Stanford University, Graduate School of Business.
    17. Michael Ostrovsky & Michael Schwarz, 2023. "Reserve Prices in Internet Advertising Auctions: A Field Experiment," Journal of Political Economy, University of Chicago Press, vol. 131(12), pages 3352-3376.
    18. Rene Saran & Roberto Serrano, 2012. "Regret Matching with Finite Memory," Dynamic Games and Applications, Springer, vol. 2(1), pages 160-175, March.
    19. Michel Benaïm & Josef Hofbauer & Sylvain Sorin, 2006. "Stochastic Approximations and Differential Inclusions, Part II: Applications," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 673-695, November.
    20. Gomes, Renato & Sweeney, Kane, 2014. "Bayes–Nash equilibria of the generalized second-price auction," Games and Economic Behavior, Elsevier, vol. 86(C), pages 421-437.
    21. Ehud Lehrer & Eilon Solan, 2016. "A General Internal Regret-Free Strategy," Dynamic Games and Applications, Springer, vol. 6(1), pages 112-138, March.

    More about this item

    Keywords

    Auction design; Equilibrium analysis; Price of anarchy; Bayesian games; Generalized second price auction; Keyword auctions;
    All these keywords.

    JEL classification:

    • D44 - Microeconomics - - Market Structure, Pricing, and Design - - - Auctions

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:jetheo:v:156:y:2015:i:c:p:343-388. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622869 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.