betaFeedback

WorksComputer Science

Robust Analysis of First-Price Auctions with Large Supply

Abstract

This paper performs a robust analysis of welfare (i.e., the price of anarchy) in multi-unit first-price auctions with independent private values and unit-demand bidders. We employ a smoothness framework (see \citealp{ST-13}) to analyze the price of anarchy when supply is large. The main barrier to analysis in this framework is a worst-case bid distribution that establishes a lower bound on the price of anarchy of 1−1e1- \frac{1}{e}. We show that such worst-case distributions cannot arise in equilibrium when agents' values satisfy a mild density lower bound condition. This characterization leads to novel asymptotic lower bounds. In particular, the price of anarchy for εε-approximate equilibrium as the number of units goes to infinity is at least 1−Θ(εlog⁡(1ε))1-Θ\left(ε\log \left(\frac{1}ε\right)\right). Our analysis relies on a key structural property of equilibrium bid distributions: for a welfare analysis in any multi-unit first-price auction, it is without loss to analyze (approximate) equilibria with no atoms. In addition to this, we establish continuity and monotonicity properties of Bayes-Nash equilibria. We believe these results are of independent interest.

Introduction

Many economic environments involve the sale of multiple identical goods. A leading example is online marketplaces, where firms sell products from large inventories. Policymakers and online market designers are often interested in the welfare guarantees of standard market mechanisms as the market grows large. We study this question in a canonical first-price auction with large supply.

An agent has an independent private value for obtaining a good and submits a single bid to obtain a single unit of the good. A first-price auction allocates goods to the highest bidders, up to the total supply, and the winners pay their bids. This auction format, and variants of it, are commonly used in practice because they are simple and transparent. For instance, in 2019, Google Ad Manager transitioned to “unified first-price auctions” as it provided an increase in transparency1. A key feature of this mechanism, however, is that agents strategically shade their bids below their valuations. This causes inefficiencies in allocation: a high-value agent may lose out if she bids less aggressively than a low-value competitor. What is the extent of these inefficiencies as supply becomes large?

To study this question, we analyze the Price of Anarchy, henceforth PoAPoA, described as the worst-case ratio of equilibrium welfare to the socially optimum welfare (see Roughgarden et al.,

*We thank Ben Golub, Bruno Strulovici and Jeroen Swinkels for very valuable discussions. We used LLM tools including Refine.ink and Google DeepReview to check writing and check proofs.

†Department of Computer Science, Northwestern University. Email:[email protected].

‡University of Cambridge. Email:[email protected].

§Department of Computer Science, Northwestern University. Email:[email protected]. 2017 for a comprehensive survey of the PoA in auctions). A long line of work has studied the PoA in an environment with single-unit supply and independent private values. In pioneering work, Syrgkanis and Tardos [24] developed a smoothness framework to analyze PoA in auctions and established a lower bound of 1−1e1-\frac{1}{e}. Outside of this standard smoothness framework, Hoy et al. [10] improved the lower bound by leveraging the independence of value distributions to show that equilibrium welfare is a 0.743-fraction of socially optimum welfare. For the upper bound, Hartline et al. [6] provided a value distribution and corresponding equilibrium in which welfare is a 0.869-fraction of the optimum welfare. In a recent breakthrough result, Jin and Lu [12] showed that for a single-unit first-price auction with independent private values, the PoA is 1−1e21-\frac{1}{e^2}. Their analysis, which is outside the smoothness paradigm, characterizes the worst-case equilibrium bid distribution through a differential equation.

The smoothness framework was developed by works such as Roughgarden [18], Syrgkanis and Tardos [24], and Hartline et al. [6], and is a central technique to bound the PoA. As a proof technique, the primary appeal of this framework is its robustness to exact details of equilibrium behavior. Characterizing equilibria in first-price auctions is, in general, analytically difficult. Complex auction environments, some examples of which include auctions with combinatorial demand constraints and simultaneous composition of auctions (see Hartline, [8]), only further compound this issue. Remarkably, the smoothness framework establishes non-trivial bounds on the PoA in these complex environments without characterizing equilibrium behavior.

