Tight Liquid Welfare Guarantees for Auctions with Budgets

arXiv:2609.39532 · cs.GT · Submitted 2026-09-30 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Tight Liquid Welfare Guarantees for Auctions with Budgets".

Jane: Here's the gist of the paper. Tight liquid welfare guarantees for auctions with budgets via LP duality study the efficiency of auctions with budget-constrained bidders and derive tight price of anarchy bounds for coarse correlated equilibria (CCE) <ref:2609.39532#pg2>.

Tom: Framework Development The authors develop a general framework that reduces proving PoA guarantees to finding feasible solutions to the dual of a linear program <ref:2609.39532#pg2> 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 <ref:2609.39532#pg2> This approach enables simple and tight PoA analyses across a broad range of auction formats <ref:2609.39532#pg2>.

Jane: Key Contributions The paper presents several key results, including the development of a linear programming framework that reduces proving PoA bounds for CCE of budget-constrained bidders to finding a feasible solution to the dual (Dual LP) of a linear program <ref:2609.39532#pg2> This framework yields tight or near-tight liquid welfare guarantees for a number of auction formats of practical significance <ref:2609.39532#pg2>.

Tom: Specifically, they recover the tight bound of

20: for first-price auctions (FPAs) with fractionally subadditive (XOS) valuations <ref:2609.39532#pg2> and derive new tight bounds for the second-price and all-pay variants <ref:2609.39532#pg2>.

Paper summary: Tom: So, we're talking about this paper now called "Tight Liquid Welfare Guarantees for Auctions with Budgets". Basically, they're looking at how efficiency works in auctions where bidders have limits on what they can spend.

Jane: Right. The main idea here is that proving efficiency guarantees in these budget-constrained settings is really hard, so they've built a new way to solve it using the dual of a linear program.

Lu: It’s about turning a game theory problem into an optimization problem over some per-bidder statistics, and they introduce this new smoothness notion specifically for budget-constrained environments <ref:2609.39532#pg2>. That's the technical engine they developed to make things work.

Meng: But what does that actually mean for us at the startup? Are we talking about something that can handle real traffic, or is this just theoretical fluff?

Tom: Well, they’ve shown this framework lets them get tight bounds on the price of anarchy, or PoA, for coarse correlated equilibria in these budget settings <ref:2609.39532#pg2>. That means they can give us a real guarantee on how much worse the outcome can be compared to the perfect scenario.

Jane: The paper claims they recovered tight bounds for several auction types, including simultaneous first-price, second-price, and all-pay auctions <ref:2609.39532#pg1>. They even got a specific bound of two point one eight eight for those simultaneous first-price auctions with fractionally subadditive valuations <ref:2609.39532#pg3>.

Lu: And they also derived new tight bounds for the second-price and all-pay variants, which is interesting because budget constraints make things fundamentally different from the budget-free cases <ref:2609.39532#pg2>.

Meng: So, if I’m running a system where users have budgets, this suggests we can actually predict how much inefficiency we're going to see, instead of just guessing based on standard models. But what's the catch?

Tom: The catch is that the framework relies on finding a feasible solution to the dual linear program <ref:2609.39532#pg2>. The complexity shifts from proving a hard inequality to solving this specific optimization problem.

Jane: And they showed how this new smoothness notion connects back to classical smoothness, which is important because it gives them a principled way to get these PoA bounds across many different auction formats <ref:2609.39532#pg1>.

Lu: The paper’s technical comparison with prior work is notable because they use aggregate per-bidder equilibrium statistics instead of the full distribution of the correlated equilibria themselves <ref:2609.39532#pg2>. That coupling constraint they used to unify first-price, all-pay, and second-price rules is a key technical ingredient.

Meng: From an engineering standpoint, that sounds promising for deployment because it unifies the analysis across different auction types under one single mathematical structure <ref:2609.39532#pg2>. But how sure are we about these bounds when real-world bidding isn't perfectly correlated?

Paper summary: Tom: Lalam’s looking at the literature, and I think it confirms that this approach is solid because it handles the complexities introduced by budget constraints in two major ways <ref:2609.39532#pg2>. First, the auction becomes a generalized game where actions depend on payments induced by other bidders.

Jane: And second, quasi-linearity gets lost when budgets are involved, which means social welfare isn't the right benchmark anymore; liquid welfare is what you have to use instead <ref:2609.39532#pg2>. That’s a big shift in how we think about efficiency here.

