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.