pith. sign in

arxiv: 1906.09403 · v2 · pith:X4433R6Xnew · submitted 2019-06-22 · 💻 cs.GT

Bayesian Nash Equilibrium in First-Price Auction with Discrete Value Distributions

Weiran Shen , Zihe Wang , Song Zuo This is my paper

Pith reviewed 2026-05-25 18:17 UTC · model grok-4.3

classification 💻 cs.GT
keywords first-price auctionBayesian Nash equilibriumdiscrete value distributionsasymmetric auctionsindependent private valuesequilibrium computationauction theory
0
0 comments X

The pith

First-price auctions with discrete bidder values have a unique Bayesian Nash equilibrium.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves existence and uniqueness of the Bayesian Nash Equilibrium for first-price auctions when bidders draw values from discrete distributions. It supplies a direct algorithm to find the equilibrium strategies. This matters because many practical auctions involve discrete possible values or bids, and continuous approximations can produce both speed and accuracy problems. The discrete case requires its own proof since continuous uniqueness results do not transfer.

Core claim

In the asymmetric independent private values model, a first-price auction with discrete value distributions admits a unique Bayesian Nash Equilibrium; the equilibrium can be recovered exactly by an algorithm that operates directly on the finite support points rather than by solving ordinary differential equations.

What carries the argument

The algorithm that computes the BNE by characterizing best-response strategies at each discrete value point and solving the resulting finite system.

If this is right

  • Equilibrium strategies can be computed without the numerical errors that arise from solving differential equations or from approximating discrete supports by continuous densities.
  • Auctioneers and bidders can obtain exact predictions for settings such as government procurement where values or bids are naturally discrete.
  • Analysis of first-price auctions must treat the discrete case separately rather than relying on limiting arguments from the continuous case.
  • The same algorithmic approach yields both existence and uniqueness in one pass.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Procurement platforms could embed the algorithm to suggest bids to participants in real time.
  • The method may generalize to other sealed-bid formats once their discrete equilibria are characterized.
  • Empirical tests on field data from discrete-bid auctions could check whether observed behavior matches the predicted unique equilibrium.
  • Hybrid models that mix a few discrete types with a continuous component could be studied by extending the finite-support technique.

Load-bearing premise

Buyers' value distributions are common knowledge and independent of one another.

What would settle it

An explicit pair of discrete distributions for two bidders in an asymmetric first-price auction for which either no pure-strategy BNE exists or more than one such equilibrium exists.

Figures

Figures reproduced from arXiv: 1906.09403 by Song Zuo, Weiran Shen, Zihe Wang.

