PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight Liquid Welfare Guarantees for Auctions with Budgets via LP Duality

Twan Kroll, Guido Schäfer, Artem Tsikiridis

arXiv:2609.39532v1cs.GT

TL;DR

Budget-constrained auction PoA guarantees remain challenging because prior analyses are often format-specific and largely do not cover CCE. This paper uses LP duality to establish tight liquid welfare guarantees across auction formats and lower bounds that settle the budget-free uniform-price auction under no-overbidding.

  • Problem

    Prior budget-constrained auction analyses are largely format-specific and leave the robust CE and CCE solution concepts largely unexplored.

    Source: §1 · p. 2

  • Method

    An LP-duality framework uses a small set of per-bidder equilibrium statistics and budget-feasible semi-smoothness, which classical smoothness implies.

    Source: §1.1 · p. 2

  • Results

    The framework yields tight or new liquid welfare guarantees for simultaneous first-price, second-price, all-pay, and restricted-interface auctions, multi-unit formats, and generalized first-price position auctions.

    Source: §1.1 · pp. 2–3

  • Takeaways & Limitations

    Under no-overbidding, the budget-free uniform-price auction lower bound matches the upper bound, settling the format’s inefficiency.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

We study the efficiency of auctions with budget-constrained bidders and derive tight price of anarchy (PoA) bounds for coarse correlated equilibria (CCE). To this end, we develop a general framework that reduces proving PoA guarantees to finding feasible solutions to the dual of a linear program. The LP is formulated over a small number of per-bidder equilibrium statistics, incorporates constraints implied by the auction setting and equilibrium behavior, and captures a novel smoothness notion tailored to budget-constrained environments; we provide a reduction from classical smoothness to this new notion. Our approach enables simple and tight PoA analyses across a broad range of auction formats. Using our framework, we obtain tight liquid welfare guarantees for simultaneous first-price, second-price, and all-pay auctions, simultaneous auctions with restricted uniform bidding interfaces, discriminatory and uniform price multi-unit auctions, and generalized first-price position auctions. Beyond budget-constrained settings, we derive new lower bounds for the budget-free uniform price auction and generalized second-price auction; in particular, our lower bound for the uniform price auction matches the upper bound of $3.146$ by de Keijzer et al. (2013).

1 Introduction

Budget-constrained auctions are important in markets that use simple formats, but their equilibria can be inefficient and require liquid welfare rather than social welfare as the benchmark. The paper develops an LP-duality framework for bounding CCE inefficiency and applies it across auction formats, with matching lower bounds for several results.

1 Introduction

  • Budget constraints make equilibrium analysis harder because feasible actions depend on opponents’ payments and preferences are no longer quasi-linear; liquid welfare is the standard benchmark.Existing budgeted-auction PoA results are largely format-specific and leave CE and CCE comparatively unexplored, despite their relevance to learning-based bidding.Source: §1 · p. 2

1.3 Related Work

  • The paper addresses a gap in prior budgeted-auction PoA work, which was largely format-specific and mostly did not cover CE or CCE.Its framework also differs from earlier duality approaches by tracking equilibrium statistics rather than the CCE distribution itself.Source: §1 · p. 2, §1.2 · p. 3

1.1 Our Contributions

  • The framework reduces proving CCE PoA bounds to finding a feasible dual solution for an LP over a small number of per-bidder equilibrium statistics.The LP captures budget-feasible semi-smoothness, and any feasible dual solution yields a PoA bound for pay-your-bid and second-price-type rules.Source: §1.1 · p. 2, §1.2 · p. 3
  • The framework yields tight or near-tight liquid-welfare guarantees for simultaneous first-price, second-price, and all-pay auctions, restricted-uniform-bidding first-price auctions, discriminatory and uniform-price multi-unit auctions, and generalized first-price position auctions.It recovers the known tight first-price bound for XOS valuations, gives the first upper bound for subadditive valuations, and establishes bounds for the restricted uniform bidding interface.Source: §1.1 · pp. 2–3
  • Matching lower bounds cover several formats, and the budget-free uniform-price lower bound matches the paper’s upper bound under its no-overbidding assumption.The constructions hold already at mixed or pure Nash equilibrium for several formats, and therefore also for stronger equilibrium concepts.Source: §1.1 · p. 3, Table 1 · p. 3

