On the Nisan-Ronen conjecture for submodular valuations



Christodoulou, Giorgos, Koutsoupias, Elias and Kovacs, Annamaria
(2020) On the Nisan-Ronen conjecture for submodular valuations. In: STOC 2020, 2020-6-22 - 2020-6-26.

[img] Text
submodular.pdf - Author Accepted Manuscript

Download (359kB) | Preview

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 ω(gn) 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.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: Nisan-Ronen conjecture, incentive compatible scheduling, submodular optimization
Depositing User: Symplectic Admin
Date Deposited: 15 Apr 2020 09:56
Last Modified: 18 Jan 2023 23:54
DOI: 10.1145/3357713.3384299
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3083240