On the Nisan-Ronen conjecture for submodular valuations

Journal article

We consider mechanisms for scheduling n unrelated machines when the valuations of the players (i.e., machines) are submodular. We give a lower bound of Ω(√n) on the approximation ratio of incentive compatible deterministic mechanisms. This lower bound holds for supermodular valuations and also when all players, except of one, have additive valuations. This is an information-theoretic impossibility result on the approximation ratio of mechanisms that provides strong evidence for the Nisan-Ronen conjecture, which states that the approximation ratio is n when the valuations of all machines are additive. Our approach is based on a novel multi-player characterization of appropriately selected instances that allows us to focus on particular type of algorithms, linear mechanisms, and it is a potential stepping stone towards the full resolution of the Nisan-Ronen conjecture.

Authors: Christodoulou, G; Koutsoupias, E; Kovács, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Journal: SIAM Journal on Computing
• Volume: 54
• Issue: 4
• Pages: 1021-1064
• Publication date: 2025-08-11
• Acceptance date: 2025-05-02
• DOI: 10.1137/22m1483141
• EISSN: 1095-7111
• ISSN: 0097-5397
• Language: English
• Keywords: algorithmic mechanism design; algorithmic game theory; truthfulness