Lu: The results show that second-price-type payment rules don't get worse under budget constraints, but the pay-your-bid formats do provably get worse <ref:2609.39532#pg1>. This is a significant distinction in the guarantees they provide <ref:2609.39532#pg1>.

Meng: So, for production systems that involve user budgets, we might find that second-price rules are safer bets than pay-your-bid formats if you want tight guarantees on inefficiency <ref:2609.39532#pg1>. What about the actual numbers for those worst cases?

Tom: They give a specific bound of two point one eight eight for simultaneous first-price auctions with fractionally subadditive valuations <ref:2609.39532#pg3>. That's a concrete number tied to a specific auction setup <ref:2609.39532#pg1>.

Jane: And they also showed that in multi-unit auctions, the PoA for coarse correlated equilibria in discriminatory price multi-unit auctions with budgets is at most two point one eight eight <ref:2609.39532#pg3>. That applies to a lot of complex scenarios involving many bidders and different pricing rules.

Lu: They also looked at position auctions, and for those, the PoA for coarse correlated equilibria in GFP auctions with budgets is at most two point one eight eight <ref:2609.39532#pg3>. That shows the framework isn't just limited to simple simultaneous or multi-unit settings.

Meng: The paper also mentions that for uniform price auctions under aggregate no bidding over budget, the PoA is at most about three point one four six <ref:2609.39532#pg3>. That’s a higher number compared to some other formats, which makes sense given the constraints on those specific types of auctions.

Tom: The paper also gives lower bound constructions, which means they aren't just giving us upper limits; they’re showing that these bounds are achievable in certain situations <ref:2609.39532#pg1>. For instance, for budget-constrained simultaneous FPAs with restricted uniform bidding interfaces, the MNE price of anarchy is at least two point one eight eight <ref:2609.39532#pg1>.

Jane: That lower bound matches the upper bound for the uniform price auction under budget-free settings, which suggests that even without budgets, we already know how inefficient that format can be <ref:2609.39532#pg3>. It’s a good check on their math.

Lu: The paper also touches on position auctions where they show the PoA is at least two point one eight eight <ref:2609.39532#pg1>, which sets a baseline for how hard it is to achieve better outcomes there. It suggests that settling the exact price of anarchy for position auctions with subadditive valuations is still an open direction in this field <ref:2609.39532#pg2>.

Paper summary: Meng: So, what’s the big picture implication for us deploying these systems? We get a tighter mathematical handle on inefficiency, but we still have to worry about the complexity of solving that dual linear program <ref:2609.39532#pg1>.

Tom: Exactly. The framework itself is what matters here, though; it simplifies the process by reducing proving PoA guarantees to finding a feasible solution to that dual <ref:2609.39532#pg1>. It’s a tool for analysis, not necessarily a plug-and-play solver for every auction scenario.

Jane: So, to wrap up this discussion on the paper "Tight Liquid Welfare Guarantees for Auctions with Budgets," it really shows that we can use linear programming duality to get very tight performance guarantees when bidders have budgets <ref:2609.39532#pg1>. It shifts the focus from just measuring what happened to finding a mathematical structure that limits how bad things can possibly get.

Lu: The authors are building a toolkit for getting principled PoA bounds that extend to correlated equilibria and settings with incomplete information, which is pretty ambitious <ref:2609.39532#pg2>. They’re connecting smoothness notions in a way that makes the analysis much more robust across different auction formats <ref:2609.39532#pg1>.

Meng: I just hope that when we try to build these systems at scale, the computational cost of solving that dual program doesn't become prohibitive for real-time decisions <ref:2609.39532#pg1>. That’s the practical hurdle for me.

Tom: Yeah, that’s what they seem to be addressing by formulating it over a small number of per-bidder equilibrium statistics rather than the whole distribution <ref:2609.39532#pg2>. That keeps the complexity manageable for computation while still getting tight results.

Jane: So, for listeners who just want to know what this means, these results provide concrete numbers—like two point one eight eight or three point one four six—for various auction types with budgets <ref:2609.39532#pg3>. It gives us a solid mathematical floor on how bad the outcome can be compared to an ideal one <ref:2609.39532#pg1>.

Lu: The paper’s main contribution is showing that budget constraints introduce two major game-theoretic challenges, and they tackle them by using this specific LP framework <ref:2609.39532#pg2>. They show exactly where the efficiency guarantee breaks down compared to the budget-free world <ref:2609.39532#pg1>.

Meng: I guess for my team, it means we should test our current models against these known worst-case bounds derived from this paper <ref:2609.39532#pg1>. It’s a benchmark for our own system performance under budget pressure.

