Game Theory: Decision Making with Kotlin Examples

Game theory is a mathematical discipline that considers the modeling of actions of players who have a goal, which is to choose the optimal strategies of behavior in conditions of conflict. On Habré, this topic has already been covered , but today we will talk about some of its aspects in more detail and consider examples on Kotlin.

So, a strategy is a set of rules that determine the choice of a course of action for each personal move, depending on the situation. The optimal player strategy is a strategy that provides the best position in this game, i.e. maximum winnings If the game is repeated several times and contains, besides personal, random moves, then the optimal strategy provides the maximum average gain.

The task of game theory is to identify the optimal strategies of players. The main assumption, on the basis of which the optimal strategies are found, is that the opponent (or opponents) is no less intelligent than the player himself, and does everything to achieve his goal. Relying on a sensible adversary is only one of the potential positions in a conflict, but in the theory of games, it is she who is the basis.

There are games with nature in which there is only one participant maximizing their profits. Games with nature are mathematical models in which the choice of decision depends on objective reality. For example, customer demand, state of nature, etc. “Nature” is a generalized concept of an adversary who does not pursue his own goals. In this case, several criteria are used to select the optimal strategy.
There are two types of tasks in games with nature:
')

1. the problem of making decisions under risk conditions, when the probabilities with which nature assumes each of the possible states are known;
2. decision-making problems in conditions of uncertainty, when there is no possibility to obtain information about the probabilities of the appearance of states of nature.

Briefly about these criteria described here .

Now we will consider the decision criteria in pure strategies, and at the end of the article we will solve the game in mixed strategies by an analytical method.

Formulation of the problem

All decision criteria, we will analyze the end-to-end example. The task is this: the farmer needs to determine in what proportions to sow his field with three crops, if the yield of these crops, and, therefore, profit, depend on what summer will be: cool and rainy, normal, or hot and dry. The farmer calculated the net profit from 1 hectare from different crops depending on the weather. The game is determined by the following matrix:



Further we will present this matrix in the form of strategies:

$$

$$U_ {1} = (0,2,5), U_ {2} = (2,3,1), U_ {3} = (4,3, -1)$$

Looking for the optimal strategy we denote $$$u_ {opt}$ . We will solve the game using the criteria of Wald, optimism, pessimism, Savage and Hurwitz under conditions of uncertainty and the criteria of Bayes and Laplace under conditions of risk.

As mentioned above, examples will be on Kotlin. I note that there are generally solutions like Gambit (written in C), Axelrod and PyNFG (written in Python), but we will ride our own bike, assembled on the knee, just to poke a little stylish, trendy and youth programming language.

In order to programmatically implement the solution of the game, we will create several classes. First, we need a class that allows us to describe a row or column of the game matrix. The class is extremely simple and contains a list of possible values ​​(alternatives or states of nature) and the corresponding name. The key field will be used for identification, as well as for comparison, and the comparison will be needed when implementing dominance.


The game matrix contains information about alternatives and states of nature. In addition, it implements some methods, such as finding the dominant set and the net price of the game.


We describe the interface that meets the criteria

Decision making under uncertainty

Decision making under uncertainty implies that the player is not opposed by a reasonable opponent.

Wald Criterion

In the Wald criterion, the worst possible outcome is maximized:

$$

$$u_ {opt} = max_ {i} min_ {j} [U]$$

Using the criterion insures against the worst result, but the price of such a strategy is the loss of the opportunity to get the best possible result.

Consider an example. For strategies $$$U_ {1} = (0,2,5), U_ {2} = (2,3,1), U_ {3} = (4,3, -1)$ find the minimums and get the next three $$$S = (0, 1, -1)$ . The maximum for the indicated three will be the value 1, therefore, according to the Wald criterion, the winning strategy is the strategy $$$U_ {2} = (2,3,1)$ corresponding to planting culture 2.