Figure 1
Figure 1. Figure 1: The equilibrium strategy of two i.i.d. buyers with uniform [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Each value’s corresponding bid interval is indicated by braces. A dot implies [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Monotonicity of b( ¯b). In the left part, the guess is ¯b = 8.5 and the algorithm stops at b( ¯b) = 0.35. In the right part, the guess is ¯b = 9.5, and the algorithm stops at b( ¯b) = 3.76. 5 Existence and uniqueness of the BNE 5.1 Existence In Algorithm 2, if the point b( ¯b) where the algorithm terminates does not match the actual smallest winning bid b, the bidding strategies we get do not form a BNE. B… view at source ↗
Figure 5
Figure 5. Figure 5: The oscillation of continuous algorithms. The two curves corresponds to buyer [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Running time comparison. The y-axis is the cumulative distribution of the [PITH_FULL_IMAGE:figures/full_fig_p020_6.png] view at source ↗
read the original abstract

First price auctions are widely used in government contracts and industrial auctions. In this paper, we consider the Bayesian Nash Equilibrium (BNE) in first price auctions with discrete value distributions. We study the characterization of the BNE in the first price auction and provide an algorithm to compute the BNE at the same time. Moreover, we prove the existence and the uniqueness of the BNE. Some of the previous results in the case of continuous value distributions do not apply to the case of discrete value distributions. In the meanwhile, the uniqueness result in discrete case cannot be implied by the uniqueness property in the continuous case. Unlike in the continuous case, we do not need to solve ordinary differential equations and thus do not suffer from the solution errors therein. Compared to the method of using continuous distributions to approximate discrete ones, our experiments show that our algorithm is both faster and more accurate. The results in this paper are derived in the asymmetric independent private values model, which assumes that the buyers' value distributions are common knowledge.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript claims to characterize the Bayesian Nash Equilibrium (BNE) for first-price auctions under discrete value distributions in the asymmetric independent private values (IPV) model. It provides an algorithm to compute the BNE, proves existence and uniqueness of the equilibrium, and argues that standard results from the continuous case (including uniqueness) do not carry over. The approach avoids solving ODEs and is shown via experiments to be faster and more accurate than approximating discrete distributions by continuous ones.

Significance. If the existence/uniqueness proofs and algorithm are correct, the work supplies a direct, non-approximative method for a practically relevant setting (discrete supports) where continuous-case techniques fail. The explicit algorithm and experimental comparison constitute a concrete, falsifiable contribution that can be checked by implementation.

minor comments (3)
  1. The abstract states that 'some of the previous results in the case of continuous value distributions do not apply' and that 'the uniqueness result in discrete case cannot be implied by the uniqueness property in the continuous case,' but does not name the specific continuous-case theorems being referenced; adding these citations in the introduction would clarify the precise gap being filled.
  2. The model section should explicitly state the finite support assumption (number of atoms per distribution) and whether the supports are required to be identical across bidders; this is load-bearing for the algorithm description.
  3. The experimental section compares runtime and accuracy against a continuous approximation; the paper should report the exact discretization grid size used in the baseline and the number of Monte Carlo replications for the accuracy metric.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation for minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; direct mathematical proof of existence/uniqueness

full rationale

The paper's central contribution is a direct theoretical proof of existence and uniqueness of Bayesian Nash Equilibrium for the first-price auction under discrete value distributions in the asymmetric IPV model. The abstract explicitly notes that continuous-case results do not carry over and that a separate argument is required, with the derivation framed as a self-contained characterization plus algorithm rather than any reduction to fitted parameters, self-citations, or imported uniqueness theorems. No load-bearing steps reduce by construction to inputs; the model assumptions are standard and externally stated. This is the expected outcome for a pure existence/uniqueness proof paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard independent private values assumption with common-knowledge discrete distributions; no free parameters or invented entities are mentioned in the abstract.

axioms (1)
  • domain assumption Buyers' value distributions are common knowledge in the asymmetric independent private values model.
    Explicitly stated as the modeling framework in the final sentence of the abstract.

pith-pipeline@v0.9.0 · 5705 in / 1103 out tokens · 28896 ms · 2026-05-25T18:17:32.078602+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Credible mechanisms

    Mohammad Akbarpour and Shengwu Li. Credible mechanisms. InProceedings of the 2018 ACM Conference on Economics and Computation, pages 371–371. ACM, 2018

    work page 2018

  2. [2]

    Single crossing properties and the existence of pure strategy equilibria in games of incomplete information.Econometrica, 69(4):861–889, 2001

    Susan Athey. Single crossing properties and the existence of pure strategy equilibria in games of incomplete information.Econometrica, 69(4):861–889, 2001

    work page 2001

  3. [3]

    Comparing competition and collusion: a numerical approach.Eco- nomic Theory, 18(1):187–205, 2001

    Patrick Bajari. Comparing competition and collusion: a numerical approach.Eco- nomic Theory, 18(1):187–205, 2001

    work page 2001

  4. [4]

    Auctionswithuniqueequilibria

    ShuchiChawlaandJasonDHartline. Auctionswithuniqueequilibria. In Proceedings of the fourteenth ACM conference on Electronic commerce, pages 181–196. ACM, 2013

    work page 2013

  5. [5]

    Existence and computation of equilibria of first-price auctions with integral valuations and bids

    Guillaume Escamocher, Peter Bro Miltersen, and Rocio Santillan. Existence and computation of equilibria of first-price auctions with integral valuations and bids. In AAMAS (2), pages 1227–1228. Citeseer, 2009

    work page 2009

  6. [6]

    Asymmetric first-price auctions-a perturbation approach

    Gadi Fibich and Arieh Gavious. Asymmetric first-price auctions-a perturbation approach. Mathematics of Operations Research, 28(4):836–852, 2003. 22

    work page 2003

  7. [7]

    Numerical simulations of asymmetric first-price auc- tions

    Gadi Fibich and Nir Gavish. Numerical simulations of asymmetric first-price auc- tions. Games and Economic Behavior, 73(2):479–495, 2011

    work page 2011

  8. [8]

    Asymmetric first-price auctions-a dynamical-systems approach

    Gadi Fibich and Nir Gavish. Asymmetric first-price auctions-a dynamical-systems approach. Mathematics of Operations Research, 37(2):219–243, 2012

    work page 2012

  9. [9]

    Numerical solutions of asymmetric, first-price, independent private values auctions

    Wayne-Roy Gayle and Jean Francois Richard. Numerical solutions of asymmetric, first-price, independent private values auctions. Computational Economics, 32(3): 245–278, 2008

    work page 2008

  10. [10]

    Price of anarchy for auction revenue

    Jason Hartline, Darrell Hoy, and Sam Taggart. Price of anarchy for auction revenue. InProceedings of the fifteenth ACM conference on Economics and computation, pages 693–710. ACM, 2014

    work page 2014

  11. [11]

    A tighter welfare guarantee for first- price auctions

    Darrell Hoy, Samuel Taggart, and Zihe Wang. A tighter welfare guarantee for first- price auctions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 132–137. ACM, 2018

    work page 2018

  12. [12]

    Asymmetric first-price auctions with uniform distributions: analytic solutions to the general case.Economic Theory, 50(2):269– 302, 2012

    Todd R Kaplan and Shmuel Zamir. Asymmetric first-price auctions with uniform distributions: analytic solutions to the general case.Economic Theory, 50(2):269– 302, 2012

    work page 2012

  13. [13]

    Existence of an equilibrium in first price auctions

    Bernard Lebrun. Existence of an equilibrium in first price auctions. Economic Theory, 7(3):421–443, 1996

    work page 1996

  14. [14]

    First price auctions in the asymmetric n bidder case.International Economic Review, 40(1):125–142, 1999

    Bernard Lebrun. First price auctions in the asymmetric n bidder case.International Economic Review, 40(1):125–142, 1999

    work page 1999

  15. [15]

    Continuity of the first price auction nash equilibrium correspon- dence

    Bernard Lebrun. Continuity of the first price auction nash equilibrium correspon- dence. Economic Theory, 20(3):435–453, 2002

    work page 2002

  16. [16]

    Uniqueness of the equilibrium in first-price auctions.Games and Economic Behavior, 55(1):131–151, 2006

    Bernard Lebrun. Uniqueness of the equilibrium in first-price auctions.Games and Economic Behavior, 55(1):131–151, 2006

    work page 2006

  17. [17]

    Auction choice.International Journal of Industrial Organization, 25(6):1269–1298, 2007

    Huagang Li and John G Riley. Auction choice.International Journal of Industrial Organization, 25(6):1269–1298, 2007

    work page 2007

  18. [18]

    Numerical analysis of asymmetric first price auctions.Games and Eco- nomic Behavior, 7(2):193–220, 1994

    Robert C Marshall, Michael J Meurer, Jean-Francois Richard, and Walter Stromquist. Numerical analysis of asymmetric first price auctions.Games and Eco- nomic Behavior, 7(2):193–220, 1994

    work page 1994

  19. [19]

    Equilibrium in sealed high bid auctions.The Review of Economic Studies, 67(3):439–454, 2000

    Eric Maskin and John Riley. Equilibrium in sealed high bid auctions.The Review of Economic Studies, 67(3):439–454, 2000

    work page 2000

  20. [20]

    Uniqueness of equilibrium in sealed high-bid auctions

    Eric Maskin and John Riley. Uniqueness of equilibrium in sealed high-bid auctions. Games and Economic Behavior, 45(2):395–409, 2003

    work page 2003

  21. [21]

    A theory of auctions and competitive bidding

    Paul R Milgrom and Robert J Weber. A theory of auctions and competitive bidding. Econometrica: Journal of the Econometric Society, pages 1089–1122, 1982

    work page 1982

  22. [22]

    Characterization and computation of nash-equilibria for auctions with incomplete information.International Journal of Game Theory, 20(4):393–418, 1992

    Michael Plum. Characterization and computation of nash-equilibria for auctions with incomplete information.International Journal of Game Theory, 20(4):393–418, 1992. 23

    work page 1992

  23. [23]

    Optimal auctions.The American Economic Review, 71(3):381–392, 1981

    John G Riley and William F Samuelson. Optimal auctions.The American Economic Review, 71(3):381–392, 1981

    work page 1981

  24. [24]

    On different methods for allocating resources.Kyklos, 23(2):332–337, 1970

    Martin Shubik. On different methods for allocating resources.Kyklos, 23(2):332–337, 1970

    work page 1970

  25. [25]

    Big changes coming to auctions, as exchanges roll the dice on first-price

    Sarah Sluis. Big changes coming to auctions, as exchanges roll the dice on first-price. URL: https://adexchanger. com/platforms/big-changescoming-auctions-exchanges- roll-dice-first-price, 2017

    work page 2017

  26. [26]

    Counterspeculation, auctions, and competitive sealed tenders.The Journal of finance, 16(1):8–37, 1961

    William Vickrey. Counterspeculation, auctions, and competitive sealed tenders.The Journal of finance, 16(1):8–37, 1961. 24 APPENDIX A Omitted proof in Section 4 A.1 Proof of Theorem 2 To prove Theorem 2, We first consider a lemma which compare buyers’ value from the bid distribution. Lemma 8. Assume bidb1 is an element inSi(vi), and bidb2 is an element inSj...

    work page 1961

  27. [27]

    Other buyers’ next values are smaller than or equal to the value at end point

    Hence, the bidding set only contains buyer 1 at the end point. Other buyers’ next values are smaller than or equal to the value at end point. Then we put the remaining bid probability of buyer 1 on biddingb. We are also able to create a bidding strategy For other buyers when their value smaller than or equal tob, we create a bidding strategy such that the...

    work page