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