On the Nisan-Ronen conjecture for submodular valuations

George Christodoulou, Elias Koutsoupias, Annamária Kovács

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...

Figure