A reduction.

  • Budget-feasible semi-smoothness makes deviations affordable; conservative budget-free deviations can be mixed with opt-out so expected payment stays within budget and the guarantee degrades to liquid valuation.This reduction leaves each auction format with the task of proving one conservative smoothness inequality.Source: A reduction · p. 4

2 Preliminaries

The preliminaries define the budgeted mechanism environment, equilibrium notions, and the ex-ante liquid-welfare benchmark used to measure inefficiency. They also establish that equilibrium expected payments do not exceed either expected value or budget.

2 Preliminaries

  • A budgeted mechanism instance specifies bidders, action and allocation sets, valuations, and budgets; an action profile determines allocations and nonnegative payments, with each bidder able to opt out at zero payment.Budget feasibility is defined in expectation, and a bidder’s admissible actions can depend on opponents’ actions, making the environment a generalized game.Source: §2 · pp. 5–6
  • The paper considers pure and mixed Nash, correlated, and coarse correlated equilibria, with mixed Nash contained in correlated equilibrium and correlated equilibrium contained in coarse correlated equilibrium.In this generalized game, pure Nash equilibria are not necessarily a subset of mixed Nash equilibria.Source: §2 · p. 6
  • Ex-ante liquid welfare sums each bidder’s expected value capped at budget, and its optimum ranges over random allocation profiles.The paper chooses this benchmark because it is consistent with in-expectation budget constraints; using ex-post liquid welfare can yield unbounded PoA even for simultaneous first-price auctions with additive valuations and mixed Nash equilibrium.Source: §2 · pp. 6–7
  • At equilibrium, each bidder’s expected payment is at most the minimum of expected value and budget.Budget feasibility gives the budget bound, while the opt-out action and equilibrium condition give the expected-value bound.Source: §2 · p. 7

3 PoA of Auctions with Budgets via LP Duality

The section develops LP-duality bounds for budget-constrained auctions by combining equilibrium constraints with budget-feasible smoothness. It reduces the PoA analysis to finding feasible dual solutions and connects classical smoothness proofs to the budgeted setting.

3 PoA of Auctions with Budgets via LP Duality

  • Budget-feasible semi-smoothness incorporates affordability into deviations, the obstacle in applying ordinary smoothness to budget-constrained bidders.Source: §3.1 · p. 8

3.1 PoA Bounds via Duality

  • The LP lower-bounds equilibrium liquid welfare using per-bidder statistics and constraints from the auction and equilibrium; its dual yields CCE PoA bounds under budget-feasible semi-smoothness.The analysis partitions bidders according to whether their expected equilibrium value reaches their budget.Source: §3.1 · pp. 9–10
  • For NOB mechanisms, Theorem 3.1 gives CCE-POA(I) ≤ µ + max{1, λ 1{I≠I∞}} / λ; for budget-free instance classes, the bound matches [63].Source: §3.1 · p. 10

3.2 Reduction

  • Conservative semi-smoothness reduces to budget-feasible semi-smoothness when deviations never pay more than the value of their targeted outcome, enabling classical smoothness proofs to support the LP bounds.The reduction uses deviations defined for arbitrary target outcomes and requires the stronger target-value payment cap.Source: §3.2 · p. 12

4 Simultaneous Single-Item Auctions

The section applies the framework to simultaneous first-price, second-price, and all-pay auctions, as well as first-price auctions with a restricted uniform bidding interface. It establishes upper bounds and, in several settings, matching lower bounds.

