IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2303.16388.html
   My bibliography  Save this paper

Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules

Author

Listed:
  • Xi Chen
  • Binghui Peng

Abstract

We study the complexity of finding an approximate (pure) Bayesian Nash equilibrium in a first-price auction with common priors when the tie-breaking rule is part of the input. We show that the problem is PPAD-complete even when the tie-breaking rule is trilateral (i.e., it specifies item allocations when no more than three bidders are in tie, and adopts the uniform tie-breaking rule otherwise). This is the first hardness result for equilibrium computation in first-price auctions with common priors. On the positive side, we give a PTAS for the problem under the uniform tie-breaking rule.

Suggested Citation

  • Xi Chen & Binghui Peng, 2023. "Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules," Papers 2303.16388, arXiv.org.
    • Handle: RePEc:arx:papers:2303.16388
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2303.16388
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Emmanuel Guerre & Isabelle Perrigne & Quang Vuong, 2000. "Optimal Nonparametric Estimation of First-Price Auctions," Econometrica, Econometric Society, vol. 68(3), pages 525-574, May.
    2. Marshall Robert C. & Meurer Michael J. & Richard Jean-Francois & Stromquist Walter, 1994. "Numerical Analysis of Asymmetric First Price Auctions," Games and Economic Behavior, Elsevier, vol. 7(2), pages 193-220, September.
    3. Maskin, Eric & Riley, John, 2003. "Uniqueness of equilibrium in sealed high-bid auctions," Games and Economic Behavior, Elsevier, vol. 45(2), pages 395-409, November.
    4. Dirk Bergemann & Benjamin Brooks & Stephen Morris, 2017. "First‐Price Auctions With General Information Structures: Implications for Bidding and Revenue," Econometrica, Econometric Society, vol. 85, pages 107-143, January.
    5. Plum, M, 1992. "Characterization and Computation of Nash-Equilibria for Auctions with Incomplete Information," International Journal of Game Theory, Springer;Game Theory Society, vol. 20(4), pages 393-418.
    6. Todd Kaplan & Shmuel Zamir, 2012. "Asymmetric first-price auctions with uniform distributions: analytic solutions to the general case," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 50(2), pages 269-302, June.
    7. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    8. 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.
    9. Lebrun, Bernard, 1999. "First Price Auctions in the Asymmetric N Bidder Case," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 40(1), pages 125-142, February.
    10. Lebrun, Bernard, 2006. "Uniqueness of the equilibrium in first-price auctions," Games and Economic Behavior, Elsevier, vol. 55(1), pages 131-151, April.
    11. Elodie Guerre & I. Perrigne & Q.H. Vuong, 2000. "Optimal nonparametric estimation of first-price auctions [[Estimation nonparamétrique optimale des enchères au premier prix]]," Post-Print hal-02697497, HAL.
    12. Eric Maskin & John Riley, 2000. "Equilibrium in Sealed High Bid Auctions," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 67(3), pages 439-454.
    13. Lizzeri, Alessandro & Persico, Nicola, 2000. "Uniqueness and Existence of Equilibrium in Auctions with a Reserve Price," Games and Economic Behavior, Elsevier, vol. 30(1), pages 83-114, January.
    14. Lebrun, Bernard, 1996. "Existence of an Equilibrium in First Price Auctions," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 7(3), pages 421-443, April.
    15. Philip J. Reny & Shmuel Zamir, 2004. "On the Existence of Pure Strategy Monotone Equilibria in Asymmetric First-Price Auctions," Econometrica, Econometric Society, vol. 72(4), pages 1105-1125, July.
    16. Daskalakis, Constantinos & Papadimitriou, Christos H., 2015. "Approximate Nash equilibria in anonymous games," Journal of Economic Theory, Elsevier, vol. 156(C), pages 207-245.
    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. Papadimitriou, Christos & Peng, Binghui, 2023. "Public goods games in directed networks," Games and Economic Behavior, Elsevier, vol. 139(C), pages 161-179.

    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. Lorentziadis, Panos L., 2016. "Optimal bidding in auctions from a game theory perspective," European Journal of Operational Research, Elsevier, vol. 248(2), pages 347-371.
    2. Hickman Brent R. & Hubbard Timothy P. & Sağlam Yiğit, 2012. "Structural Econometric Methods in Auctions: A Guide to the Literature," Journal of Econometric Methods, De Gruyter, vol. 1(1), pages 67-106, August.
    3. Hickman Brent R. & Hubbard Timothy P. & Sağlam Yiğit, 2012. "Structural Econometric Methods in Auctions: A Guide to the Literature," Journal of Econometric Methods, De Gruyter, vol. 1(1), pages 67-106, August.
    4. Kotowski, Maciej H., 2018. "On asymmetric reserve prices," Theoretical Economics, Econometric Society, vol. 13(1), January.
    5. Cantillon, Estelle, 2008. "The effect of bidders' asymmetries on expected revenue in auctions," Games and Economic Behavior, Elsevier, vol. 62(1), pages 1-25, January.
    6. Kaplan, Todd R. & Zamir, Shmuel, 2015. "Advances in Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    7. repec:vuw:vuwscr:19224 is not listed on IDEAS
    8. Timothy Hubbard & René Kirkegaard & Harry Paarsch, 2013. "Using Economic Theory to Guide Numerical Analysis: Solving for Equilibria in Models of Asymmetric First-Price Auctions," Computational Economics, Springer;Society for Computational Economics, vol. 42(2), pages 241-266, August.
    9. Kirkegaard, René, 2009. "Asymmetric first price auctions," Journal of Economic Theory, Elsevier, vol. 144(4), pages 1617-1635, July.
    10. Timothy P. Hubbard & Harry J. Paarsch, 2012. "On the Numerical Solution of Equilibria in Auction Models with Asymmetries within the Private-Values Paradigm," Carlo Alberto Notebooks 291, Collegio Carlo Alberto.
    11. Sağlam, Yiğit, 2012. "Structural Econometric Methods in Auctions: A Guide to the Literature," Working Paper Series 19224, Victoria University of Wellington, The New Zealand Institute for the Study of Competition and Regulation.
    12. Timothy P. Hubbard & Rene Kirkegaard, 2015. "Asymmetric Auctions with More Than Two Bidders," Working Papers 1502, University of Guelph, Department of Economics and Finance.
    13. Li, Huagang & Riley, John G., 2007. "Auction choice," International Journal of Industrial Organization, Elsevier, vol. 25(6), pages 1269-1298, December.
    14. Olivier Armantier & Jean-Pierre Florens & Jean-Francois Richard, 2008. "Approximation of Nash equilibria in Bayesian games," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 23(7), pages 965-981.
    15. Mares, Vlad & Swinkels, Jeroen M., 2014. "On the analysis of asymmetric first price auctions," Journal of Economic Theory, Elsevier, vol. 152(C), pages 1-40.
    16. Rene Kirkegaard, 2005. "A Simple Approach to Analyzing Asymmetric First Price Auctions," Working Papers 0504, Brock University, Department of Economics, revised Nov 2005.
    17. Lebrun, Bernard, 2006. "Uniqueness of the equilibrium in first-price auctions," Games and Economic Behavior, Elsevier, vol. 55(1), pages 131-151, April.
    18. Prokopovych, Pavlo & Yannelis, Nicholas C., 2019. "On monotone approximate and exact equilibria of an asymmetric first-price auction with affiliated private information," Journal of Economic Theory, Elsevier, vol. 184(C).
    19. Wayne-Roy Gayle & Jean Richard, 2008. "Numerical Solutions of Asymmetric, First-Price, Independent Private Values Auctions," Computational Economics, Springer;Society for Computational Economics, vol. 32(3), pages 245-278, October.
    20. Pycia, Marek & Woodward, Kyle, 2021. "Auctions of Homogeneous Goods: A Case for Pay-as-Bid," CEPR Discussion Papers 15656, C.E.P.R. Discussion Papers.
    21. Aryal, Gaurab & Gabrielli, Maria F., 2013. "Testing for collusion in asymmetric first-price auctions," International Journal of Industrial Organization, Elsevier, vol. 31(1), pages 26-35.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:arx:papers:2303.16388. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.