PaperlayerView exact revision on arXiv

Source-linked AI summary

Simultaneous Auctions are (almost) Efficient

Michal Feldman, Hu Fu, Nick Gravin, Brendan Lucier

arXiv:1209.4703v1cs.GT

TL;DR

Simultaneous item auctions simplify bidding on complex preferences, but their equilibrium efficiency is a central question. This paper analyzes Bayesian Nash equilibria for subadditive valuations and proves constant welfare guarantees for first- and second-price auctions. The second-price guarantee requires no-overbidding.

  • Problem

    Simultaneous item auctions simplify bidding on complex preferences, but it is important to determine how their outcomes compare with socially optimal allocation.

    Source: §1 · p. 1

  • Method

    The analysis constructs a single-player bidding strategy against price distributions and uses randomized equilibrium deviations based on virtual opponent types.

    Source: §1 · p. 5

  • Results

    First-price BNE outcomes achieve at least half of optimal welfare, while second-price outcomes achieve at least one quarter under no-overbidding.

    Source: §1 · p. 3

  • Takeaways & Limitations

    For subadditive valuations, the paper establishes constant Bayesian price-of-anarchy bounds for both auction formats.

    Source: §1 · p. 3

    The second-price guarantee is conditional on no-overbidding; strong no-overbidding is meaningless for complementary valuations because it precludes item bidding.

    Source: §1 · p. 3

Abstract

from arXiv · show

Simultaneous item auctions are simple procedures for allocating items to bidders with potentially complex preferences over different item sets. In a simultaneous auction, every bidder submits bids on all items simultaneously. The allocation and prices are then resolved for each item separately, based solely on the bids submitted on that item. Such procedures occur in practice (e.g. eBay) but are not truthful. We study the efficiency of Bayesian Nash equilibrium (BNE) outcomes of simultaneous first- and second-price auctions when bidders have complement-free (a.k.a. subadditive) valuations. We show that the expected social welfare of any BNE is at least 1/2 of the optimal social welfare in the case of first-price auctions, and at least 1/4 in the case of second-price auctions. These results improve upon the previously-known logarithmic bounds, which were established by [Hassidim, Kaplan, Mansour and Nisan '11] for first-price auctions and by [Bhawalkar and Roughgarden '11] for second-price auctions.

1 Introduction

This paper studies how efficiently simultaneous item auctions allocate goods at Bayesian Nash equilibrium when bidders have complex valuations. It establishes constant welfare guarantees for subadditive valuations, with a no-overbidding condition for second-price auctions.

1 Introduction

  • For complement valuations, the price of anarchy can grow as Ω(√m) in first-price auctions, with the same lower bound extending to second-price auctions under weak no-overbidding.Strong no-overbidding is meaningless with complements because it precludes item bidding altogether.Source: §1 · p. 3
  • For first- and second-price auctions, the paper establishes constant Bayesian price-of-anarchy bounds when valuations are complement-free, or subadditive.The introduction presents complements as the barrier to constant bounds.Source: §1 · p. 3
  • First-price BNE outcomes achieve at least half of optimal social welfare for subadditive valuations.This improves on the previously best-known O(log n) bound.Source: §1 · p. 3
  • The second-price guarantee requires no-overbidding because unrestricted equilibria can involve players overreporting values and inducing others to bid nothing.The strong condition caps each agent’s bids on every item set by that set’s value.Source: §1 · p. 3
  • Second-price auctions have Bayesian price of anarchy at most 4 under strong no-overbidding for subadditive valuations.The same bound extends to weakly no-overbidding agents.Source: §1 · pp. 3–4
  • The weak no-overbidding condition permits richer equilibrium behavior than the strong condition, but also introduces new possible deviations.The two assumptions’ BNE outcomes are incomparable.Source: §1 · p. 4
  • Subadditive valuations are more expressive than XOS valuations, and lack the natural additive bids available for targeting a set under XOS valuations.Earlier constant bounds covered XOS valuations, while subadditive bounds were only logarithmic; the paper’s approach also falls outside the smoothness framework because its strategies depend on opponents’ equilibrium strategies.Source: §1 · pp. 4–5
  • The analysis uses a single-player bidding strategy against price distributions, then applies randomized deviations based on opponents’ virtual types to bound equilibrium welfare.At BNE, agents cannot benefit from these deviations, which yields a constant-factor welfare guarantee.Source: §1 · p. 5

2 Preliminaries

The section defines simultaneous item auctions and Bayesian equilibrium analysis, then sets out the subadditive valuation scope and second-price no-overbidding assumptions.

2.1 Auctions and Equilibria

  • Items are allocated separately by highest bids; winners pay their own bids in first-price auctions or the second-highest bid in second-price auctions.The section defines welfare through bidders’ allocated bundles and evaluates outcomes using Bayesian price of anarchy, the worst-case ratio over equilibria.Source: §2.1 · pp. 5–6, A Single Bidder’s Perspective on Bidding · p. 7

