On the Nisan-Ronen Conjecture for Submodular Valuations

Explore the Nisan-Ronen conjecture for submodular valuations in this 26-minute conference talk presented at an Association for Computing Machinery (ACM) event. Delve into the world of unrelated scheduling and mechanism design, examining truthful mechanisms and related results. Gain insights into various types of player valuations and cost functions, with a focus on weak monotonicity. Analyze mechanisms for two additive players and two tasks, and understand the proof sketch involving the Linearity Lemma. Conclude with valuable remarks on this complex topic in algorithmic game theory and mechanism design.

Intro
Unrelated Scheduling
Mechanism Design for Scheduling
Some truthful mechanisms
Some related results
Types of player valuations (cost functions)
Weak monotonicity
Mechanisms for 2 additive players and 2 tasks
Proof Sketch
Idea: Linearity Lemma
Concluding remarks