Tom: That sounds like a good next step. We can use these tight liquid welfare guarantees as a baseline to see how far we are from the theoretical limit <ref:2609.39532#pg1>.

Jane: And ultimately, this work suggests that the way we model efficiency in auctions needs to account for the affordability of actions, which is what they’ve done by introducing that novel smoothness notion <ref:2609.39532#pg2>. It’s a necessary refinement for modeling real-world scenarios.

Conclusion: Tom: So, we've been looking at this paper called "Tight Liquid Welfare Guarantees for Auctions with Budgets." It’s about figuring out exactly how much inefficiency you can expect when bidders have budgets in place during auctions.

Jane: Right. Basically, they developed a new mathematical way to prove performance guarantees for these auctions, using the dual of a linear program instead of just guessing the outcome.

Tom: They're trying to get tight bounds on the price of anarchy for coarse correlated equilibria, which is just a fancy way of saying how bad things can get compared to perfect efficiency.

Jane: The authors showed that this framework gives them really concrete numbers, like two point one eight eight for certain first-price auctions, and they found that second-price auction types don't get worse under budget constraints at all.

Tom: That's a big deal because it sets a real floor for how much you can expect to lose out when budgets are involved in the bidding process.

Jane: It shifts the focus from just looking at what happens to measuring exactly how bad things can be possible, which is what liquid welfare actually measures here.

Tom: This work means we have a better way to predict system performance under real-world budget constraints, not just theoretical perfect scenarios.

Jane: But the authors also pointed out that you still have to solve this dual linear program to get those specific numbers, which is the main technical hurdle for anyone trying to use it in production.

Tom: Yeah, so we're looking at a solid tool for analysis and setting benchmarks, but we still need a way to run that program fast enough when you're dealing with millions of bids.

Jane: Exactly. So next up, we’ll look at how this framework applies to different auction formats like second-price or all-pay auctions where the guarantees are actually different.

Centrum Wiskunde & Informatica (CWI) · University of Amsterdam · Technical University of Munich

cs.GT

Submitted: 2026-09-30

Updated: 2026-11-10

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 94/100

The gist: Tight liquid welfare guarantees for auctions with budgets via LP duality study the efficiency of auctions with budget-constrained bidders and derive tight price of anarchy bounds for coarse…

Key concepts

LP Duality Framework
This is a mathematical tool used to prove bounds. The authors reformulate the problem of finding PoA guarantees as solving the dual of a linear program (LP). This allows them to find tight lower bounds on welfare by solving a simpler, related optimization problem, making complex proofs tractable.
Budget-Feasible Semi-Smoothness
This is a specific mathematical condition introduced to handle budget constraints. It measures how much an outcome deviates from an equilibrium while ensuring that this deviation remains affordable for the bidders under their respective budget limitations. This concept links classical smoothness to the practical reality of having money constraints.
Price of Anarchy (PoA)
PoA measures the inefficiency in a system, specifically how much worse the outcome is compared to an ideal, perfectly coordinated outcome. In this context, it quantifies how much welfare is lost when bidders act selfishly under budget constraints in different auction settings.
Coarse Correlated Equilibria (CCE)
CCE refers to a set of outcomes where players coordinate only on coarse aspects of their strategies rather than every detail. The paper focuses on analyzing the PoA for CCEs, which is a practical way to study how bidders behave when they are not perfectly aligned but still make strategic decisions within their budget limits.

Terminology

Summary

Tight liquid welfare guarantees for auctions with budgets via LP duality study the efficiency of auctions with budget-constrained bidders and derive tight price of anarchy bounds for coarse correlated equilibria (CCE) <ref:2609. p. 0

Where the paper says it

Tight Liquid Welfare Guarantees for Auctions with Budgets via LP Duality Twan Kroll2 , Guido Sch¨afer1,2, and Artem Tsikiridis3 1Centrum Wiskunde & Informatica (CWI), The Netherlands 2University of Amsterdam, The Netherlands 3Technical University of Munich, Germany Abstract 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.

39532#pg2>.

Framework Development

The authors develop a general framework that reduces proving PoA guarantees to finding feasible solutions to the dual of a linear program <ref:2609.39532#pg2> 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 <ref:2609. p. 0

Where the paper says it

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.

39532#pg2> This approach enables simple and tight PoA analyses across a broad range of auction formats <ref:2609. p. 0
Where the paper says it

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.

39532#pg2>.