4.1 First-Price

  • For budget-constrained simultaneous first-price auctions, the PoA is at most 2.188 for XOS valuations and at most 3 for subadditive valuations.The XOS analysis recovers the result of Colini-Baldeschi et al. [20] without using value maximizers.Source: §4.1 · pp. 14–15

4.2 Uniform Bidding Interface

  • With the restricted uniform bidding interface, budget-constrained simultaneous first-price auctions have PoA at most 2.188, matched by a mixed Nash equilibrium lower bound.Source: §4.2 · p. 17

4.3 Second-Price

  • For every class of monotone valuations, simultaneous second-price auctions have PoA at most 2, and the bound is tight for classes containing additive valuations.The lower bound is shown for pure Nash equilibria in the budget-free setting.Source: §4.3 · p. 18

4.4 All-Pay

  • For budget-constrained simultaneous all-pay auctions with XOS valuations, the CCE PoA is at most 3, matched by a mixed Nash equilibrium lower bound.Source: §4.4 · p. 19

5 Multi-Unit Auctions

The section analyzes discriminatory and uniform price multi-unit auctions with concave valuations and budgets. It gives tight CCE PoA bounds for discriminatory auctions and for uniform price auctions under the aggregate no-overbidding condition.

5.1 Discriminatory Price

  • Discriminatory price multi-unit auctions with budgets have CCE PoA at most 2.188, matched by a lower bound.Source: §5.1 · p. 20

5.2 Uniform Price

  • Under the aggregate NOB condition, uniform price multi-unit auctions with budgets have CCE PoA at most 3.146, and budget-free pure Nash equilibria attain a matching lower bound.Source: §5.2 · p. 21

6 Position Auctions

The section studies generalized first-price and generalized second-price position auctions with budgets. It proves tight CCE bounds for generalized first-price auctions and gives a budget-free lower bound for generalized second-price auctions.

6.1 GFP

  • Generalized first-price auctions with budgets have CCE PoA at most 2.188, with a matching lower bound.Source: §6.1 · p. 22

6.2 GSP

  • Generalized second-price auctions with budgets have CCE PoA at most 3.146; budget-free pure Nash equilibria have PoA at least 2.Source: §6.2 · p. 22

7 Conclusion

The paper presents an LP-duality framework for bounding the liquid-welfare PoA of CCE and applies it to standard auction formats. Its results distinguish pay-your-bid formats, whose guarantees worsen with budgets, from second-price-type formats, where budgets do not worsen tight guarantees.

7 Conclusion

  • The framework bounds CCE liquid-welfare PoA using an LP-duality approach and yields mostly tight bounds for standard simple auction formats with budget-constrained bidders.The primal LP uses aggregate per-bidder equilibrium statistics and captures first-price, all-pay, and second-price payment rules in a unified dual framework.Source: §7 · p. 23, A Detailed Comparison with other… · p. 29
  • The second-price-type formats do not worsen under budgets, while pay-your-bid guarantees worsen; the exact GSP PoA remains open in [2, 3.146].The SSPA and UPA confirm the second-price-type result; the GSP remains unresolved.Source: §7 · p. 23
  • Settling the exact PoA of GSP and of SFPAs with subadditive valuations remains an open direction.Source: §7 · p. 23

A Detailed Comparison with other Duality-based Approaches

  • Kim Thang analyzes proportional and pacing mechanisms using KKT structure, whereas this framework directly bounds CCE inefficiency for simultaneous, multi-unit, and position auctions.The cited work’s differentiable, concave mechanism structure does not directly extend to the discrete allocations and XOS or subadditive valuations considered here.Source: A Detailed Comparison with other… · p. 29
  • The LP tracks per-bidder payments, willingness-to-pay, and thresholds, with a coupling constraint; budget-feasible deviations make smoothness arguments applicable despite budget limits.The authors contrast this with prior duality frameworks, where deviations are always feasible.Source: A Detailed Comparison with other… · p. 29

