Source-linked AI summary
Price of Anarchy for Greedy Auctions
Brendan Lucier, Allan Borodin
TL;DR
The paper asks whether computationally efficient greedy allocation algorithms can be implemented as mechanisms that preserve approximation performance at equilibrium. The paper analyzes first-price and critical-price mechanisms built from greedy allocation rules using equilibrium price-of-anarchy arguments. For a greedy c-approximate allocation rule, the pay-your-bid auction has a Bayes-Nash Price of Anarchy of at most c + O(c²/e^c).
Problem
The paper asks whether computationally efficient greedy allocation algorithms can be implemented as mechanisms that preserve approximation performance at equilibrium.
Source: §1 · p. 2, §6 · p. 26Method
The paper analyzes first-price and critical-price mechanisms built from greedy allocation rules using equilibrium price-of-anarchy arguments.
Source: §1 · p. 2, §1.1 · p. 3Results
For a greedy c-approximate allocation rule, the pay-your-bid auction has a Bayes-Nash Price of Anarchy of at most c + O(c²/e^c).
Source: §1.1 · p. 3Takeaways & Limitations
Greedy algorithms can be designed for computational performance and paired with pricing schemes that preserve close approximation guarantees at equilibrium.
Source: §1 · p. 2The results concern monotone greedy algorithms; the correlated-equilibrium first-price bound requires fixed-order greedy allocation and is 4c, compared with c + o(1) for independent types.
Source: §6 · p. 26
Abstract
from arXiv · showhide
We consider auctions in which greedy algorithms, paired with first-price or critical-price payment rules, are used to resolve multi-parameter combinatorial allocation problems. We study the price of anarchy for social welfare in such auctions. We show for a variety of equilibrium concepts, including Bayes-Nash equilibrium and correlated equilibrium, the resulting price of anarchy bound is close to the approximation factor of the underlying greedy algorithm.
1 Introduction
The paper asks how to retain strong social-welfare approximations when computationally efficient greedy allocation rules are used in strategic auctions. It shows that first-price and critical-price mechanisms can have price-of-anarchy bounds close to the underlying greedy algorithm’s approximation factor, across several equilibrium settings.
1 Introduction
- Exact welfare maximization can be computationally intractable or communication-intensive, while greedy algorithms are efficient and intuitive but generally are not dominant-strategy truthful.The paper studies equilibrium performance as an alternative to requiring dominant-strategy truthfulness.Source: §1 · pp. 1–2
1.1 Our Results
- Greedy allocation rules can yield mechanisms whose price-of-anarchy bounds closely match their approximation factors across several equilibrium concepts.The analysis covers pure and mixed Nash, Bayes-Nash, and Bayesian equilibria with correlated types.Source: §1 · p. 2, §1.1 · p. 3
- A greedy c-approximate allocation rule with pay-your-bid payments has Bayes-Nash price of anarchy at most c + O(c^2/e^c), with bound c at pure Nash equilibrium.The mechanisms are prior-free, and the analysis also extends to coarse correlated equilibria.Source: §1.1 · p. 3
- For arbitrarily correlated agent types, a weaker O(c) bound holds for non-adaptive greedy algorithms, so equilibrium performance asymptotically matches the allocation algorithm.The first-price correlated-types analysis uses a fixed-order greedy algorithm and a deviation that bids half of true value on every set.Source: §1.1 · p. 3
- With critical-price payments and no overbidding, a greedy c-approximate allocation rule has Bayes-Nash price of anarchy at most c + 1.The paper shows that the extra +1 term is essentially necessary for large c.Source: §1.1 · pp. 3–4
1.2 Related Work
- Strong loser-independence, a strengthening introduced to simplify proofs, is the basic property of greedy algorithms used in this paper; loser-independence is conceptually related to smoothness.Source: §1.2 · p. 4
2 Preliminaries
The preliminaries define the feasible allocation and auction setting, the equilibrium concepts used to evaluate welfare, and the greedy allocation rules studied. They also give examples of allocation problems where greedy algorithms provide approximation guarantees.
2.1 Feasible Allocation Problems
- Feasible allocations determine which bundles agents can receive; the objective is to maximize the sum of their values, and critical values measure the minimum bid needed to win a set.The setting assumes monotone, normalized valuations and separable feasibility constraints.Source: §2.1 · p. 5
2.2 Mechanisms
- Mechanisms combine an allocation rule with payments: first-price charges the winner’s bid, while critical-price charges the minimum bid needed to win.Declarations need not equal agents’ true valuations.Source: §2.2 · p. 6
2.3 Equilibria of One-shot Auctions
- The paper evaluates welfare at Nash and Bayesian Nash equilibria, including correlated-type Bayesian settings, against the optimal expected welfare.The standard Bayesian setting assumes independently distributed types; the paper also defines correlated-type variants.Source: §2.3 · pp. 6–7
2.4 Greedy Allocation Rules
- Non-adaptive greedy allocation algorithms use a single priority function throughout execution, while adaptive greedy allocation algorithms can change their priority function on each iteration, depending on the partial allocation formed on previous iterations.The framework is motivated by Borodin, Nielsen and Rackoff, Mu’alem and Nisan, and Borodin and Lucier.Source: §2.4 · p. 7
2.5 Applications
- Applications include combinatorial auctions with a 2m-approximation, cardinality-restricted auctions, unsplittable flow, convex bundle auctions, and unit-job scheduling.The cited guarantees include O(m^(1/(B−1))) for unsplittable flow when B > 1 and O(R^(4/3)) for convex bundle auctions; alternative algorithms improve special cases such as rectangles.Source: §2.5 · p. 8
3 Strong Loser-Independence
Strong loser-independence extends loser-independence to multi-parameter settings and simultaneous changes to losing bids. The paper uses this algorithmic property to relate equilibrium welfare to optimal welfare through critical values.
3 Strong Loser-Independence
- Strong loser-independence extends loser-independence to multi-parameter settings by tracking losing bids, and requires invariance when multiple agents change such bids simultaneously.The definition compares outcomes under the original profile and profiles where one agent changes a declaration.Source: §3 · p. 9
- Every adaptive greedy algorithm is strongly loser-independent; monotone adaptive greedy algorithms are also component-wise monotone.Source: §3 · pp. 9–10
- A c-approximate strongly loser-independent algorithm also approximates the sum of critical values for an optimal allocation profile.The proof perturbs declarations toward critical values and applies the algorithm’s approximation guarantee.Source: §3 · pp. 10–11
3.1 Applying Strong Loser Independence
- The analysis combines the equilibrium condition with the critical-value bound to relate optimal welfare to equilibrium welfare and the welfare of price-setting agents.For pure Nash equilibrium results, no overbidding removes the need for monotonicity; other results require it.Source: §3.1 · p. 11
- Unlike smoothness [32], this approach assumes an equilibrium bid profile; that distinction allows a pure first-price price of anarchy of c, a bound not available for Bayesian price of anarchy.Source: §3.1 · p. 11
4 First-Price Mechanisms
This section studies equilibrium inefficiency in first-price mechanisms based on strongly loser-independent greedy allocation rules, covering pure, Bayesian, and correlated types; it also notes that overbidding on a set an agent may win is weakly dominated. It shows that the Bayesian bound’s loss can be necessary and describes the correlated-types proof’s use of a greedy-allocation comparison and a lemma applied from arbitrary strategy profiles to an equilibrium profile.
4 First-Price Mechanisms
- Under a monotone strongly loser-independent allocation rule, overbidding on a potentially won set is weakly dominated, so equilibrium bidders do not overbid on sets they win with positive probability.The dominance is strict when the agent wins an overbid set with positive probability.Source: §4 · p. 12
4.1 Pure Nash Equilibria
- A c-approximate monotone strongly loser-independent allocation rule yields a first-price mechanism with price of anarchy at most c at pure Nash equilibrium.Some instances do not guarantee that the mechanism has a pure Nash equilibrium.Source: §4.1 · p. 13
4.2 Bayes-Nash Equilibria
- The Bayesian price of anarchy is at most c/(1−e^−c) for independent type distributions, and can be at least c + c^2/e^(4c) for some mixed equilibria.The same upper bound applies to coarse correlated equilibrium; the lower-bound construction uses a non-adaptive greedy c-approximation for c ≥ 2.Source: §4.2 · pp. 14, 17
4.3 Correlated Types
- For any type distribution, a c-approximate non-adaptive greedy algorithm gives correlated Bayesian price of anarchy at most 4c.The analysis uses a deviation that bids half of an agent’s true value on every set and requires a fixed-order greedy algorithm.Source: §4.3 · pp. 19–20
- For each agent, the proof compares the greedy allocation on an input with that agent’s value bids halved against the agent’s allocation in the optimum.If the stated threshold condition fails, non-adaptivity and the greedy guarantee imply v_i(x_i) ≥ 1/c · v_i(y_i).Source: §4.3 · p. 20
- The proof’s concluding inequality uses the first-price payment scheme.Source: §4.3 · p. 20
- Theorem 4.10 follows from Lemma 4.11, which holds for all strategy profiles, by taking an equilibrium profile under type distribution F.Source: §4.3 · pp. 20–21
5 Critical-Price Mechanisms
Critical-price mechanisms built from suitable greedy allocation rules have welfare guarantees near the algorithms’ approximation factors, under specified equilibrium and bidding assumptions. The section also gives a restricted-expressiveness variant that removes the no-overbidding assumption and describes a binary-search method for calculating critical prices.
5 Critical-Price Mechanisms
- M2(A) applies an arbitrary monotone strongly loser-independent algorithm to declarations, allocates its output, and charges each agent the critical value of the set received.The critical value is computed through additional calls to the allocation algorithm.Source: §5 · p. 21
5.1 Bayes-Nash Equilibria
- A c-approximate monotone strongly loser-independent rule yields a (c+1)-approximation to expected optimal welfare at no-overbidding Bayes-Nash equilibria of M2(A).The same price-of-anarchy bound extends to coarse correlated equilibrium.Source: §5.1 · pp. 22–23
- For every c ≥1, an example has algorithm approximation factor c + 1 c and pure price of anarchy c + 1, showing the bound’s gap is necessary for large c.The authors conclude the Theorem 5.1 bound cannot generally be improved beyond c + 1 − O(1 c).Source: §5.1 · p. 23
5.2 Correlated Types
- With arbitrary type distributions, a c-approximate non-adaptive greedy algorithm and no-overbidding yield correlated Bayesian price of anarchy at most 4c.The independent-types result does not require the non-adaptive-greedy condition stated for this bound.Source: §5.2 · p. 23
5.3 Overbidding and Restricted Expressiveness
- In mixed equilibria, an agent may strictly improve utility by overbidding, motivating a modified mechanism that makes overbidding dominated and preserves the (c + 1)-approximation guarantee.For the modified M∗2(A), truthful-valued single-minded declarations are undominated, and the Bayes-Nash welfare guarantee no longer assumes no-overbidding.Source: §5.3 · pp. 24–25
5.4 Calculating Critical Prices
- Critical prices for allocated sets can be approximated within ǫ using binary search, with O(n log(vmax/ǫ)) invocations of the allocation algorithm for all agents.Monotonicity lets each query test whether a declaration at value z still wins the allocated set.Source: §5.4 · p. 26
6 Conclusion and open problems
The paper shows that approximation guarantees for a broad class of greedy allocation algorithms can become closely matching price-of-anarchy bounds for mechanisms. The results cover Bayesian equilibria, but their scope excludes some algorithms commonly considered greedy and leaves extensions open.
6 Conclusion and open problems
- For a wide class of greedy algorithms, approximation bounds translate into closely matching price-of-anarchy bounds, including for Bayesian equilibria and some repeated auctions.The paper contrasts this with incentive compatibility, where approximation bounds generally are not expected to be preserved.Source: §6 · p. 26
- The results are motivated by monotone greedy algorithms and generally apply to monotone strongly loser-independent algorithms, but some correlated-equilibrium results require fixed-order greedy algorithms.The first-price correlated-equilibrium bound is 4c, unlike the c + o(1) result for independent agent distributions.Source: §6 · p. 26
- The framework excludes some algorithms commonly called greedy, including item-by-item allocation to agents with the highest marginal gains for monotone submodular valuations.The authors also raise extensions to broader greedy rules, non-monotone auctions, and interdependent valuations.Source: §6 · pp. 26–27
A Existence of Pure Nash Equilibria
The appendix gives a first-price mechanism instance with no pure Nash equilibrium, even when values and payments are discretized. The example also rules out a (1 + ǫ)-approximate pure equilibrium for small ǫ.
A Existence of Pure Nash Equilibria
- The M1(A) example has no pure Nash equilibrium despite valuations and payments being multiples of arbitrarily small ǫ > 0, and has no (1 + ǫ)-approximate pure Nash equilibrium for small ǫ > 0.Source: A Existence of Pure Nash Equilibria · p. 29
B Combining Mechanisms
Combining a greedy allocation rule with a rule that allocates all objects to one bidder can yield a good approximation algorithm but poor equilibrium welfare. The section notes a randomized alternative that may work when the rules operate on disjoint declaration spaces.
B Combining Mechanisms
- Amax is O(√m)-approximate, yet its first-price and critical-price mechanisms have price of anarchy Ω(m) in the constructed instance.As ǫ →0, the equilibrium welfare is 1 while optimal welfare is m.Source: B Combining Mechanisms · p. 30
- Randomly choosing between separate mechanisms can work well when the allocation rules operate on disjoint parts of declaration space, letting agents optimize bids separately.Source: B Combining Mechanisms · p. 30