Solving the „Tracking Game“

Guest article from Doris A. Behrens


Games taking place in a shared environment are characterized by the fact that the effectiveness of individual decisions heavily depends on the decisions of other players. Our algorithm OPTGAME is able to approximate the evolution of choices to be made if a number of independent decision makers seek to reach individually desirable states. The evolution of states subject to control is described by a system of nonlinear difference equations. We call this a „tracking game“, since is an extension of the linear regulator problem (also known as „tracking problem“) that is well known from LQ optimal control theory.
OPTGAME is a tool that steers the control and state paths towards desired outcomes. It is novel in a way that it works for game theoretic systems with nonlinear constraints. It searches for equilibrium solutions by iteratively applying a sequence of local linearization and optimization over the entire planning horizon. The tool yields three types of non-cooperative equilibrium solutions (open-loop Nash equilibrium, feedback Nash equilibrium, feedback Stackelberg equilibrium) plus one cooperative solution (Pareto-optimal strategy).
An example for such a game could be the decision-making within a monetary union such as the European Monetary Union (EMU). In this game all but one player represent countries with intentions for economic growth, employment and limited budget deficit and one player represents the European Central Bank, aiming solely at price stability. Besides trade-offs between state variables, for example the well-known trade-off between unemployment and price stability (see Phillips curve), there are strong economic interdependencies due to international trade.

European Monetary Union

For instance, if a single country aims at economic growth, one option could be to increase the demand for goods and services from the public sector. This increases production in response to demand, which in turn increases incomes. However, within an open economy the future success strongly depends on the situation and behavior of the other member countries. In order to find a solution for this problem it is necessary to estimate the countries’ individual parameters as well as the degree of economic interdependencies (like trade) between countries.
Such models, in order to be accurate are inherently nonlinear, which cannot be solved analytically by a linear model such as the LQ game. In our work we apply OPTGAME to a monetary union macroeconomic model based on the nonlinear MUMOD1 model. In this model, there are basically two groups of countries, one economically stronger than the other, all experiencing a brief period of recession.

Doris A. Behrens is a senior re-
searcher working on optimization
in techno-socio-economic systems
at the Alpen-Adria-Universität
Klagenfurt

Without policy intervention all countries would experience a deep recession and an enormous increase in public debt. By applying OPTGAME for different solution concepts we learn that macroeconomic properties like public debt, economic growth, inflation, etc. can be significantly improved with system-aware control actions of players.

The OPTGAME tool is available as MATLAB implementation upon request (Contact Doris A. Behrens).

Literature:

Doris A. Behrens, Reinhard Neck, Approximating Solutions for Nonlinear Dynamic Tracking Games, Computational Economics, Springer, February 2014. DOI: 10.1007/s10614-014-9420-4

Reinhard Neck, Doris A. Behrens, A macroeconomic policy game for a monetary union with adaptive expectations. Atlantic Economic Journal, 37(4), 335–349, 2009. DOI: 10.1007/s11293-009-9186-6f

Cake paradox resolved - an excursion into Game Theory

In the last posting we elaborated the cake paradox. In short, if we agree to bring in a cake on any day within the following week, Friday (the last day) is not a good choice, because then, the people can predict this already after there was no cake until Thursday. Iterating this argument we end up that no day is good for a surprise.

Actually, we need to clarify certain things in the model here. First, a situation where one is expecting a cake, but it is not brought is also a kind of surprise, though a disappointing one.
Second, if the colleagues are forced to choose one day, the odds are simply 1 out of 5 to guess the day right. Waiting until Thursday to place the bet does not help the guesser here, because in this case you have a high chance to have already lost because the cake was brought before.

However, the game becomes interesting, if the colleagues get the possibility to put a bet on a day at any time before that day but making betting optional. So if you are a cautious person, you might not bet at all, or would wait until Thursday evening, and place the sure bet in case the was not brought before. What is the best strategy for this set up?

Let's look at the payoff table for a situation where only Thursday and Friday are left, the cake has not been brought in yet and no bet was made so far. Player A has to bring in the cake, while player B tries to place the bet.

	Player A brings cake on Thursday	Player A brings cake on Friday
Player B places bet on Thursday	(-1,1) Player B guessed it right	(1,-1) Player B guessed it wrong
Player B waits and eventually places bet on Friday	(0,0) No bet was placed, game is over (because cake is there)	(-1,1) Player B guessed it right

This situation has no pure-strategy Nash Equilibrium. For the best mixed strategy, Player A should chose Thursday with a probability of 2/3, otherwise Friday. In contrast, Player B's best strategy is to bet on Friday with a probability of 2/3. The expected payoff for Player A is then -1/3, which means an advantage for B.

Now we can set up a payout table for the "Wednesday or Later" game. The "Later"-Payoff in the case that neither the cake has been brought yet nor Player B has used her bet so far is the 1/3 derived from the previous payout table.

	Player A brings cake on Wednesday	Player A brings cake later
Player B places bet on Wednesday	(-1,1) Player B guessed it right	(1,-1) Player B guessed it wrong
Player B waits	(0,0) No bet was placed, game is over (because cake is there)	(1/3,-1/3) Game defaults to previous situation

This way we can iterate the game until we end up on Monday. Assuming optimum mixed strategies, the best strategy for Player A to bring in the cake calculates to
16/31 for Monday
8/31 for Tuesday
4/31 for Wednesday
2/31 for Thursday
and 1/31 for Friday.

The guessing player has the same probabilities but increasing from 1/31 for Monday until 16/31 for Friday because the chances favor the guesser towards the end of the week. These mixed strategies establish a Nash equilibrium, thus none of the players has a benefit on changing the strategy. In overall, the game slightly favors the guesser, who is expected to win 3% more often.

Now, we earned ourselves a cake - bon appetit!

• Strategies in Game Theory@Wikipedia
  
• Nash Equilibrium@Wikipedia
  
• Unexpected hanging paradox@Wikipedia