• Abstract. The Nisan-Ronen conjecture states that no truthful mechanism for makespan-minimization when allocating a set of tasks to \(n\) unrelated machines can have approximation ratio less than \(n\). Over more than two decades since its formulation, little progress has been made in resolving it. In this talk, I will discuss recent progress towards validating the conjecture by showing a lower bound of \(1+\sqrt{n}\). The lower bound is based on studying an interesting class of instances that can be represented by multi-graphs in which vertices represent machines and edges represent tasks, and each task should be allocated to one of its two incident machines.

Elias Koutsoupias (Oxford)

17 November '21

• Bio. Elias Koutsoupias is a professor of computer science at the University of Oxford. His research interests include algorithmic aspects of game theory, economics and networks, online algorithms, decision-making under uncertainty, design and analysis of algorithms, computational complexity. He received the Gödel Prize of theoretical computer science in 2012 for his work on the price of anarchy, in reference to laying the foundations of algorithmic game theory. He is also the recipient of the ERC Advanced Grant “Algorithms, Games, Mechanisms, and the Price of Anarchy”. He previously held faculty positions at the University of California, Los Angeles (UCLA) and the University of Athens. He studied at the National Technical University of Athens (B.S. in electrical engineering) and the University of California, San Diego (Ph.D. in computer science).

Historical Notes and Further Readings

• The problem of truthful machine scheduling is the prototypical problem that Nisan and Ronen studied when they defined the field of algorithmic mechanism design [1]. In this version of the classic machine scheduling problem for makespan minimisation, the machines are self-interested agents that wish to minimise their assigned load, and have to be monetarily compensated in order to process the jobs. The challenge is how to come up with a truthful mechanism, i.e., a function that assigns jobs to machines and issues payments such that the machines do not have any incentives to misreport their real processing times. The agenda of algorithmic mechanism design studies how well an aggregate objective (e.g., here the makespan) can be approximated by truthful mechanisms. In their original paper, Nisan and Ronen proved that a version of the VCG mechanism (which is known to be optimal for sum objectives) achieves an approximation ratio of \(n\) for the problem. They complemented this result with a lower bound of 2 for the approximation ratio of any truthful mechanism. They also conjectured that no truthful mechanism can actually achieve an approximation ratio better than \(n\), which would prove that VCG mechanism is indeed optimal. Despite many years of work and significant effort, until 2020, the best known lower bound was 2.618 due to Koutsoupias and Vidali [2]. In 2020, two improvements to this bound were achieved: first Giannakopoulos, Hammerl and Poças [3] improved the bound to 2.755 and then Dobzinski and Shaulker [4] improved the bound to \(3-\delta\), for any positive \(\delta\). Still, all of these bounds are small constants, and quite far from the upper bound of n provided by Nisan and Ronen. The first major breakthrough came when Christodoulou, Koutsoupias and Kovacs [5] finally showed a lower bound of \(1+\sqrt{n}\) on the approximation ratio of truthful mechanisms, thus making significant progress towards solving the Nisan-Ronen conjecture.

• Related Work

1. Noam Nisan and Amir Ronen. "Algorithmic mechanism design." Games and Economic behavior 35.1-2 (2001): 166-196.
2. Elias Koutsoupias and Angelina Vidali. "A lower bound of \(1+\phi\) for truthful scheduling mechanisms." Algorithmica 66.1 (2013): 211-223.
3. Yiannis Giannakopoulos, Alexander Hammerl and Diogo Poças. "A new lower bound for deterministic truthful scheduling." Algorithmica (2021): 1-19.
4. Shahar Dobzinski and Ariel Shaulker. "Improved lower bounds for truthful scheduling." arXiv preprint arXiv:2007.04362 (2020).
5. George Christodoulou, Elias Koutsoupias and Annamária Kovács. "On the Nisan-Ronen conjecture." Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (2021), to appear.

• Further Reading

1. George Christodoulou, Elias Koutsoupias, and Annamária Kovács. "On the Nisan-Ronen conjecture for submodular valuations." Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC) (2020).
2. George Christodoulou, Elias Koutsoupias and Annamaria Kovacs. "Truthful allocation in graphs and hypergraphs." Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP) (2021).
3. Itai Ashlagi, Shahar Dobzinski and Ron Lavi. "Optimal lower bounds for anonymous scheduling mechanisms." Mathematics of Operations Research 37.2 (2012): 244-258.
4. George Christodoulou, Elias Koutsoupias and Angelina Vidali. "A lower bound for scheduling mechanisms." Algorithmica 55.4 (2009): 729-740.
5. Yiannis Giannakopoulos and Maria Kyropoulou. "The VCG mechanism for Bayesian scheduling." ACM Transactions on Economics and Computation (TEAC) 5.4 (2017): 1-16.
6. Michael Saks and Lan Yu. "Weak monotonicity suffices for truthfulness on convex domains." Proceedings of the 6th ACM conference on Electronic Commerce (EC) (2005).
7. George Christodoulou and Elias Koutsoupias. "Mechanism Design for Scheduling." Bull. EATCS 97 (2009): 40-59.