Software implementation of the Wald criterion is simple:

 class WaldCriteria(gameMatrix : GameMatrix) : ICriteria { val gameMatrix: GameMatrix init{ this.gameMatrix = gameMatrix } override fun optimum(): List<GameVector> { val mins = gameMatrix.alternatives.map { a -> Pair(a, a.min()) } val max = mins.maxWith( Comparator { o1, o2 -> o1.second!!.compareTo(o2.second!!)}) return mins .filter { m -> m.second == max!!.second } .map { m -> m.first } } } 

For greater clarity, for the first time I will show how the solution would look like a test:


It is not difficult to guess that for other criteria the difference will be only in the creation of the object criteria .

Optimism criterion

When using the optimist criterion, the player chooses a solution that gives the best result, while the optimist assumes that the conditions of the game will be most favorable for him:

$$

$$u_ {opt} = max_ {i} max_ {j} [U]$$

An optimist's strategy can lead to negative consequences when the maximum supply coincides with the minimum demand — a firm may suffer losses when writing off unsold products. At the same time, the strategy of the optimist has a certain meaning, for example, there is no need to worry about unsatisfied customers, since any possible demand is always satisfied, so there is no need to maintain the location of customers. If the maximum demand is realized, the strategy of the optimist allows you to get the maximum utility at the time, as other strategies will lead to lost profits. This gives certain competitive advantages.

Consider an example. For strategies $$$U_ {1} = (0,2,5), U_ {2} = (2,3,1), U_ {3} = (4,3, -1)$ find the maximum and get the next three $$$S = (5, 3, 4)$ . The maximum for the indicated three will be 5, therefore, according to the criterion of optimism, the winning strategy is the strategy $$$U_ {1} = (0,2,5)$ corresponding to planting culture 1.

The implementation of the optimism criterion hardly differs from the Wald criterion:

 class WaldCriteria(gameMatrix : GameMatrix) : ICriteria { val gameMatrix: GameMatrix init{ this.gameMatrix = gameMatrix } override fun optimum(): List<GameVector> { val mins = gameMatrix.alternatives.map { a -> Pair(a, a.min()) } val max = mins.maxWith( Comparator { o1, o2 -> o1.second!!.compareTo(o2.second!!)}) return mins .filter { m -> m.second == max!!.second } .map { m -> m.first } } } 

Pessimism criterion

This criterion is designed to select the smallest element of the game matrix from its minimum possible elements:

$$

$$u_ {opt} = min_ {i} min_ {j} [U]$$

The criterion of pessimism suggests that developments will be unfavorable for the decision maker. When using this criterion, the decision maker is guided by the possible loss of control over the situation, therefore, he tries to eliminate potential risks by choosing the option with the minimum yield.

Consider an example. For strategies $$$U_ {1} = (0,2,5), U_ {2} = (2,3,1), U_ {3} = (4,3, -1)$ find the minimum and get the next three $$$S = (0, 1, -1)$ . The minimum for the specified three will be -1, therefore, according to the criterion of pessimism, the winning strategy is the strategy $$$U_ {3} = (4.3, -1)$ corresponding to planting culture 3.

After getting acquainted with the Wald and optimism criteria, I think it is easy to guess what the class of pessimism criterion will look like:

 class PessimismCriteria(gameMatrix : GameMatrix) : ICriteria { val gameMatrix: GameMatrix init{ this.gameMatrix = gameMatrix } override fun optimum(): List<GameVector> { val mins = gameMatrix.alternatives.map { a -> Pair(a, a.min()) } val min = mins.minWith( Comparator { o1, o2 -> o1.second!!.compareTo(o2.second!!)}) return mins .filter { m -> m.second == min!!.second } .map { m -> m.first } } } 

Savage Criterion

The Savage Criterion (a regretting pessimist criterion) involves minimizing the greatest lost profits, in other words, the greatest regrets for lost profits are minimized:

$$

