Complexity of Auctions with Interdependence
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910059478384640 |
|---|---|
| author | Loiseau, Patrick Mauras, Simon Xu, Minrui |
| author_facet | Loiseau, Patrick Mauras, Simon Xu, Minrui |
| contents | We study auction design in the celebrated interdependence model introduced by Milgrom and Weber [1982], where a mechanism designer allocates a good, maximizing the value of the agent who receives it, while inducing truthfulness using payments. In the lesser-studied procurement auctions, one allocates a chore, minimizing the cost incurred by the agent selected to perform it.
Most of the past literature in theoretical computer science considers designing truthful mechanisms with constant approximation for the value setting, with restricted domains and monotone valuation functions.
In this work, we study the general computational problems of optimizing the approximation ratio of truthful mechanism, for both value and cost, in the deterministic and randomized settings. Unlike most previous works, we remove the domain restriction and the monotonicity assumption imposed on value functions. We provide theoretical explanations for why some previously considered special cases are tractable, reducing them to classical combinatorial problems, and providing efficient algorithms and characterizations. We complement our positive results with hardness results for the general case, providing query complexity lower bounds, and proving the NP-Hardness of the general case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_18668 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Complexity of Auctions with Interdependence Loiseau, Patrick Mauras, Simon Xu, Minrui Computer Science and Game Theory Computational Complexity Data Structures and Algorithms We study auction design in the celebrated interdependence model introduced by Milgrom and Weber [1982], where a mechanism designer allocates a good, maximizing the value of the agent who receives it, while inducing truthfulness using payments. In the lesser-studied procurement auctions, one allocates a chore, minimizing the cost incurred by the agent selected to perform it. Most of the past literature in theoretical computer science considers designing truthful mechanisms with constant approximation for the value setting, with restricted domains and monotone valuation functions. In this work, we study the general computational problems of optimizing the approximation ratio of truthful mechanism, for both value and cost, in the deterministic and randomized settings. Unlike most previous works, we remove the domain restriction and the monotonicity assumption imposed on value functions. We provide theoretical explanations for why some previously considered special cases are tractable, reducing them to classical combinatorial problems, and providing efficient algorithms and characterizations. We complement our positive results with hardness results for the general case, providing query complexity lower bounds, and proving the NP-Hardness of the general case. |
| title | Complexity of Auctions with Interdependence |
| topic | Computer Science and Game Theory Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.18668 |