A Single Bidder’s Perspective on Bidding

  • A bidder’s perceived price vector consists of the highest competing bid on each item and determines which items a bid wins.Strategies map each valuation to a possibly randomized bid vector, and BNE requires that no type benefits from unilaterally changing strategy.Source: A Single Bidder’s Perspective on Bidding · p. 6

2.2 Subadditive Valuations

  • The analysis targets subadditive valuations, for which prior approaches through XOS valuations incur a logarithmic gap, motivating a proof technique that avoids that route.Subadditive valuations include more restrictive complement-free classes such as submodular and gross-substitute valuations.Source: §2.2 · p. 7

2.3 Overbidding

  • Second-price bounds require no-overbidding restrictions: strong no-overbidding limits bids to the valuation, while weak no-overbidding bounds expected bids by expected value at given price distributions.Strong no-overbidding ensures nonnegative utility at any prices and is described as a strong risk-aversion assumption.Source: §2.3 · p. 8

3 Bidding Strategies Under Uncertain Prices

The section develops bids that perform well against uncertain item prices for subadditive valuations. It then adapts the approach to satisfy strong no-overbidding.

3 Bidding Strategies Under Uncertain Prices

  • A bid drawn from the price distribution yields, in expectation, the desired utility-versus-price inequality, so some bid in its support achieves it.The argument uses subadditivity to relate the value of winning against one price vector to the value against another.Source: §3 · pp. 8–9

3.1 No-Overbidding Strategies Under Uncertain Prices

  • For second-price settings, a strongly no-overbidding bid against uncertain prices exists for every subadditive valuation.The construction truncates prices on a maximal set whose value does not exceed its total price, producing truncated price vectors dominated by the valuation.Source: §3.1 · pp. 9–10

4 Price of Anarchy for First Price Auctions

The proof applies bidding strategies against prices induced by other bidders’ equilibrium bids on items in an optimal allocation. It establishes a constant price-of-anarchy bound for first-price auctions with subadditive bidders, under independent valuations.

4 Price of Anarchy for First Price Auctions

  • 2 is the upper bound on Bayesian price of anarchy in simultaneous first-price auctions with subadditive bidders.Equivalently, every BNE achieves at least half the optimal expected welfare.Source: §4 · p. 10
  • The proof considers competing bids on each bidder’s bundle in an optimal allocation and uses a deviation against their induced price distribution.The bid is selected independently of the optimal allocation partition, enabling the equilibrium inequalities to be summed across bidders.Source: §4 · pp. 10–11
  • The bound does not extend to correlated valuations; the paper gives a polynomial lower bound of Ω(n^(1/6)) for that setting.The construction draws heavily on a lower bound for second-price auctions.Source: §4 · p. 11

5 Price of Anarchy for Second Price Auctions

For simultaneous second-price auctions, the paper bounds Bayesian price of anarchy under strong or weak no-overbidding. It also gives a weakly no-overbidding BNE example whose inefficiency exceeds 2.

5 Price of Anarchy for Second Price Auctions

  • 4 is the upper bound on Bayesian price of anarchy for subadditive bidders in simultaneous second-price auctions under strong or weak no-overbidding.The theorem assumes bidders’ valuations are independently drawn.Source: §5 · p. 12
  • The gap above 2 also occurs under weak no-overbidding, unlike the earlier cited example, whose strategy profile is not a BNE under that weaker notion.The example uses symmetric valuations over two three-item sets and parameters a = 0.06 and b = 0.85.Source: §5 · pp. 12–13
  • For the specified parameter values, bidding true additive values on each bidder’s Si and zero elsewhere is a Bayesian equilibrium with weakly no-overbidding; welfare is 1.94 versus 4, giving Bayesian price of anarchy 4/1.94 > 2.061.The alternative allocation gives S2 to bidder 1 and S1 to bidder 2, yielding utility 2 for each.Source: §5 · p. 13

A A Proof of Example 1

The proof reduces the possible deviations to a small set and shows that any profitable remaining deviation violates weak no-overbidding. Thus the example’s strategy profile is a Bayesian equilibrium under that restriction.

A A Proof of Example 1

  • Only pure deviations by bidder 1 need consideration, and it suffices to check bids 0, a, or b on items in S2 while bidding 0 on S1.The restriction applies to every bid in the strategy’s support; bidder 1 values either S1 or S2, but not both.Source: A A Proof of Example 1 · p. 14
  • The table enumerates possible bids and their expected values, payments, and bids, showing the quantities used to compare deviations with the current strategy.It gives parametric expressions and values for a = 0.06 and b = 0.85.Source: A A Proof of Example 1 · p. 14
  • The profile is a Bayesian equilibrium with weakly no-overbidding bidders: the two excluded deviations violate the restriction, and every other deviation gives lower expected utility.The current expected utility is 2a + b = 0.97.Source: A A Proof of Example 1 · p. 15

