Load game

A load game or congestion game is a mathematical model from game theory . In such a game , each player chooses a subset of commonly available resources to accomplish their goal. The cost of a resource depends on the number of players who use it. Road networks are an example of load games . Each driver (player) chooses certain roads (resources) to get to his destination. The travel time (costs) on each route section depends on how many drivers use it.

Occupancy games are non-cooperative games as the players do not agree with each other. The class of occupancy games goes back to Robert W. Rosenthal , who described it in 1973 in his essay "A Class of Games Possessing Pure-Strategy Nash Equilibria".

Formal definition

Let it be a set of resources and in each case the cost function of the resource . A load game is a normal form game with ${\displaystyle R=\{r_{1},r_{2},\ldots ,r_{t}\}}$ ${\displaystyle t}$ ${\displaystyle c_{j}\colon \mathbb {N} _{0}\to \mathbb {R} }$ ${\displaystyle r_{j}}$ ${\displaystyle \Gamma =(N,\Sigma ,u)}$

• Crowd of players ${\displaystyle N=\{1,2,\ldots ,n\}}$
• Strategy room with ${\displaystyle \Sigma =\{\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{n}\}}$ ${\displaystyle \Sigma _{i}\subseteq {\mathcal {P}}(R)}$
• Utility functions

  ${\displaystyle u_{i}(\sigma )=-\sum _{r_{j}\in \sigma _{i}}c_{j}(x_{j}(\sigma ))}$

  ${\displaystyle x_{j}(\sigma )}$is the number of players who have chosen in the strategy combination. ${\displaystyle r_{j}}$ ${\displaystyle \sigma }$

The minus sign in the utility function comes from the fact that reduced costs are associated with increased benefits.

Nash equilibria

Every load game has at least one Nash equilibrium in pure strategies , since it has a potential function . One of these Nash equilibria is a combination of strategies that use the expression ${\displaystyle \sigma ^{*}}$

${\displaystyle \sum _{j=0}^{t}\sum _{y=0}^{x_{j}(\sigma )}c_{j}(y)}$

minimized. Because assuming no Nash equilibrium, there would be a player and a strategy in which this player would be better off: ${\displaystyle \sigma ^{*}}$ ${\displaystyle i}$ ${\displaystyle \sigma '=(\sigma _{i}',\sigma _{-i}^{*})}$

${\displaystyle -\sum _{r_{j}\in \sigma _{i}' \atop r_{j}\notin \sigma _{i}^{*}}c_{j}(x_{j}(\sigma ^{*})+1)>-\sum _{r_{j}\in \sigma _{i}^{*} \atop r_{j}\notin \sigma _{i}'}c_{j}(x_{j}(\sigma ^{*}))}$

This leads to a contradiction to the minimality of . ${\displaystyle \sigma ^{*}}$

${\displaystyle \sum _{j=0}^{t}\sum _{y=0}^{x_{j}(\sigma ')}c_{j}(y)=\sum _{j=0}^{t}\sum _{y=0}^{x_{j}(\sigma ^{*})}c_{j}(y)+\sum _{r_{j}\in \sigma _{i}' \atop r_{j}\notin \sigma _{i}^{*}}c_{j}(x_{j}(\sigma ^{*})+1)-\sum _{r_{j}\in \sigma _{i}^{*} \atop r_{j}\notin \sigma _{i}'}c_{j}(x_{j}(\sigma ^{*}))<\sum _{j=0}^{t}\sum _{y=0}^{x_{j}(\sigma ^{*})}c_{j}(y)}$

swell

1. ^ Robert W. Rosenthal: A Class of Games Possessing Pure-Strategy Nash Equilibria. In: International Journal of Game Theory. No. 2, 1973, pp. 65-67
2. ^ Dov Monderer, Lloyd S. Shapley: Potential Games. (PDF; 200 kB) Games and Economic Behavior 14, 1996, pp. 124-143