Key Contributions

The paper presents several key results, including the development of a linear programming framework that reduces proving PoA bounds for CCE of budget-constrained bidders to finding a feasible solution to the dual (Dual LP) of a linear program <ref:2609.39532#pg2> This framework yields tight or near-tight liquid welfare guarantees for a number of auction formats of practical significance <ref:2609. p. 1

Where the paper says it

1 converts any such dual solution into a PoA bound, for pay-your-bid as well as second-price-type payment rules. Our LP-duality framework in Section 3 yields tight or near-tight liquid welfare guarantees for a number of auction formats of practical significance.

39532#pg2>. Specifically, they recover the tight bound of [20] for first-price auctions (FPAs) with fractionally subadditive (XOS) valuations <ref:2609. p. 1
Where the paper says it

We first consider simultaneous auctions in Section 4. We recover the tight bound of [20] for first-price auctions (FPAs) with fractionally subadditive (XOS) valuations (Theorem 4.

39532#pg2> and derive new tight bounds for the second-price and all-pay variants <ref:2609. p. 1
Where the paper says it

1), prove the first upper bound for the more general class of subadditive valuations (Theorem 4. 2), and derive new tight bounds for the second-price and all-pay variants (Theorems 4.

39532#pg2>.

Smoothness and Duality

The technical machinery involves defining a notion of budget-feasible semi-smoothness (Definition 3.1) which captures affordability into the deviation, and a reduction (Theorem 3. p. 3

Where the paper says it

Our notion of budget-feasible semi-smoothness (Definition 3. 1) builds affordability into the deviation, and this is precisely what Theorem 3.

2) showing that classical, budget-free smoothness implies the new notion <ref:2609. p. 1
Where the paper says it

1), tailored to environments with budgets, together with a reduction (Theorem 3. 2) showing that classical, budget-free smoothness implies the new notion.

39532#pg2> The LP formulation uses per-bidder equilibrium statistics rather than the equilibrium distribution itself <ref:2609. p. 1
Where the paper says it

We develop a linear programming framework (Section 3) that reduces proving PoA bounds for CCE of budget-constrained bidders to finding a feasible solution to the dual (Dual LP) of a linear program (Primal LP). Unlike most previous duality-based approaches in the literature, which concern budget-free settings (see also Appendix A for a comparison of duality-based PoA frameworks), the variables of our LP formulation are not the equilibrium distribution itself, but rather a small number of per-bidder equilibrium statistics.

39532#pg2> The dual program is formulated to lower bound the liquid welfare LW(I, A) of any CCE A <ref:2609. p. 3
Where the paper says it