B Missing Material of Section 2

The examples distinguish deterministic from expectation-based budget feasibility and show why the liquid-welfare benchmark uses random allocation profiles. The section also clarifies no-overbidding refinements and the consequences of omitting no-overbidding.

B Missing Material of Section 2

  • Under an expected budget constraint, PNE need not be MNE; in the two-bidder first-price example, a mixed deviation is budget-feasible and profitable.The pure profile is a PNE, but bidder 1's deviation bids 2 with probability 0.5 and otherwise 0, with expected payment 1.Source: B Missing Material of Section 2 · pp. 29–30
  • Using random rather than deterministic allocation profiles strengthens the liquid-welfare benchmark; the deterministic optimum can be arbitrarily small relative to CCE liquid welfare.The example constructs a CCE in which each of n bidders has probability 1/n to win, while the deterministic optimum is 1.Source: B Missing Material of Section 2 · p. 30

C.1 NOB and Pay-Your-Bid Mechanisms

  • In pay-your-bid mechanisms, every PNE, MNE, CE, and CCE satisfies the stated NOB restriction.Source: §C.1 · p. 30

C.2 Unbounded POA without NOB

  • Without NOB, a second-price equilibrium can have unbounded PoA: a bidder with value 1 wins and pays 0 while the optimum liquid welfare is B.The winning bidder overbids, with willingness-to-pay B + 1 despite liquid welfare 1.Source: §C.2 · p. 31

C.3 NOB: Strategy vs. Equilibrium Refinement

  • NOB is imposed as an equilibrium refinement, not an action-space restriction, and holds in expectation and only in aggregate across bidders.The authors describe this as more permissive than excluding overbidding actions or imposing per-bidder conditions.Source: §C.3 · p. 31

C.4 PoA of NOB mechanisms

The section derives CCE PoA bounds for NOB mechanisms from budget-feasible semi-smoothness. It also relates classical conservative smoothness to budget-feasible variants used in the framework.

C.4 PoA of NOB mechanisms

  • For NOB mechanisms, Theorem 3.1 gives a CCE PoA bound under its threshold and budget-feasible semi-smoothness hypotheses.The theorem assumes suitable thresholds for every instance, CCE, and optimal profile.Source: §C.4 · p. 31
  • In the budget-free case, the N1 constraint set is empty, leaving the stated constraint δ + µδ ≤ 1 for the bound derivation.Source: §C.4 · p. 32

C.5 Further Smoothness

  • Conservative smoothness implies budget-feasible smoothness; the framework needs only the weaker budget-feasible semi-smoothness notion for its PoA bounds.The reduction uses deviations whose payments do not exceed the value of their targeted outcome.Source: §C.5 · pp. 32–33

D Missing Smoothness Proofs

The appendix establishes smoothness bounds for simultaneous first-price auctions with subadditive bidders and for generalized first-price position auctions. It specifies the deviations used to obtain those results and, for the latter, the conservative payment condition.

D.1 Simultaneous FPAs with Subadditive Bidders

  • Subadditive bidders in simultaneous first-price auctions are conservatively (1/2 − δ, 1)-semi-smooth for every 0 < δ < 1/2.The proof constructs mixed bids on the target allocation and invokes subadditivity to bound utility.Source: §D.1 · p. 33
  • The simultaneous first-price proof samples opponents’ winning bids and uses bids on the target allocation to establish the semi-smoothness bound.Source: §D.1 · p. 33

D.2 Generalized First-Price Auction

  • Generalized first-price bidders are conservatively (µG, µ)-semi-smooth for any µ ≥ 0, where G = 1 − e^-1.The deviation randomizes a bid level and makes the bid with a probability chosen so its expected payment is at most the targeted value.Source: §D.2 · p. 34

E.1 Simultaneous Auctions with Uniform Bids

