On the Nisan-Ronen conjecture for submodular valuations
Lists
Only you see this
Abstract
We consider incentive compatible mechanisms for a domain that is very close to the domain of scheduling n unrelated machines: the single exception is that the valuation of just one machine is submodular. For the scheduling problem with such cost functions, we give a lower bound of Ω(√n) on the approximation ratio of incentive compatible deterministic mechanisms. This is a strong information-theoretic impossibility result on the approximation ratio of mechanisms that provides strong evidence for the Nisan-Ronen conjecture. This is the first non-constant lower bound that assumes no restriction on the mechanism side; in contrast, all previous general results hold for only special classes of mechanisms such as local, strongly monotone, and anonymous mechanisms. 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 conjecture.
BibTeX
@inproceedings{christodoulou2020nisan,
author = {George Christodoulou and Elias Koutsoupias and Annamária Kovács},
title = {{On the Nisan-Ronen conjecture for submodular valuations}},
booktitle = {STOC},
year = {2020},
doi = {10.1145/3357713.3384299},
}Loading related content...