In classical job-scheduling games, each job behaves as a selfish player, choosing a machine to minimize its own completion time. To reduce the equilibria inefficiency, coordination mechanisms [8] are employed, allowing each machine to follow its own scheduling policy. In this paper we study the effects of incorporating rank-based utilities within coordination mechanisms across environments with either identical or unrelated machines. With rank-based utilities, players aim to perform well relative to their competitors, rather than solely minimizing their completion time. We first demonstrate that even in basic setups, such as two identical machines with unit-length jobs, a pure Nash equilibrium (NE) assignment may not exist. This observation motivates our inquiry into the complexity of determining whether a given game instance admits a NE. We prove that this problem is NP-complete, even in highly restricted cases. In contrast, we identify specific classes of games where a NE is guaranteed to exist, or where the decision problem can be resolved in polynomial time. Additionally, we examine how competition impacts the efficiency of Nash equilibria, or sink equilibria if a NE does not exist. We derive tight bounds on the price of anarchy, and show that competition may either enhance or degrade overall performance.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Coordination Mechanisms with Rank-Based Utilities

  • Gilad Lavie,
  • Tami Tamir

摘要

In classical job-scheduling games, each job behaves as a selfish player, choosing a machine to minimize its own completion time. To reduce the equilibria inefficiency, coordination mechanisms [8] are employed, allowing each machine to follow its own scheduling policy. In this paper we study the effects of incorporating rank-based utilities within coordination mechanisms across environments with either identical or unrelated machines. With rank-based utilities, players aim to perform well relative to their competitors, rather than solely minimizing their completion time. We first demonstrate that even in basic setups, such as two identical machines with unit-length jobs, a pure Nash equilibrium (NE) assignment may not exist. This observation motivates our inquiry into the complexity of determining whether a given game instance admits a NE. We prove that this problem is NP-complete, even in highly restricted cases. In contrast, we identify specific classes of games where a NE is guaranteed to exist, or where the decision problem can be resolved in polynomial time. Additionally, we examine how competition impacts the efficiency of Nash equilibria, or sink equilibria if a NE does not exist. We derive tight bounds on the price of anarchy, and show that competition may either enhance or degrade overall performance.