On the Nisan-Ronen conjecture for submodular valuations

27^th March 2019, 13:00
Giorgos Christodoulou
University of Liverpool

Abstract

We will discuss the Nisan-Ronen conjecture, which was posed in the seminal paper by Nisan and Ronen in the ’99 paper that originated Algorithmic Mechanism Design. The conjecture has to do with the approximation ratio that can be achieved by truthful mechanisms for makespan minimization on scheduling unrelated machines. The conjecture, arguably the most important open problem in algorithmic mechanism design, states that the approximation ratio is n when the valuation of all machines are additive. We will give an overview of the area and present recent progress for submodular domains.

This is joint work with Elias Koutsoupias (U Oxford) and Annamaria Kovacs (U Frankfurt).