B A Lower Bound for Correlated Valuations

The section constructs a correlated-valuation setting in which even unit-demand valuations yield a polynomial lower bound on the Bayesian price of anarchy. Its argument bounds type-I bidders’ reserve-item wins and compares equilibrium welfare with optimal welfare.

B A Lower Bound for Correlated Valuations

  • Ω(n^1/6) is a lower bound on the Bayesian price of anarchy for first-price auctions with correlated subadditive valuations, even when valuations are unit demand.The construction draws heavily on a lower bound for second-price auctions by Bhawalkar and Roughgarden (2011).Source: B A Lower Bound for Correlated… · p. 15
  • The construction has 3n players arranged in triples of one type-I and two type-II players, and partitions items into a common pool, reserve items, and matched mock pools.Source: B A Lower Bound for Correlated… · p. 15
  • Type-II bidders bid n^-1/6 on their reserve item in the typical case and bid zero on all items in the atypical case.Bidding more risks negative utility, while bidding less lets the other type-II bidder in the triple obtain positive utility.Source: B A Lower Bound for Correlated… · p. 15
  • A type-I player cannot distinguish typical from atypical cases and must bid at least n^-1/6 on the reserve item to win it typically; equilibrium limits such bids to k ≤ n^1/3 items.If he bids that amount on k items, he wins all k in the atypical profile and pays at least k n^-1/6 there; expected payment across cases is at least pkn^-1/6 = kn^-1/3, which exceeds 1 if k > n^1/3.Source: B A Lower Bound for Correlated… · p. 16
  • The typical-case welfare bound accounts for type-II bidders, type-I bidders winning reserve items, and type-I bidders winning common-pool items; since optimal welfare is at least n in each case, the price of anarchy is at least Ω(n^1/6).The bound uses the listed components of typical-case welfare and the stated lower bound on optimal welfare.Source: B A Lower Bound for Correlated… · p. 16

C No Overbidding: a Discussion

No-overbidding restrictions differ in how they constrain bidders’ strategies: strong no-overbidding protects against arbitrary opponent behavior, while weak no-overbidding relies on expected behavior. The discussion notes both that restrictions can exclude best responses and that undominated strategies alone do not ensure efficient outcomes.

C No Overbidding: a Discussion

  • Strong no-overbidding guarantees nonnegative utility regardless of opponents’ behavior, whereas weak no-overbidding guarantees it only when opponents behave as expected.Under the weak condition, nonnegative utility is still guaranteed if the auction changes ex post from second-price to first-price.Source: C No Overbidding: a Discussion · p. 16
  • With an additive opponent truthfully bidding values 0.9 and 1.1 across two items, a unit-demand bidder bidding between 0.9 and 1 on each wins one and pays 0.9, satisfying weak but not strong no-overbidding.Strong no-overbidding would require indicating value of at least 1.8 for both items, exceeding the bidder’s true value of 1.Source: C No Overbidding: a Discussion · p. 16
  • The example shows that weak no-overbidding can still exclude utility-improving deviations, while the preceding example has a best response allowed by weak but excluded by strong no-overbidding.The authors identify finding a weaker restriction that never excludes best responses while preserving a constant bound as future work.Source: C No Overbidding: a Discussion · p. 17
  • Undominated strategies alone do not ensure good welfare: a second-price equilibrium in undominated strategies has welfare 2 − ε versus an optimum of roughly n.The discussion contrasts this with Vickrey and GSP settings where overbidding is weakly dominated.Source: C No Overbidding: a Discussion · p. 17

D Existence of Equilibria

The paper establishes equilibrium existence for a bounded, discretized auction game but explains why that argument does not extend automatically to continuous bids and values. For simultaneous auctions with subadditive valuations, prior work does not establish tie-breaking rules that always guarantee BNE existence, so the results are scoped most directly to discrete approximations.

D Existence of Equilibria

  • When values and bids are bounded and discretized, a Bayes-Nash equilibrium exists because the set of bidding functions is finite and Nash’s existence result applies.The Bayesian game is represented as a normal-form game in which each player selects a bidding function ex ante.Source: D Existence of Equilibria · p. 17
  • Equilibria in discretized games do not necessarily imply an equilibrium in the continuous limit; discontinuous utilities can prevent equilibrium existence.In the single-item first-price example, no fixed bid just above 1/2 is optimal for the bidder with value 1.Source: D Existence of Equilibria · p. 18
  • For complete-information mixed Nash equilibria, an appropriate tie-breaking rule can yield existence, but the rule may depend on agents’ types.The cited result concerns complete-information games.Source: D Existence of Equilibria · p. 18
  • For simultaneous item auctions with subadditive valuations, prior work does not establish tie-breaking rules that always ensure BNE existence; general existence remains open.The authors therefore view their results as applying most directly to discrete approximations.Source: D Existence of Equilibria · p. 18
Loading 1209.4703v1…