$$u_ {opt} = min_ {i} max_ {j} [S] \\ s_ {i, j} = (max \ begin {bmatrix} u_ {1, j} \\ u_ {2, j} \\. .. \\ u_ {n, j} \ end {bmatrix} - u_ {i, j})$$

In this case, S is a regret matrix.

The optimal solution according to the Savage criterion should give the least regret of the regrets found at the previous step. The solution corresponding to the found utility will be optimal.

The peculiarities of the solution obtained include the guaranteed absence of the greatest disappointments and the guaranteed reduction of the maximum possible gains of other players.

Consider an example. For strategies $$$U_ {1} = (0,2,5), U_ {2} = (2,3,1), U_ {3} = (4,3, -1)$ we will make a regret matrix:



Three of maximum regrets $$$S = (4,4,6)$ . The minimum value of these risks will be 4, which corresponds to the strategies $$$U_ {1}$ and $$$U_ {2}$ .

To program the Savage criterion is a little more difficult:

 class SavageCriteria(gameMatrix: GameMatrix) : ICriteria { val gameMatrix: GameMatrix init { this.gameMatrix = gameMatrix } fun GameMatrix.risk(): List<Pair<GameVector, Double?>> { val maxStates = this.natureStates.map { n -> Pair(n, n.values.max()) } .map { n -> n.first.key to n.second }.toMap() var am: MutableList<Pair<GameVector, List<Double>>> = mutableListOf() for (a in this.alternatives) { var v: MutableList<Double> = mutableListOf() for (i in 0..a.values.lastIndex) { val mn = maxStates.get(i) v.add(mn!! - a.values[i]) } am.add(Pair(a, v.toList())) } return am.map { m -> Pair(m.first, m.second.max()) } } override fun optimum(): List<GameVector> { val risk = gameMatrix.risk() val minRisk = risk.minWith(Comparator { o1, o2 -> o1.second!!.compareTo(o2.second!!) }) return risk .filter { r -> r.second == minRisk!!.second } .map { m -> m.first } } } 

Hurwitz criterion

The Hurwitz criterion is a regulated compromise between extreme pessimism and complete optimism:

$$

$$u_ {opt} = max (\ gamma × A (k) + A (0) × (1 - \ gamma))$$

A (0) is the strategy of the extreme pessimist, A (k) is the strategy of a complete optimist, $$$\ gamma = 1$ - set value of weight coefficient: $$$0 \ leq \ gamma \ leq1$ ; $$$\ gamma = 0$ - extreme pessimism, $$$\ gamma = 1$ - complete optimism.

With a small number of discrete strategies, setting the desired value of the weighting factor $$$\ gamma$ and then round the result to the nearest possible value, taking into account the performed sampling.

Consider an example. For strategies $$$U_ {1} = (0,2,5), U_ {2} = (2,3,1), U_ {3} = (4,3, -1)$ . We assume that the coefficient of optimism $$$\ gamma = $ 0.$ . Now we will make the table:



The maximum value of the calculated H will be 3, which corresponds to the strategy $$$U_ {1}$ .

The implementation of the Hurwitz criterion is already more voluminous:

 class HurwitzCriteria(gameMatrix: GameMatrix, optimisticKoef: Double) : ICriteria { val gameMatrix: GameMatrix val optimisticKoef: Double init { this.gameMatrix = gameMatrix this.optimisticKoef = optimisticKoef } inner class HurwitzParam(xmax: Double, xmin: Double, optXmax: Double){ val xmax: Double val xmin: Double val optXmax: Double val value: Double init{ this.xmax = xmax this.xmin = xmin this.optXmax = optXmax value = xmax * optXmax + xmin * (1 - optXmax) } } fun GameMatrix.getHurwitzParams(): List<Pair<GameVector, HurwitzParam>> { return this.alternatives.map { a -> Pair(a, HurwitzParam(a.max()!!, a.min()!!, optimisticKoef)) } } override fun optimum(): List<GameVector> { val hpar = gameMatrix.getHurwitzParams() val maxHurw = hpar.maxWith(Comparator { o1, o2 -> o1.second.value.compareTo(o2.second.value) }) return hpar .filter { r -> r.second == maxHurw!!.second } .map { m -> m.first } } } 

