List Scheduling on a Congestion Game

In a congestion game, each player chooses a strategy (typically a route), and the latency on each resource depends on how many players use it. List scheduling is a sequential greedy algorithm that processes players in a fixed order $1, 2, \ldots, n$ and assigns each player to the strategy that minimizes its own latency given the choices already committed by earlier players.

Let $n_s^{(k-1)}$ be the number of already-assigned players on strategy $s$ after the first $k-1$ players have been placed. Player $k$ is then assigned to

$$s_k = \arg\min_{s \in S_k} \ell_s\!\left( n_s^{(k-1)} + 1 \right),$$

where $\ell_s(x)$ is the latency on $s$ when $x$ players use it. Each decision is myopic -- player $k$ ignores future arrivals and just minimizes its own cost against the current load.

For example, consider two parallel routes with latencies $\ell_1(x) = 3x$ and $\ell_2(x) = 5,$ and two flights $F_1, F_2$ processed in order:

• $F_1{:}$ $\ell_1(1) = 3,$ $\ell_2(1) = 5.$ Choose route $1.$ Loads become $(1, 0).$
• $F_2{:}$ $\ell_1(2) = 6,$ $\ell_2(1) = 5.$ Choose route $2.$ Loads become $(1, 1).$