2016/05/16 by Ioannis Caragiannis, Caragiannis, Ioannis, Angelo Fanelli +1 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Discrete Mathematics (cs.DM) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.1605.04674
openalex publication_date 2016/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Coordination mechanisms aim to mitigate the impact of selfishness when scheduling jobs to different machines. Such a mechanism defines a scheduling policy within each machine and naturally induces a game among the selfish job owners. The desirable properties of a coordination mechanism includes simplicity in its definition and efficiency of the outcomes of the induced game. We present a broad class of coordination mechanisms for unrelated machine scheduling that are simple to define and we identify one of its members (mechanism \Dcoord) that is superior to all known mechanisms. \Dcoord induces potential games with logarithmic price of anarchy and only constant price of stability. Both bounds are almost optimal.