Making decisions at risk

Decision making methods can rely on decision criteria under risk conditions if the following conditions are met:

• lack of reliable information on possible consequences;
• availability of probability distributions;
• knowledge of the likelihood of outcomes or consequences for each decision.

If the decision is made under risk, then the cost of alternative solutions are described by probability distributions. In this regard, the decision is based on the use of the criterion of the expected value, according to which alternative solutions are compared in terms of maximizing the expected profit or minimizing the expected costs.

The expected value criterion can be reduced to either maximizing the expected (average) profit, or minimizing the expected costs. In this case, it is assumed that the profit (cost) associated with each alternative solution is a random variable.

The formulation of such tasks is usually the following: a person chooses some actions in a situation where random events affect the outcome of actions. But the player has some knowledge about the probabilities of these events and can calculate the most advantageous set and sequence of his actions.

So that you can continue to give examples, let's add the game matrix with probabilities:



In order to take into account the probabilities will have to alter a little class that describes the game matrix. It turned out, in truth, not very elegant, but oh well.

Bayes criterion

Bayes criterion (expectation criterion) is used in decision making under risk as a strategy assessment. $$$u_ {i}$ the mathematical expectation of the corresponding random variable appears. In accordance with this rule, the optimal strategy of the player $$$u_ {opt}$ is found from the condition:

$$

$$u_ {opt} = max_ {1 \ leq i \ leq n} M (u_ {i}) \\ M (u_ {i}) = max_ {1 \ leq i \ leq n} \ sum_ {j = 1} ^ m u_ {i, j} \ cdot y_ {j} ^ 0$$

In other words, an indicator of the strategy’s inefficiency $$$u_ {i}$ according to the Bayes criterion with respect to risks, the average value (expectation) of the risks of the i-th row of the matrix is $$$U$ whose probabilities coincide with the probabilities of nature. Then the optimal among the pure strategies for the Bayes criterion regarding risks is the strategy $$$u_ {opt}$ which has minimal inefficiency, that is, minimal average risk. The Bayes criterion is equivalent to gains and risks, i.e. if strategy $$$u_ {opt}$ is optimal for the Bayes criterion for winnings, it is optimal for the Bayes criterion for risks, and vice versa.

Let us turn to an example and calculate the mathematical expectations:

$$

$$M_1 = 0 \ cdot0.2 +2 \ cdot0.5 +5 \ cdot0.3 = 2.5; \\ M_2 = 2 \ cdot0.2 +3 \ cdot0.5 +1 \ cdot0.3 = 2.2 ; \\ M_4 = 0 \ cdot0.2 +3 \ cdot0.5 + (- 1) \ cdot0.3 = 2.0;$$

The maximum expected value is $$$M_1$ therefore, the winning strategy is strategy $$$U_1$ .

Software implementation of the Bayesian criterion:

 class BayesCriteria(gameMatrix: ProbabilityGameMatrix) : ICriteria { val gameMatrix: ProbabilityGameMatrix init { this.gameMatrix = gameMatrix } fun ProbabilityGameMatrix.bayesProbability(): List<Pair<GameVector, Double?>> { var am: MutableList<Pair<GameVector, Double>> = mutableListOf() for (a in this.alternatives) { var alprob: Double = 0.0 for (i in 0..a.values.lastIndex) { alprob += a.values[i] * this.probabilities[i] } am.add(Pair(a, alprob)) } return am.toList(); } override fun optimum(): List<GameVector> { val risk = gameMatrix.bayesProbability() val maxBayes = risk.maxWith(Comparator { o1, o2 -> o1.second!!.compareTo(o2.second!!) }) return risk .filter { r -> r.second == maxBayes!!.second } .map { m -> m.first } } } 

Laplace criterion

