Truthful algorithms for scheduling selfish tasks on parallel machines

Eric Angel, Evripidis Bampis and Fanny Pascual
Theoretical Computer Science
Volume 369, Issues 1-3 , 15 December 2006, Pages 157-168
http://dx.doi.org/10.1016/j.tcs.2006.07.057

WINE2005から．
スケジューリングとオークションの論文．
設定はm個の同一機械並列スケジューリングで，makespanの最小化．
これが社会的な目的関数．
一方，n個のジョブはそれぞれ自分の完了時刻を最小化したい．
こちらが個人的な目的関数．
ジョブは自分の処理時間を申告．それに応じてメカニズムが機械への割当と順番を定める．
Christodoulou, Koutsoupias, & Nanavati (ICALP2004) では，social optimumの2倍以下となるmakespanを与えるtruthfulなオークションを提案したが，この論文はそれを改善．
なかなか面白い．