Job scheduling on parallel machines is a well-studied singleton
congestion game. We consider a variant of this game in which the
jobs are partitioned into competition sets, and the goal of every player
is to minimize the completion time of his job relative to his competitors.
Speciffcally, the primary goal of a player is to minimize the rank of its
completion time among his competitors, while minimizing the completion
time itself is a secondary objective. This fits environments with strong
competition among the participants, in which the relative performance
of the players determine their welfare.
We define and study the corresponding race scheduling game (RSG). We
show that RSGs are signiffcantly different from classical job-scheduling
games, and that competition may lead to a poor outcome. In particular,
an RSG need not have a pure Nash equilibrium, and best-response dynamics
may not converge to a NE even if one exists. We identify several
natural classes of games, on identical and on related machines, for which
a NE exists and can be computed efficiently, and we present tight bounds
on the equilibrium ineffciencies. For some classes we prove convergence
of BRD, while for others, even with very limited competition, BRD may
loop. Among classes for which a NE is not guaranteed to exist, we distinguish
between classes for which, it is tractable or NP-hard to decide
if a given instance has a NE.
Striving for stability, we also study the Nashification cost of RSGs, either
by adding dummy jobs, or by compensating jobs for having high rank.
Our analysis provides insights and initial results for several other congestion
and cost-sharing games that have a natural `race' variant.