The section establishes lower bounds for simultaneous auctions with restricted uniform bids and for simultaneous all-pay auctions. It does so with mixed Nash equilibrium constructions whose liquid welfare falls below the optimum.

E.1 Simultaneous Auctions with Uniform Bids

  • 2.188 is a lower bound on the PoA of mixed Nash equilibria for budget-constrained simultaneous first-price auctions with restricted uniform bidding.Source: §E.1 · p. 35
  • The uniform-bid construction has an equilibrium liquid welfare of B(m−ℓ+1) + ℓ, while an allocation achieves at least B(m−ℓ+1) + m −1.The construction is an MNE because no bidder has a profitable pure deviation, and therefore no profitable mixed deviation.Source: §E.1 · p. 35

E.2 Simultaneous All-Pay Auctions

  • 3 is a lower bound on the PoA of mixed Nash equilibria in budget-constrained simultaneous all-pay auctions with XOS valuations.Source: §E.2 · p. 36
  • The all-pay example uses two bidders and two items, with a mixed bid profile shown to be an MNE; taking V to infinity gives the lower bound.The instance has optimal liquid welfare exactly 3.Source: §E.2 · pp. 36–37

E.3 Discriminatory Price Auction

The section constructs a coarse correlated equilibrium for a discriminatory price multi-unit auction with budgets. Its liquid welfare yields a PoA lower bound of 2.188.

E.3 Discriminatory Price Auction

  • 2.188 is a lower bound on the PoA of CCEs in discriminatory price multi-unit auctions with budgets.Source: §E.3 · p. 37
  • The construction samples a common bid level and gives the bidders bid vectors (b, k + 1) and (b, k); the resulting profile is budget-feasible and a CCE.The distribution has an atom at zero, where bidder 2 receives k units and bidder 1 receives one; at positive levels, bidder 1 receives all k + 1 units.Source: §E.3 · pp. 37–38
  • At the constructed CCE, liquid welfare is B1 + a k, while the optimal liquid welfare is B1 + k.The bound follows by taking the limit of the resulting PoA lower bound as k grows.Source: §E.3 · p. 38

E.4 Uniform Price Auction

The section gives a lower-bound construction for the budget-free uniform price auction under the aggregate NOB. The constructed profile is a pure Nash equilibrium and yields a PoA lower bound of approximately 3.146.

E.4 Uniform Price Auction

  • Approximately 3.146 is a lower bound on the PoA of pure Nash equilibria in the budget-free uniform price auction under the aggregate NOB.Source: §E.4 · pp. 38, 41
  • The construction uses one bidder with capped unit-demand valuation and other unit-demand bidders; its bid profile has total demand equal to the number of units and price zero.The profile is shown to be NOB-feasible and a pure Nash equilibrium.Source: §E.4 · pp. 39–40
  • The optimal liquid welfare is m + A −ℓ, and the construction's limiting PoA lower bound is −W−1(−e−2) ≈3.146.The construction establishes the lower bound for every k ≥25 before taking the limit.Source: §E.4 · pp. 40–41

E.5 Generalized First-Price Auction

The section constructs a coarse correlated equilibrium for a generalized first-price auction with budgets. Its liquid welfare relative to the optimum gives a PoA lower bound of 2.188.

E.5 Generalized First-Price Auction

  • 2.188 is a lower bound on the PoA of coarse correlated equilibria in generalized first-price auctions with budgets.Source: §E.5 · p. 41
  • The construction uses three bidders with clickthrough rates 1 and δ for the first two slots, and a distribution over profiles in which all bidders submit the same bid.The optimal allocation places the budget-capped bidder in the lower slot.Source: §E.5 · p. 41
  • The constructed profile B is a CCE; choosing a := −W0(−e−2) ≈ 0.158 and taking δ → 0 yields 2 + W0(−e−2), not 2.188.At the profile, liquid welfare is 1 + a ln(a) + (1 − a)δ.Source: §E.5 · pp. 41–42
Loading 2609.39532v1…