This paper builds on the concepts of individual efficiency and competitive efficiency — a decomposition of the smoothness framework — introduced by Hartline et al. [6]. These objects are the two main drivers of inefficiency in an auction. Individual efficiency measures losses in welfare due to aggregate uncertainty while competitive efficiency measures losses due to unpriced externalities. In any multi-unit first-price auction, unpriced externalities are absent and the only inefficiency is due to aggregate uncertainty.

Mathematically, individual efficiency is defined as the following intuitive tradeoff: in equilibrium, either an agent gets large utility, or faces strong competition from other bidders in the auction. A primary barrier to a proof approach using individual efficiency is a worst-case bid distribution which leads to a PoA lower bound of 1−1e1-\frac{1}{e} in any multi-unit first-price auction. The first contribution of this paper is to show that such worst-case bid distributions do not arise in equilibrium when values satisfy a density lower bound condition. This establishes novel PoA bounds in the large supply regime which we informally provide below.

Theorem (Informal). Consider the PoA of a kk-unit first-price auction with worst-case performance analyzed over independent value distributions satisfying a density lower bound condition and ϵ(k)\epsilon^{(k)}-approximate equilibria satisfying no over-bidding. Let ϵ:=lim⁡k→∞ϵ(k)\epsilon:= \lim_{k\to\infty}\epsilon^{(k)}.

(a) If ϵ=0\epsilon=0, then lim⁡k→∞PoA=1\lim_{k\to\infty} PoA=1.

(b) If ϵ>0\epsilon>0, then lim⁡k→∞PoA≥1−Θ(ϵlog⁡(1ϵ))\lim_{k\to\infty} PoA \ge1-\Theta\left(\epsilon\log\left(\frac{1}{\epsilon}\right)\right).

The main challenge is to analyze structural properties of (approximate) equilibria in settings where it is analytically intractable to explicitly solve for such objects. With non-identical values, the optimization problem that bidders face can be very different, leading to asymmetric equilibrium behavior. Our approach combines a law of large numbers argument with (approximately) optimal best-response properties to establish worst-case bounds on the distribution function of the kk-th order statistic of equilibrium bids. This order statistic is closely related to the individual efficiency of an auction. Indeed, any uncertainty in this statistic quantifies a bound on the PoA.

In § 4, we adapt the smoothness framework to show what feature of the limit distribution of the kk-th order statistic of equilibrium bids governs the PoA. Individual efficiency is typically defined for a fixed auction environment. Our framework adapts this definition to a sequence of auctions with increasing number of units. A key object we introduce is an extremizing sequence of bid pairs. As the name suggests, this is a sequence of pairs of bids, with each bid-pair corresponding to a particular auction in the sequence. Briefly, it has the property that the kk-th order statistic lies in the interval defined by a bid-pair with probability tending to one. Then, the area below the distribution function when restricted to this bid-pair interval governs the PoA. When the distribution function is relatively flat over a large interval, the loss in welfare is high. When it is steep over a small interval, the loss in welfare is small. We show that when agents optimally best-respond (ϵ=0\epsilon=0), the kk-th order statistic of equilibrium bids converges to a step function. When agents approximately best-respond (ϵ>0\epsilon>0), we characterize a distribution which is stochastically dominated by the kk-th order statistic in the limit; this leads to the PoA lower bound in Part (b) of the above result (see § 5).

The second contribution of this paper is to establish key structural properties of (approximate) equilibrium in first-price auctions (see § 6). Our analysis is driven by the following result: for a welfare analysis, it is without loss to analyze equilibria with no atoms. We provide an informal statement of the result below.

Theorem (Informal). Consider any ϵ\epsilon-approximate equilibrium E\mathcal{E}. For every ω>0\omega>0, there exists a profile of bid distributions E~\widetilde{\mathcal{E}} satisfying the following properties:

