Scheduling games with rank-based utilities

• 成果类型: Article
• 署名作者: Rosner, Shaul; Tamir, Tami
• 署名单位: Reichman University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2023.03.007
• 发表日期: 2023
• 页码: 229-252
• 关键词: Scheduling games; COMPETITION; Equilibrium inefficiency; Nashifying

摘要

Job scheduling on parallel machines is a well-studied singleton congestion game. We consider a variant of this game, arising in environments with strong competition. In a scheduling game with rank-based utilities (SRBG) the players are partitioned into competition sets, and the goal of every player is to perform well relative to its competitors. We show that SRBGs are significantly different from classical job-scheduling games, and that competition may lead to poor outcomes. An SRBG need not have a pure Nash equilibrium, and best-response dynamics may not converge to a NE even if one exists. We identify several classes of games for which a NE exists and can be computed efficiently, present tight bounds on the equilibrium inefficiencies, and suggest ways to modify SRBGs in order to guarantee NE existence. Our analysis provides insights for several other congestion and cost-sharing games that have a natural 'rank-based' variant. (c) 2023 Elsevier Inc. All rights reserved.