together with a partition of bidders based on whether their expected value at equilibrium reaches their budget. Altogether, the liquid welfare of any CCE is lower bounded by the optimum of a linear program and, by weak duality, any feasible solution of its dual corresponds to a PoA bound (Theorem 3.

39532#pg2>.

Auction Format Results

The framework yields tight bounds for various auction formats, including simultaneous first-price, second-price, and all-pay auctions <ref:2609.39532#pg2>. For simultaneous FPAs with XOS valuations, the PoA is at most 2. p. 1

Where the paper says it

We first consider simultaneous auctions in Section 4. We recover the tight bound of [20] for first-price auctions (FPAs) with fractionally subadditive (XOS) valuations (Theorem 4.

188 <ref:2609. p. 0
Where the paper says it

, a single bid per item, click, or unit, and allocation and payments are determined separately per item or unit. arXiv:2609.

p. 0
Where the paper says it

, a single bid per item, click, or unit, and allocation and payments are determined separately per item or unit. arXiv:2609.

p. 0
Where the paper says it

, a single bid per item, click, or unit, and allocation and payments are determined separately per item or unit. arXiv:2609.

p. 0
Where the paper says it

, a single bid per item, click, or unit, and allocation and payments are determined separately per item or unit. arXiv:2609.

p. 0
Where the paper says it

, a single bid per item, click, or unit, and allocation and payments are determined separately per item or unit. arXiv:2609.

p. 0
Where the paper says it

, a single bid per item, click, or unit, and allocation and payments are determined separately per item or unit. arXiv:2609.

39532#pg2> For simultaneous FPAs with restricted uniform bidding interfaces, the PoA is upper bounded by 2. p. 0
Where the paper says it

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.

188 <ref:2609.39532#pg2>. In multi-unit auctions, the PoA of CCEs in discriminatory price multi-unit auctions with budgets is at most 2. p. 0
Where the paper says it

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.

188 <ref:2609.39532#pg2> and for the uniform price auction under aggregate NOB, it is at most −W−1(−e−2) ≈ 3. p. 0
Where the paper says it

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.

146 <ref:2609. p. 0
Where the paper says it

, a single bid per item, click, or unit, and allocation and payments are determined separately per item or unit. arXiv:2609.

p. 0
Where the paper says it

, a single bid per item, click, or unit, and allocation and payments are determined separately per item or unit. arXiv:2609.

39532#pg2>.

Conclusion on Guarantees

The results reveal a dichotomy where second-price-type formats do not worsen under budget constraints, whereas those of the pay-your-bid formats provably do <ref:2609.39532#pg2> The best possible guarantee rises from e e−1 ≈ 1. p. 2

Where the paper says it

We complement our upper bounds with a collection of matching lower bound constructions. These are established for the weakest solution concept for which they are possible, i.

58 [19, 63] to 2.188 [20] for first-price, and from at most 2 [63] to 3 (Theorem 4. p. 2
Where the paper says it

Simultaneous item auctions First-price XOS 2. 188 ∗ [20] 2.

8) for all-pay <ref:2609. p. 0
Where the paper says it

, a single bid per item, click, or unit, and allocation and payments are determined separately per item or unit. arXiv:2609.

39532#pg2>. The PYB bound max(1,λ+µ)λ strictly exceeds its budget-free counterpart max(1,µ)λ whenever λ + µ > 1 <ref:2609. p. 9
Where the paper says it

The dual LP is as follows: DP := max X i∈N1 γivˆi(χ ∗ i ) + λ X i∈N2 δivˆi(χ ∗ i ) subject to γi + ηi + τ ≤ 1 ∀i ∈ N1 δi + ηi + τ ≤ 1 ∀i ∈ N2 0 ≤ ηi + κi ∀i ∈ N1 0 ≤ δi + ηi + κi ∀i ∈ N2 µδi ≤ θ ∀i ∈ N2 θ + κi ≤ τ ∀i ∈ N γi , δj , ηk, κk, τ, θ ≥ 0 ∀i ∈ N1, j ∈ N2, k ∈ N. (Dual LP) For PYB settings, because Wi = Pi for all i ∈ N in the primal, it is important to note that κi becomes a free variable in the dual and is not constrained to κi ≥ 0.

39532#pg2>.

Lower Bound Constructions

The authors complement upper bounds with matching lower bound constructions established for the weakest solution concept for which they are possible <ref:2609.39532#pg2> For instance, the MNE-POA of budget-constrained simultaneous FPAs with restricted uniform bidding interface is at least 2. p. 1

Where the paper says it

2), and derive new tight bounds for the second-price and all-pay variants (Theorems 4. We also obtain the first bounds for simultaneous FPAs under the restricted uniform bidding interface studied in [26, 53] (Theorem 4.

188 <ref:2609.39532#pg2> and the PoA of mixed Nash equilibria of simultaneous all-pay auctions with budgets where bidders have XOS valuations is at least 3 <ref:2609. p. 4
Where the paper says it

[2] for a survey. Tight PoA bounds for value maximizers are known for pure Nash equilibria of the second-price auction [1], the VCG mechanism [26], and the GSP auction [27], as well as for simultaneous first-price auctions at pure and mixed Nash equilibria [28, 52, 53]; under the restricted uniform bidding interface, the PoA for budgeted value maximizers is unbounded [53], in contrast to our tight bound for budgeted utility maximizers (Theorem 4.

39532#pg2>. The lower bound for the uniform price auction under budget-free settings matches its upper bound, settling the inefficiency of that format even without budgets <ref:2609. p. 2
Where the paper says it

4 and the discussion in Appendix C. 3), our lower bound for the uniform price auction is budget-free and matches our upper bound, thereby settling the inefficiency of the format even without budgets.

39532#pg2>.

Further Analysis

The analysis extends to position auctions, showing that the PoA of coarse correlated equilibria of GFP auctions with budgets is at most 2.188 <ref:2609.39532#pg2> and at least 2. p. 8

Where the paper says it

Let A ∈ CCE(I) be a coarse correlated equilibrium and χ ∗ an optimal liquid welfare allocation. We partition the bidders in N into two sets N1 and N2, based on whether their expected value at the equilibrium A is at least their budget; more formally, we define N1 := {i ∈ N | Ea∼A[vi(Xi(a))] ≥ Bi} and N2 := N \ N1.

188 <ref:2609.39532#pg2>. For the GSP auction under aggregate NOB, the PoA is at least −W−1(−e−2) ≈ 3. p. 4
Where the paper says it

[2] for a survey. Tight PoA bounds for value maximizers are known for pure Nash equilibria of the second-price auction [1], the VCG mechanism [26], and the GSP auction [27], as well as for simultaneous first-price auctions at pure and mixed Nash equilibria [28, 52, 53]; under the restricted uniform bidding interface, the PoA for budgeted value maximizers is unbounded [53], in contrast to our tight bound for budgeted utility maximizers (Theorem 4.

146 <ref:2609.39532#pg2>. The analysis also shows that for budget-free GSP auctions, the PoA is at least 2 <ref:2609. p. 3
Where the paper says it

For position auctions with budgets, equilibrium existence was studied in [4, 29] and the PoA for pure Nash equilibria was shown by Voudouris [65] to be exactly 2 for GFP, GSP and VCG. Most work on the price of anarchy of simple auctions has been carried out for bidders who are not budget-constrained.

39532#pg2>. This work suggests that settling the exact PoA of the GSP and of SFPAs with subadditive valuations is a fascinating open direction <ref:2609. p. 3
Where the paper says it

For position auctions with budgets, equilibrium existence was studied in [4, 29] and the PoA for pure Nash equilibria was shown by Voudouris [65] to be exactly 2 for GFP, GSP and VCG. Most work on the price of anarchy of simple auctions has been carried out for bidders who are not budget-constrained.

39532#pg2>.

Technical Comparison

The LP duality framework differs substantially from previous approaches by using aggregate per-bidder equilibrium statistics instead of the CCE distribution itself <ref:2609.39532#pg2> This formulation unifies the analysis for first-price, all-pay, and second-price payment rules through a single coupling constraint <ref:2609. p. 1

Where the paper says it

2) showing that classical, budget-free smoothness implies the new notion. 1 converts any such dual solution into a PoA bound, for pay-your-bid as well as second-price-type payment rules.

39532#pg2>. The key technical ingredient is a reduction showing that smoothness can be achieved by deviations that remain budget-feasible against every action profile of the opponents <ref:2609. p. 3
Where the paper says it

A reduction. The obstacle that separates budget-constrained from budget-free mechanisms is that the deviation at the heart of every smoothness proof may be unaffordable against some behavior of the opponents.

39532#pg2>.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Development of a linear programming framework for budget-constrained auctions allows AI systems to derive tight price of anarchy bounds by reducing proving PoA guarantees to finding feasible solutions to a dual linear program over equilibrium statistics.

  2. The framework enables the derivation of liquid welfare guarantees for various auction formats, including simultaneous first-price, second-price, and all-pay auctions under budget constraints.

  3. AI systems can be equipped with the ability to analyze efficiency in generalized games where action feasibility depends on induced payments by tracking per-bidder equilibrium statistics like expected payment and willingness to pay.

  4. The system can leverage the new notion of budget feasible semi-smoothness, which is tailored for budget-constrained environments, to derive PoA bounds through a reduction from classical smoothness notions.

  5. The framework provides upper bounds on the Price of Anarchy for coarse correlated equilibria (CCE) in various auction settings, such as simultaneous first-price auctions with subadditive valuations, yielding bounds like 2.188 or 3.146.

  6. AI systems can distinguish between the performance guarantees of second-price-type formats and pay-your-bid formats under budget constraints, revealing that the latter provably worsen under budgets while the former do not.

  7. The system can be used to analyze multi-unit auctions (Discriminatory Price and Uniform Price) with budgets, providing tight PoA bounds such as 2.188 for discriminatory auctions and 3.146 for uniform price auctions under aggregate no-overbidding.

  8. AI systems can assess the efficiency of position auctions (GFP and GSP) with budgets, establishing upper bounds of 2.188 and lower bounds matching these values in certain settings under aggregate no-overbidding.

  9. The system can identify specific conditions, such as when lambda plus mu is greater than one, where the PYB bound strictly exceeds its budget-free counterpart to quantify the impact of budget constraints on efficiency guarantees.

Abstract

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 bounding the optimal value 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 first-price auctions in which every bidder scales her values by a single bid multiplier (Deng et al., 2021), discriminatory and uniform price multi-unit auctions, and generalized first-price and second-price position auctions. Beyond budget-constrained settings, we also prove tight bounds for the budget-free uniform price auction and the budget-free generalized second-price auction.

Sources

Related papers