(a) E~\widetilde{\mathcal{E}} is an (ϵ+ω)(\epsilon+\omega)-approximate equilibrium.

(b) For every agent ii, the bid distribution E~i\widetilde{\mathcal{E}}_i has no atoms.

(c) welfare⁡(E)=welfare⁡(E~)\operatorname{welfare}(\mathcal{E}) = \operatorname{welfare}(\widetilde{\mathcal{E}}).

Approximate equilibrium bids are typically characterized by atoms, which makes them challenging to analyze. The above result reduces the problem to working with distributions without atoms. This is useful in our large market analysis and greatly simplifies agents’ optimal bidding problem. To give a quick sketch of the construction of the atom-less distribution, fix any ϵ\epsilon-approximate equilibrium and the locations of atoms in the agents’ bid distributions. Cumulatively shift the atoms to the right and add a small uniform random bid at each atom. The total cumulative shift can be arbitrarily small, so the resulting distribution is still an approximate equilibrium. Figure 1 provides a pictorial description of this construction. Surprisingly, the allocations under the constructed strategy and the original strategy have identical welfare.

Figure 1. This figure illustrates the construction of an equilibrium with no atoms E~\widetilde{\mathcal{E}} from one with atoms E\mathcal{E}. Column (a) depicts the distribution function of equilibrium bids for each agent: B1(⋅)\mathcal{B}_1(\cdot) for agent 1 and B2(⋅)\mathcal{B}_2(\cdot) for agent 2. Agent 1 has atoms at α\alpha and β\beta while agent 2 only has an atom at β\beta. Column (b) depicts the shift in bids to the right of atom α\alpha by sαs_\alpha. The red dashed line shows the uniform randomization of the bid at α\alpha. Column (c) depicts the shift in bids to the right of the atom at β+sα\beta+s_\alpha by sβs_\beta.

Finally, we establish monotonicity and continuity properties of Bayes-Nash equilibrium in any multi-unit first-price auction. This generalizes analogous structural results in the single-unit setting (see [14, 16, 25] (Maskin and Riley 2003)). The fundamental challenge in our setting is that an agent’s bid distribution need not necessarily impact the competing bid distribution of a different agent. This is because an agent’s allocation is determined by the kk-th highest bid among the remaining agents. Addressing this issue requires a different set of arguments. We believe that our structural results may be of independent interest.

There is a rich body of work on robust analysis in auctions; see Roughgarden et al. [20] for a comprehensive survey. A central technique in this literature is the smoothness framework, introduced by Roughgarden [18], Syrgkanis and Tardos [24], and Roughgarden (2015), which has proven effective for analyzing efficiency guarantees across a range of mechanisms. Hartline et al. [6] further refine this approach by decomposing smoothness into two key components—individual efficiency and competitive efficiency—which highlight structural properties of auctions that ensure near-optimal outcomes.

We view our analysis of the kk-th order statistic as a contribution to this literature. The 1−1/e1 - 1/e bound in Hartline et al. [6] was a barrier to the proof approach of separating individual efficiency and competitive efficiency. The challenge in overcoming this barrier is proving that the worst-case allocation rules for individual efficiency cannot arise in equilibrium. This paper characterizes bounds on the worst-case bid distributions allowing improvements over the 1−1/e1 - 1/e bound for both Bayes-Nash and approximate equilibria.

A broader generalization of the smoothness framework, developed by Feldman et al. [5], extends the analysis of inefficiency to large games and has been applied to mechanisms such as the simultaneous uniform-price auction and greedy combinatorial auction. Their results are complementary to ours, as both address efficiency guarantees in large-scale market environments.

