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," American Economic Review, American Economic Association, vol. 100(2), pages 597-602, May.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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..
    7. Fudenberg, Drew & Levine, David K., 1999. "Conditional Universal Consistency," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 104-130, October.
    8. 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.
    9. Varian, Hal R., 2007. "Position auctions," International Journal of Industrial Organization, Elsevier, vol. 25(6), pages 1163-1178, December.
    10. 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.
    11. 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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Alison Watts, 2018. "Generalized Second Price Auctions over a Network," Games, MDPI, vol. 9(3), pages 1-11, September.
    9. Yoav Kolumbus & Joe Halpern & 'Eva Tardos, 2024. "Paying to Do Better: Games with Payments between Learning Agents," Papers 2405.20880, arXiv.org.
    10. 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. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Burguet, Roberto & Caminal, Ramon & Ellman, Matthew, 2015. "In Google we trust?," International Journal of Industrial Organization, Elsevier, vol. 39(C), pages 44-55.
    9. 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.
    10. Kaplan, Todd R. & Zamir, Shmuel, 2015. "Advances in Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    11. Yan, Haomin, 2021. "Position auctions with multi-unit demands," Games and Economic Behavior, Elsevier, vol. 127(C), pages 179-193.
    12. Emanuele Tarantino, 2012. "A Note on Vertical Search Engines’ Foreclosure," Chapters, in: Joseph E. Harrington Jr & Yannis Katsoulacos (ed.), Recent Advances in the Analysis of Competition Policy and Regulation, chapter 8, Edward Elgar Publishing.
    13. Yi Zhu & Kenneth C. Wilbur, 2011. "Hybrid Advertising Auctions," Marketing Science, INFORMS, vol. 30(2), pages 249-273, 03-04.
    14. Emmanuel LORENZON, 2016. "Collusion with a Greedy Center in Position Auctions," Cahiers du GREThA (2007-2019) 2016-08, Groupe de Recherche en Economie Théorique et Appliquée (GREThA).
    15. Renato Gomes, 2014. "Optimal auction design in two-sided markets," RAND Journal of Economics, RAND Corporation, vol. 45(2), pages 248-272, June.
    16. Wilfred Amaldoss & Preyas S. Desai & Woochoel Shin, 2015. "Keyword Search Advertising and First-Page Bid Estimates: A Strategic Analysis," Management Science, INFORMS, vol. 61(3), pages 507-519, March.
    17. M. Yenmez, 2014. "Pricing in position auctions and online advertising," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 55(1), pages 243-256, January.
    18. Tom Johnston & Michael Savery & Alex Scott & Bassel Tarbush, 2023. "Game Connectivity and Adaptive Dynamics," Papers 2309.10609, arXiv.org, revised Oct 2024.
    19. Ehud Lehrer & Eilon Solan, 2007. "Learning to play partially-specified equilibrium," Levine's Working Paper Archive 122247000000001436, David K. Levine.
    20. Mahsa Derakhshan & Negin Golrezaei & Renato Paes Leme, 2022. "Linear Program-Based Approximation for Personalized Reserve Prices," Management Science, INFORMS, vol. 68(3), pages 1849-1864, 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.