On the Nisan-Ronen conjecture for submodular valuations

Conference item

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.

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

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Host title: STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
• Pages: 1086-1096
• Publication date: 2020-06-22
• Acceptance date: 2020-02-12
• Event title: 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020)
• Event location: Virtual event
• Event website: http://acm-stoc.org/stoc2020/
• Event start date: 2020-06-22
• Event end date: 2020-06-26
• DOI: 10.1145/3357713.3384299
• ISSN: 0737-8017
• ISBN: 9781450369794
• Language: English
• Keywords: incentive compatible scheduling; Nisan-Ronen conjecture; submodular optimization