In the economics literature, there is a long tradition of studying large-market limits of auctions and games (see [26, 21, 22] (Swinkels 2001)). The study most closely related to ours is Swinkels [22], which analyzes large-market limits of Bayes-Nash equilibria in multi-unit first-price auctions. This work directly characterizes the limit PoA bound of 11 when ϵ(k)=0\epsilon^{(k)} = 0 for every k∈Nk \in\mathbb{N}. Their analysis is outside the smoothness paradigm of individual efficiency in the sense that it establishes welfare guarantees without characterizing the behavior of the kk-th order statistic. We have a detailed discussion of how our analysis relates to this work when we provide our PoA bounds in § 5.

The inefficiency of finite auction environments has also received significant attention. Notable contributions include Feldman et al. [4], Bhawalkar and Roughgarden [1], and Markakis and Telelis [15], who analyze the efficiency of uniform-price and simultaneous-item auctions. The single-unit first-price auction, in particular, has been studied extensively (see Kaplan and Zamir, [13]; Hoy et al., [10]). A central challenge across this literature lies in the characterization of Bayes-Nash equilibria, which often admit complex or non-explicit forms. In a recent breakthrough, Jin and Lu [12] show that the price of anarchy for the single-unit first-price auction is 1−1/e21 - 1/e^{2}. Their analysis characterizes the worst-case equilibrium bid distribution by solving a differential equation. Extending this type of characterization to the multi-unit setting presents substantial analytical challenges.

In orthogonal work on multi-unit mechanisms that are not winner-pays-bid, a growing body of evidence suggests that such mechanisms tend to achieve stronger welfare performance than their single-unit counterparts. For example, Yan [27] uses a correlation gap argument to show that, in posted-price mechanisms with independent values, the price of anarchy converges asymptotically to 11 at a rate of 1−O(1/k)1 - O(1/\sqrt{k}). This bound is tight when agent values are identically distributed. Similarly, Chawla et al. [2] study anonymous posted-price mechanisms and demonstrate that, under independent values, the worst-case distribution of agent demand is Poisson, allowing welfare approximation ratios to be computed for any finite number of units. Building on this line of work, Jiang et al. [11] establish that the exact rate of convergence of the welfare approximation ratio is 1−Θ(ln⁡(k)/k)1 - \Theta(\sqrt{\ln(k)}/k).

Model

There are k∈Nk \in\mathbb{N} identical units and there are n(k)n^{(k)} single-dimensional single-unit demand agents, indexed by N(k)={1,2,…,n(k)}\mathcal{N}^{(k)} = \{1,2,\ldots,n^{(k)}\}. We assume k<n(k)k < n^{(k)} because there is no loss in efficiency when k≥n(k)k \ge n^{(k)}—all agents are allocated a unit. Each agent ii has a private valuation drawn independently from a distribution Vi\mathcal{V}_i. We denote this auction environment by A(k)\mathcal{A}^{(k)}. Consider a sequence of auctions (A(k))k=1∞(\mathcal{A}^{(k)})_{k=1}^{\infty} with value distributions satisfying the following conditions:

Assumption 1. (a) (Bounded Support) There exists a constant H<∞H < \infty such that for any kk and any agent i∈N(k)i \in\mathcal{N}^{(k)}, their value viv_i is at most HH almost surely.

(b) (Density Lower Bound) There exists a constant κ>0\kappa> 0 such that for any kk and any agent i∈N(k)i \in\mathcal{N}^{(k)}, for any Δ>0\Delta> 0 and any value v∈[0,H−Δ]v \in[0,H-\Delta], the measure of values

Pr⁡[Vi∈(v,v+Δ)]>κΔ.\Pr[V_i \in(v,v+\Delta)] > \kappa\Delta.

Fix any k∈Nk \in\mathbb{N}. We suppress the dependence on kk in our notation when describing the auction rules. Each agent submits a single non-negative bid bib_i. Units are sold using a first-price auction. The kk agents with the highest bids each receive one unit and pay their submitted bid, with ties broken uniformly at random. Agents have a quasi-linear utility.

