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

CREATORPatrick Loiseau, Simon Mauras, Minrui Xu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE129863
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.18668

Browse the full library · About the Tower of Babel