Example: Suppose that players would like to have part of a shared resource: each player wants to send information along a shared channel of known maximum capacity, say . In this game each player has an infinite set of strategies, where player ‘s strategy is to send units of flow along the channel.
Assume that each player would like to have a large fraction of the bandwidth, but assume also that the quality of the channel deteriorates with the total bandwidth used. We will describe this game by a simple model, using a benefit or payoff function for each set of strategies. If the total bandwidth exceeds the channel capacity, no player gets any benefit. If then the value for player is . This models exactly the kind of trade-off we have in mind: the benefit for a player deteriorates as the total assigned bandwidth increases, but it increases with his own share (up to a point).
In my humble opinion, the authors’ original wording is a bit confusing, so I took the liberty of slightly rephrasing their example.
The authors’ definition of stable strategies is:
Definition: a set of strategies is stable if all players are playing their optimal selfish strategy, given the strategies of all other players.
Using some quick, back-of-the-envelope calculations, the authors show that the stable strategy for each player is to send
units of flow. Note that each player’s optimal selfish strategy depends on all other players’ strategies. There’s a unique stable solution: each player sends
units of flow. The total bandwidth being used is thus
which is less than the channel capacity.
The authors omit a rigorous derivation of this solution (due to time and editorial constraints, I suppose). Therefore, I figured I could present here a more detailed, step-by-step derivation.
Let be a finite set of players. The set of available actions (pure strategies) for each player is . We denote by an action for player , and by
the vector of actions for all players in except . The -tuple is an action profile or outcome of the game, i.e., contains the actions (pure strategies) chosen by all players in . We denote by
the set of action profiles (set of outcomes), and by
the set of action profiles for all players except . Note that
, , and .
What we have is a one-shot simultaneous move game:
- it’s a one-shot game because there’s only one “round” or “stage”, and thus the players only have one chance to choose their actions.
- it’s a simultaneous move game because all players simultaneously choose an action from their set of available actions .
Each particular outcome benefits each player differently. Given two outcomes in , player will (in general) prefer one over the other. This preference can be encoded in each player’s utility function , which is defined as
but, for the sake of simplicity, we shall assume that the condition holds, so we can write the utility function simply as
Let be the -dimensional vector of ones. Then, the utility function for player can be written as
where is the total bandwidth being used. Alternatively, we can consider an utility function defined as
Since this is a simultaneous move game, all players must choose their actions in a simultaneous manner. It’s therefore impossible for any player to know the other players’ actions before choosing his own action.
Assumption: we assume that all players seek to maximize their utility. This implies, of course, that each players knows its utility function.
If player somehow knew the other players’ actions, his best response would be to choose action , where mapping is defined as
In other words, given , player ‘s best move is to choose action , so that his utility is maximized. The maximum utility that player can attain (given ) is .
Note that, given , player ‘s best response is
Assuming that , we have
The maximizer is computed by seeking points where the partial derivative of with respect to vanishes. Note that
and the maximixer is the vanishing set of function , which yields a unique solution
We assumed that all players are utility-maximizers. Let us assume that all players are choosing best response actions, i.e., for all . The vector of action profiles () can be computed by solving the following system of linear equations (“linear system”)
which can be written more compactly as
where is the identity matrix. Rearranging the terms, the system becomes
It can be shown that is invertible (see Appendix A), and therefore, the solution of the linear system exists and it is unique
We can use a “trick” to solve the linear system. Note that
The (unique) solution of the linear system can thus be written as
Finally, we have
When all players choose best response actions, then for each . This is the same solution which the authors derived using back-of-the-envelope calculations. Note that and therefore our assumption that the total bandwidth being used is less than the channel capacity does hold.
Tragedy of the Commons
The value of each player’s utility function is
The sum of all players’ utility functions is
As pointed out by Éva Tardos and Vijay Vazirani, this solution is a tragedy: when all players choose best response actions, the utility for each player is very low. Moreover, the more players trying to use the channel, the less “value” each player gets (which is intuitive).
This example illustrates the Tragedy of the Commons: each player benefits from using the shared channel and wants to use it as much as possible, while the “costs” of using the channel are distributed among all of those who use it. Players are selfish and want to maximize their own utility, which leads to over-exploitation of the shared resource. Selfishness does not always pay off.
We would like to show that matrix is invertible.
For starters, note that the entries of matrix are ones. Therefore, the columns/rows of are not linearly independent. In fact, since all columns/rows of are the same, we have . The nullspace of has dimension , and therefore of the eigenvalues of are zero.
Note also that matrix is symmetric, and thus, its eigenvalues are real and its eigenvectors are orthogonal. Note that
can be regarded as an eigendecomposition of : the only nonzero eigenvalue of is , and the eigenvector associated with it is . Matrix has zero eigenvalues: . Consequently, the nullspace of is a -dimensional linear subspace spanned by an orthonormal vector basis . We now form matrices
and . We thus have an eigendecomposition
Since is an orthonormal vector basis, and since is orthogonal to any vector in the nullspace, we have . Therefore
Finally, we can conclude that the eigenvalues of are the eigenvalues of plus one
and thus the spectrum of matrix is . Since none of the eigenvalues of is zero, we can conclude that matrix is invertible.