A strategy for agent ii is a mapping Ei:Vi→Δ(R≥0)\mathcal{E}_i:\mathcal{V}_i \to\Delta(\mathbb{R}_{\ge0}) from her valuation to a distribution over bids. We will denote the distribution over bids for a value viv_i by Ei,vi\mathcal{E}_{i,v_i}. Sometimes we will overload notation and denote the marginal distribution over bids by Ei\mathcal{E}_i. We will clarify when we do so. We denote a strategy profile by E:=(Ei)i∈N\mathcal{E}:=(\mathcal{E}_i)_{i\in\mathcal{N}}.

Given a strategy profile, distribution over bids determines interim outcomes. The interim allocation rule for agent ii is a function xi:R≥0→[0,1]x_i:\mathbb{R}_{\ge0}\to[0,1] that specifies the probability that agent ii receives a unit when submitting a bid bib_i. Similarly, the interim payment rule pi:R≥0→R≥0p_i:\mathbb{R}_{\ge0}\to\mathbb{R}_{\ge0} gives agent ii’s expected payment conditional on bidding bib_i. The interim utility of agent ii with valuation viv_i and bid bib_i is

ui(vi,bi)=vixi(bi)−pi(bi).u_i(v_i,b_i)=v_i x_i(b_i)-p_i(b_i).

The optimal interim utility of agent ii with valuation viv_i is ui(vi)u_i(v_i).

Our solution concept is an ϵ\epsilon-approximate Bayes-Nash equilibrium. We provide a definition below for completeness.

Definition (ϵ\epsilon-approximate Bayes Nash Equilibrium). A strategy profile E\mathcal{E} is said to be an ϵ\epsilon-approximate Bayes-Nash equilibrium if for every agent i∈Ni \in\mathcal{N}, we have

Eb∼Ei,vi[ui(vi,b)]≥sup⁡bi∈R≥0ui(vi,bi)−ϵfor every vi∈supp⁡(Vi).\mathbb{E}_{b\sim\mathcal{E}_i,v_i}\left[u_i(v_i,b)\right]\geq\sup_{b_i\in\mathbb{R}_{\geq0}}u_i(v_i,b_i)-\epsilon\quad\text{for every }v_i\in\operatorname{supp}(\mathcal{V}_i).

We impose a mild no over-bidding assumption on equilibrium bidding behavior. Our results for exact Bayes-Nash equilibrium continue to hold without this assumption.

Assumption 2 (No Over-Bidding). Consider any auction A\mathcal{A} and equilibrium E\mathcal{E}. For any agent i∈Ni \in\mathcal{N} and value vv, the equilibrium bid Ei,v\mathcal{E}_{i,v} is at most vv almost surely.

Our goal is to perform a robust analysis of equilibrium welfare as the number of units kk becomes large. To that end, consider any kk-unit first-price auction A(k)\mathcal{A}^{(k)} and any corresponding equilibrium E(k)\mathcal{E}^{(k)}. Let expected equilibrium welfare be W(E(k),A(k))\mathcal{W}(\mathcal{E}^{(k)},\mathcal{A}^{(k)}) and expected optimal welfare be O(A(k))\mathcal{O}(\mathcal{A}^{(k)}). The rest of the paper focuses on analyzing asymptotic inefficiencies in equilibria, measured by the following quantity:

inf⁡{(A(k),E(k))}k=1∞lim inf⁡k→∞W(E(k),A(k))O(A(k)).\inf_{\left\{\left(\mathcal{A}^{(k)},\mathcal{E}^{(k)}\right)\right\}_{k=1}^{\infty}}\liminf_{k\to\infty}\frac{\mathcal{W}\left(\mathcal{E}^{(k)},\mathcal{A}^{(k)}\right)}{\mathcal{O}\left(\mathcal{A}^{(k)}\right)}.

In the objective above, the value distribution parameters H>0H>0, κ>0\kappa>0 and the best-response approximation lim⁡k→∞ϵ(k)=ϵ\lim_{k\to\infty}\epsilon^{(k)}=\epsilon are fixed and define the family of auction-equilibrium sequences over which the infimum is evaluated.

