PoA of Simple Auctions with Interdependent Values

Alon Eden, Michal Feldman, Inbal Talgam-Cohen, Ori ZviranAAAI 2021 · DOI

Abstract

Traditional auction theory often relies on the assumption of private values, where a bidder's valuation is independent of others' information. In many real-world scenarios, however, values are interdependent. This paper investigates the Price of Anarchy (PoA) in such settings, introducing a novel "$\gamma$-heterogeneity" condition to quantify information dispersion. We provide the first positive welfare guarantees for multi-item auctions with interdependent values, establishing bounds that bypass previous impossibility results and offering a path toward understanding efficiency in complex, correlated markets.

Introduction

In the study of auction design, the Price of Anarchy (PoA) serves as a critical metric for evaluating how much social welfare is lost when self-interested agents reach an equilibrium, compared to an optimal allocation by a social planner. While PoA is well-characterized for auctions with private values—where each bidder knows their own valuation—the landscape changes significantly under interdependent values (IDV).

In IDV settings, a bidder’s valuation for an item depends not only on their own private signal but also on the private signals of others. Common examples include auctions for oil drilling rights (where others' geological data informs the site's potential) or collectibles for resale (where others' knowledge of market demand affects value). Without restrictive assumptions, the PoA in these settings can degrade to the number of bidders ($n$), implying a near-total loss of potential social welfare. This paper addresses the challenge of finding natural conditions and simple mechanisms that guarantee high social welfare in these complex environments.

The Challenge of Interdependence

The primary difficulty in analyzing IDV auctions lies in the failure of the standard "smoothness framework." Most PoA analyses assume that bidders know their own values at the time of bidding. In IDV settings, a bidder's value is a function of signals they have not yet seen. Furthermore, the "single-crossing" property—a standard condition where a bidder's own signal affects their value more than anyone else's—is insufficient on its own to ensure good welfare outcomes in simple, non-truthful auctions.

The authors identify an "Information Asymmetry Wall": if a single bidder holds the vast majority of information regarding an item's value, simple auctions are mathematically doomed to perform poorly, with a PoA of $\Omega(m)$ where $m$ is the number of items. To bypass this, the paper introduces a "limited knowledge asymmetry" condition.

Methodological Framework: $\gamma$-Heterogeneity

To quantify the dispersion of information, the authors propose a new parameter: $\gamma$-heterogeneity. This metric measures how much a change in one bidder's signal affects the valuations of different participants.

  • When $\gamma=1$, influence is homogeneous; a signal change affects everyone's valuation equally.
  • As $\gamma$ increases, the influence of signals becomes more disparate across the bidder pool.

Using this parameter, the authors employ a Welfare Decomposition technique. They split total social welfare into two components: SELF (the value derived from a bidder's own signal) and OTHER (the value contributed by the signals of other bidders). By demonstrating that specific auction formats can "cover" both components, they derive robust welfare bounds.

Proposed Mechanism: Privatized Second-Price Auctions

For multi-item settings, the paper suggests a Simultaneous Privatized Second-Price Auction. In this mechanism:

  1. Bidders report their signals.
  2. The auctioneer calculates "privatized values"—the value a bidder would assign to an item if all other bidders' signals were zero.
  3. Separate second-price auctions are run for each item based on these privatized values.

This approach simplifies the strategic complexity for bidders while maintaining a connection to the underlying interdependent valuations.

Key Results

Single-Item Auctions

For single-item auctions, the paper bounds the Bayesian PoA of the Generalized Vickrey Auction (GVA) by $1 + \max\{\gamma, c\}$, where $c$ is the single-crossing constant. Notably, if the influence of information is homogeneous ($\gamma=1$), the auction achieves full efficiency.

Multi-Item Breakthroughs

In settings with unit-demand bidders (where each bidder seeks at most one item) and where the number of bidders $n$ is at least the number of items $m$, the authors establish a PoA bound of $O(d\gamma^2)$. Here, $d$ represents the degree of information asymmetry. This represents the first positive PoA result for multi-item auctions with correlated values.

Coordination Limits

The research also highlights the difficulty of coordination. When the number of items significantly exceeds the number of bidders ($m \gg n$), a "balls-and-bins" phenomenon occurs. Bidders struggle to coordinate on the most valuable items without centralized direction, leading to a welfare drop characterized by an $\Omega(\log n)^4$ PoA.

Conclusion and Future Work

This work bridges a significant gap in algorithmic game theory by providing welfare guarantees for auctions where information is shared and interdependent. By introducing $\gamma$-heterogeneity, the authors provide a language to describe why certain markets fail and others succeed.

However, limitations remain. The current multi-item results are restricted to unit-demand bidders, and the welfare guarantees depend on $\gamma$ and $d$ remaining relatively small. Future research may explore more complex combinatorial valuations (such as subadditive or XOS) and the development of "detail-free" auctions that do not require the auctioneer to have prior knowledge of the bidders' valuation functions.

Summary updated

BibTeX
@inproceedings{eden2021poa,
  author = {Alon Eden and Michal Feldman and Inbal Talgam-Cohen and Ori Zviran},
  title = {{PoA of Simple Auctions with Interdependent Values}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16671},
}
Figure