Mechanism design with uncertain inputs (to err is human, to forgive divine)

Uriel Feige, Moshe Tennenholtz

We consider a task of scheduling with a common deadline on a single machine. Every player reports to a scheduler the length of his job and the scheduler needs to finish as many job…