Robust Framework For Equilibrium Analysis

This section introduces a framework that facilitates a robust analysis of equilibrium welfare in an auction. In general, an auction admits multiple equilibria with very different welfare. Furthermore, their structure is extremely sensitive to the agents’ value distribution. This makes a direct analysis of all possible equilibria intractable. The smoothness framework provides a robust approach by establishing welfare guarantees that hold uniformly across value distributions and their corresponding equilibria.

Framework Parameters

We begin by defining two properties attributed to any auction: individual efficiency and competitive efficiency (see Hartline et al., 2023 and Syrgkanis and Tardos, [24] for closely related definitions). Together, they determine the worst-case welfare loss in every equilibrium.

We begin with the individual efficiency of an auction. To introduce some notation, consider an auction A\mathcal{A} and any corresponding equilibrium E\mathcal{E}. The individual efficiency of an auction is defined in terms of the utility of an entrant agent who competes against the incumbents playing according to equilibrium E\mathcal{E}. Let B(k)\mathcal{B}^{(k)} denote the entrant’s critical bid, that is, the minimum bid required to be allocated, and let B^\widehat{B} denote its expectation. Furthermore, let B(k)(⋅)\mathcal{B}^{(k)}(\cdot) denote its distribution function. For example, in a multi-unit first-price auction with kk units, B(k)\mathcal{B}^{(k)} is the kk-th highest equilibrium bid. The entrant has value vv and best responds to obtain utility u(v)u(v).

Definition (Individual Efficiency). An auction A\mathcal{A} is said to be η\eta-individually efficient if for any ϵ\epsilon-approximate Bayes-Nash equilibrium E\mathcal{E}, we have

u(v)+B^≥ηvfor every value v.u(v) + \widehat{B} \ge\eta v \qquad\text{for every value } v.

The individual efficiency of auction A\mathcal{A} is the largest η\eta such that the auction is η\eta-individually efficient.

We provide some intuition for this definition. The individual efficiency of an auction captures an inherent tradeoff: either the optimal utility is large (u(v)u(v) is large) or the agent faces strong competition in the auction (large expected critical bid B^\widehat{B}). Then, the sum of utility and expected critical bid recovers a large fraction of available surplus. Figure 2 provides a geometric interpretation.

Geometric interpretation of individual efficiency

Figure 2. The solid blue curve plots the distribution function of the kk-th highest bid B(k)(⋅)\mathcal{B}^{(k)}(\cdot) as a function of bids. The blue cross-hatched area is the optimal utility u(v)u(v). The red area above the curve (slanting lines) is the expected critical bid B^\widehat{B}. The green region (vertical lines) has area vv. Individual efficiency measures what fraction of the green area does the total of blue and red area cover.

To further illustrate this definition, we present the individual efficiency guarantee for any multi-unit first-price auction together with a proof (see Hartline et al., 2023 for individual efficiency guarantees in other auction environments).

