Complexity of Auctions with Interdependence
Patrick Loiseau, Simon Mauras, Minrui Xu · 2026
Read Complexity of Auctions with Interdependence by Patrick Loiseau, Simon Mauras, Minrui Xu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-18668.txt.
Description
Loiseau, Mauras, and Xu study how hard it is to design truthful auctions when bidder values depend on each other. The designer wants the good to reach the agent who values it most. A mirrored setup assigns a chore at least cost. Prior work mostly treats narrow domains with monotone values. The authors drop those limits and study the general problem, for both value and cost. Some known easy cases reduce to classic combinatorial problems. For the general case, they prove query lower bounds and NP-hardness.
Catalog record
| CREATOR | Patrick Loiseau, Simon Mauras, Minrui Xu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 129863 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.18668