The Laplace criterion represents a simplified maximization of the expectation of utility when the assumption of equal probability of demand levels is true, which eliminates the need to collect real statistics.

In the general case, when using the Laplace criterion, the matrix of expected utilities and the optimal criterion are determined as follows:

$$

$$u_ {opt} = max [\ overline {U}] \\ \ overline {U} = \ begin {bmatrix} \ overline {u} _ {1} \\ \ overline {u} _ {2} \\. .. \\ \ overline {u} _ {n} \ end {bmatrix}, \ overline {u} _ {i} = \ frac {1} {n} \ sum_ {j = 1} ^ nu_ {i, j }$$

Consider an example of decision making based on the Laplace criterion. Calculate the average for each strategy:

$$

$$\ overline {u} _ {1} = \ frac {1} {3} \ cdot (0 + 2 + 5) = 2,3 \\ \ overline {u} _ {2} = \ frac {1} { 3} \ cdot (2 + 3 + 1) = 2.0 \\ overline {u} _ {3} = \ frac {1} {3} \ cdot (4 + 3-1) = $ 2.$$

Thus, the winning strategy is the strategy $$$U_1$ .

Software implementation of the Laplace criterion:

 class LaplaceCriteria(gameMatrix: GameMatrix) : ICriteria { val gameMatrix: GameMatrix init { this.gameMatrix = gameMatrix } fun GameMatrix.arithemicMean(): List<Pair<GameVector, Double>> { return this.alternatives.map { m -> Pair(m, m.values.average()) } } override fun optimum(): List<GameVector> { val risk = gameMatrix.arithemicMean() val maxBayes = risk.maxWith(Comparator { o1, o2 -> o1.second.compareTo(o2.second) }) return risk .filter { r -> r.second == maxBayes!!.second } .map { m -> m.first } } } 

Mixed strategies. Analytical method

The analytical method allows to solve the game in mixed strategies. In order to formulate an algorithm for finding the solution of a game by an analytical method, consider some additional concepts.

Strategy $$$U_ {i}$ dominated by strategy $$$U_ {i-1}$ , If everyone $$$u_ {1..n} \ in U_ {i} \ geq u_ {1..n} \ in U_ {i-1}$ .In other words, if in a certain row of the payment matrix all elements are greater than or equal to the corresponding elements of another row, then the first row dominates the second and is called the dominant row. And also if in some column of the payment matrix all elements are less or equal to the corresponding elements of another column, then the first column dominates the second one and is called the dominant column.

The bottom price of the game is called$$$\alpha = max_i min_j u_{ij}$ .
The top price of the game is called $$$\beta = min_j max_i u_{ij}$ .

Now we can formulate an algorithm for solving a game using the analytical method:

1. Calculate the bottom $$α and top$\alpha$$$β game prices.$\beta$ If a $$α = β , then write the answer in pure strategies, if not - continue the decision further$\alpha = \beta$
2. Remove dominant rows dominant columns. There may be several. In their place in the optimal strategy, the corresponding components will be equal to 0
3. Solve a matrix game using linear programming.

In order to give an example, you must provide a class that describes the solution.


And the class that performs the solution simplex method. Since I don’t understand mathematics, I used the ready implementation from Apache Commons Math


Now we will execute the decision by an analytical method. For clarity, we take another game matrix:

$$

$$\begin{pmatrix} 2& 4& 8& 5 \\ 6& 2& 4& 6\\ 3& 2& 5& 4 \end{pmatrix}$$

There is a dominant set in this matrix:
$$\begin{pmatrix} 2& 4\\ 6& 2\end{pmatrix}$$

Game solution $$( 0 , 33 ; 0 , 67 ; 0 ) with the price of the game equal to 3.33$(0,33; 0,67; 0)$

Instead of conclusion

I hope this article will be useful to those who need a first approximation with the decision of games with nature. Instead of conclusions link to GitHub .

I would be grateful for the constructive feedback!