References

  1. [1]Bhawalkar, K. and T. Roughgarden (2011): “Welfare guarantees for combinatorial auctions with item bidding,” in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, USA: Society for Industrial and Applied Mathematics, SODA ’11, 700–709.
  2. [2]Chawla, S., N. Devanur, and T. Lykouris (2023): “Static pricing for multi-unit prophet inequalities,” Operations Research.arxiv.org/abs/2007.07990
  3. [3]Chawla, S. and J. D. Hartline (2013): “Auctions with unique equilibria,” in Proceedings of the Fourteenth ACM Conference on Electronic Commerce, New York, NY, USA: Association for Computing Machinery, EC ’13, 181–196.
  4. [4]Feldman, M., H. Fu, N. Gravin, and B. Lucier (2013): “Simultaneous auctions are (almost) efficient,” in Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, New York, NY, USA: Association for Computing Machinery, STOC ’13, 201–210.arxiv.org/abs/1209.4703
  5. [5]Feldman, M., N. Immorlica, B. Lucier, T. Roughgarden, and V. Syrgkanis (2016): “The price of anarchy in large games,” in Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, New York, NY, USA: Association for Computing Machinery, STOC ’16, 963–976.
  6. [6]Hartline, J. D., Hoy, and S. Taggart (2014): “Price of anarchy for auction revenue,” in Proceedings of the Fifteenth ACM Conference on Economics and Computation, New York, NY, USA: Association for Computing Machinery, EC ’14, 693–710.
  7. [8]Hartline, J. D. (2016): Mechanism Design and Approximation, Unpublished manuscript.
  8. [9]Helly, E. (1912): “Über lineare Funktionsoperatoren,” Sitzungsberichte der Kaiserlichen Akademie der Wissenschaften, Mathematisch-Naturwissenschaftliche Klasse, 121, 265–297.
  9. [10]Hoy, D., S. Taggart, and Z. Wang (2018): “A tighter welfare guarantee for first-price auctions,” in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, New York, NY, USA: Association for Computing Machinery, STOC 2018, 132–137.
  10. [11]Jiang, J., W. Ma, and J. Zhang (2023): “Tightness without Counterexamples: A New Approach and New Results for Prophet Inequalities,” in Proceedings of the 24th ACM Conference on Economics and Computation, New York, NY, USA: Association for Computing Machinery, EC ’23, 909.
  11. [12]Jin, Y. and P. Lu (2023): “First Price Auction is 1-1/e2 Efficient,” J. ACM, 70.
  12. [13]Kaplan, T. R. and S. Zamir (2012): “Asymmetric First-Price Auctions with Uniform Distributions: Analytic Solutions to the General Case,” Economic Theory, 50, 269–302.
  13. [14]Lebrun, B. (1999): “First Price Auctions in the Asymmetric N Bidder Case,” International Economic Review, 40, 125–142.
  14. [15]Markakis, E. and O. Telelis (2015): “Uniform Price Auctions: Equilibria and Efficiency,” Theor. Comp. Sys., 57, 549–575.
  15. [16]Maskin, E. and J. Riley (2000): “Equilibrium in Sealed High Bid Auctions,” The Review of Economic Studies, 67, 439–454.
  16. [18]Roughgarden, T. (2012): “The price of anarchy in games of incomplete information,” in Proceedings of the 13th ACM Conference on Electronic Commerce, New York, NY, USA: Association for Computing Machinery, EC ’12, 862–879.
  17. [20]Roughgarden, T., V. Syrgkanis, and E. Tardos (2017): “The price of anarchy in auctions,” J. Artif. Int. Res., 59, 59–101.arxiv.org/abs/1607.07684
  18. [21]Rustichini, A., M. A. Satterthwaite, and S. R. Williams (1994): “Convergence to Efficiency in a Simple Market with Incomplete Information,” Econometrica, 62, 1041–63.
  19. [22]Swinkels, J. M. (1999): “Asymptotic efficiency for discriminatory private value auctions,” The Review of Economic Studies, 66, 509–528.DOI
  20. [24]Syrgkanis, V. and E. Tardos (2013): “Composable and efficient mechanisms,” New York, NY, USA: Association for Computing Machinery, STOC ’13, 211–220.
  21. [25]Wang, Z., W. Shen, and S. Zuo (2020): “Bayesian Nash Equilibrium in First-Price Auction with Discrete Value Distributions,” in Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, International Foundation for Autonomous Agents and Multiagent Systems, AAMAS ’20, 1458–1466.arxiv.org/abs/1906.09403
  22. [26]Wilson, R. (1977): “A Bidding Model of Perfect Competition,” The Review of Economic Studies, 44, 511–518.DOI
  23. [27]Yan, Q. (2011): “Mechanism design via correlation gap,” in Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, SIAM, 710–719.arxiv.org/abs/1008.1843

Paper details

vlnc:W_5cs6hyfk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents