Algorithmic Mechanism Design V: The Randomly Biased Min Work Mechanism Is a Strongly Truthful 7/4-Approximation for Two AgentsResearch Paper
Algorithmic mechanism design, introduced by Nisan and Ronen (Games Econ. Behav. 35, 2001), studies optimization problems whose input is held by self-interested agents. Each agent reports its private data to a protocol, and the protocol must choose an output and payments so that reporting the truth is in every agent's interest while the chosen output is…