Puzzles for Programmers and Pros

1.7. Social Games

Since Adam Smith observed that the "invisible hand" of the free market would force self-interested manufacturers to offer low prices to consumers, governments and politics have never been the same. It took almost two more centuries, however, to achieve a proper mathematical analysis of the consequences of selfish behavior beginning with Morgenstern's and Von Neumann's game theory and the work of John Nash. (You may recall Nash as the mathematician who was the subject of the movie A Beautiful Mind.)

This puzzle explores game theory as it applies to social goods. Let's start with the invisible hand.

Bob and Alice are competitive manufacturers. If they fix their prices at a high level, then they will share the market and each will receive a profit of 3. If Alice decides to lower prices while Bob doesn't, then Alice will enjoy a profit of 4 while Bob gets a profit of 0, because nobody will buy from him. At that point, Bob will lower his price to receive at least a profit of 1. Similarly, Bob receives 4 and Alice 0 if the roles are reversed. Simply following their self-interest, both will lower their prices and their profits will drop to 1 each.

This arrangement can be expressed in the following table, where Bob's profit is shown on the left in each pair and Alice's profit is on the right. So, the upper right corner, for example, represents the state in which Bob charges a high price (and receives a profit of 0) and Alice charges a low price (and receives a profit ...