Game Theory

Please see edition equations online at https://www.routledge. com/Behavioral-Cybersecurity-Fundamental-Principles-and-Applications-of-Personality/Patterson-Winston-Proctor/p/book/ 9780367509798.

An important technique in the area of cybersecurity can be in the application of what we know as game theory (Morris, 1994; Von Neumann & Morgenstern, 1944).

For the purposes of this course, we will develop just an introductory exposition to game theory, notably what is now referred to as “two-person, zero-sum games.” The term zero-sum refers to the constraint that whatever one party gains in such a game, his or her opponent loses. Perhaps the simplest example of such a two-person zero-sum game involves the toss of a coin. The sides of the coin are labeled heads or tails, and one player tosses while the other guesses the outcome of the toss. Let’s call the players Mary and Norman and the results of the toss either H or T. Mary tosses the coin, and while it is in the air, Norman guesses the outcome. Clearly, there are four potential results in this game. In two-person game theory, we describe such a game by a matrix, with the rows of the matrix representing the choices for the first player and the columns the choices for the second. In this game, there are only two choices for each player, so we establish a 2 x 2 matrix.

Payoff

The “payoff” or outcomes are represented by values in the body of the 2 x 2 matrix. If we assume that if the first player guesses the result of the second player’s toss, he or she wins one unit of currency, say one dollar, then the entire game can be described as in this matrix.

By convention, we always label the row player’s positive outcome with a positive number; the column player interprets that value as a loss. So, in the aforementioned example, if Mary tosses heads and Norman guesses tails, then Mary wins a dollar. We enter a -1 in the T row for Norman—which Mary interprets as a +1 for her outcome.

More generally speaking, in such a game, each player knows in advance this payoff matrix, but game theory provides the analytical approach to enable each player to determine his or her best strategy.

In this example, the coin tosser does not have a strategy, but we could alter the game very slightly by saying that rather than conducting a toss, Mary would simply secretly choose one of her outcomes (H or T), and Norman would guess at the result, and then they would compare their choices.

In this model, each would develop a strategy to determine their choice, but a quick analysis would show that there is no winning strategy, as each player as a 50-50 chance of winning.

Suppose, however, that we create a game where the winning strategies might be different for each player. For example, with two players, each will call out either the number one or two. One player is designated as “odd”—let us say he is Oliver—the other player is “even,” and she will be known as Evelyn. If the result of the sum of each player’s call is odd, Oliver wins that amount; if the result of the sum is even, Evelyn wins that amount. Using the model described earlier for the game matrix, we have:

Rather than thinking of any game as a one-time event, consider what players would do if the game may be repeated. Each tries to develop a strategy whereby they can improve their chances. One “strategy” might be simply a random choice of their play, in which case in the aforementioned example, Oliver would choose “one” 50% of the time and “two” the other 50%. Evelyn would reason similarly.

In such a case, Oliver would lose two dollars half the time and win three dollars the other half if he chose “one”; in other words, 0.5(—2) + 0.5(3) = +0.5.

On the other hand, if Oliver chose “two” half the time, his result would be 0.5(3) + 0.5(-4) = -0.5. So, from Oliver’s perspective, he should just choose “one” all the time. But Evelyn, being no fool, would discern the strategy, choose “two” all the time, and thus win three dollars at each play. Therefore, in order for a game such as this to be competitive, each player must determine a strategy or a probability of each potential choice.

Suppose that Oliver chooses “one” 60% of the time (3/5) and “two” 40% of the time (2/5); then this strategy (assuming Evelyn plays randomly) will net him -2(3/5) + 3(2/5) = 0 when he calls “one,” and when he calls “two,” he wins 3(3/5) - 4(2/5) = 1/5. So, he breaks even over time when he calls “one” but wins 0.5 when he calls “two.”

Suppose we let p represent the percentage of times that Oliver calls “one.” We would like to choose p so that Oliver wins the same amount no matter what Evelyn calls. Now Oliver’s winnings when Evelyn calls “one” are -2p + 3(1 - p), and when Evelyn calls “two,” 3p - 4(1 - p). His strategy is equal when -2p + 3(1 - p) = 3p - 4(1 - p).

Solving for p gives 7/12, so Oliver should call “one” 7/12 = 58.3% of the time, and “two” 5/12 = 41.7% of the time. Then, on average, Oliver wins -2(7/12) + 3(5/12) = 1/12, or 8.3 cents every time, no matter what Evelyn does. This is called an equalizing strategy.

However, Oliver will only earn this if Evelyn does not play properly. If Evelyn uses the same procedure, she can guarantee that her average loss is 3(7/12) - 4(5/12) = 1/12. Because each is using their best strategy, the value 1/12 is called the value of the game (usually denoted V), and the procedure each player uses to gain this return is called the optimal strategy or the “minimax strategy.”

What we have just described is a mixed strategy. Where the choices among the pure strategies are made at random, the result is called a mixed strategy. In the game we have just described, the pure strategies “one” and “two” and the mixed strategy lead to the optimal with probabilities of 7/12 and 5/12.

There is one subtle assumption here. If a player uses a mixed strategy, he or she is only interested in the average return, not caring about the maximum possible wins or losses. This is a drastic assumption. Here we assume that the player is indifferent between receiving

$1 million for sure and receiving $2 million with probability one-half and zero with probability one-half. We justify this assumption arising from what is called utility theory (see Chapter 16). The basic premise of utility theory is that one should evaluate a payoff by its utility or usefulness and not its numerical monetary value. A player’s utility of money is not likely to be linear in the amount.

A two-person zero-sum game is said to be a finite game if both strategy sets are finite sets. Von Neumann has developed the fundamental theorem of game theory, called the Minimax Theorem, which states in particular: For every finite two-person zero-sum game, (1) there is a number V, called the value of the game; (2) there is a mixed strategy for player I such that I’s average gain is at least V no matter what player II plays; and (3) there is a mixed strategy for player II such that H’s average loss is at most V no matter what player I plays.

If V is zero, we say the game is fair; if V is positive, we say the game favors player I; and if V is negative, we say the game favors player II.

Matrix Games

To this point, we have only considered two-person games where there are only two pure strategies. Clearly, this is a severe restriction: in general, a player will have many pure strategy options.

More generally, a finite two-person zero-sum game can be described in strategic form as (X, Y, A). In this case, X equals the choice among m pure strategies for Player I, X = {x_b x₂, ..., x_m) and Y represents the n pure strategies for Player II, Y = {y,, y₂.....

y_n). With this terminology, we can form the payoff or game matrix with rows and columns corresponding to the choices of each player. [See “eresources: Equations and Problems” on the Website mentioned at the beginning of the chapter.]

In this form, Player I chooses a row i, Player II chooses a column j, and II pays I the entry in the chosen row and column, a^. The entries of the matrix are the winnings of the row chooser and losses of the column chooser.

Mixed Strategy

For player I to have a mixed strategy means that there is an m-tuple p with m distinct probabilities for the choices, p = {p,, p₂,..., p_m), with the additional restriction that the sum of the p, is 1.

We also denote the strategy for player II through the n-tuple of probabilities for player H’s choices. Again, the sum of the q_; probabilities must be 1.

The representation by the matrix A is a static description of the game. It merely gives the result if the row player chooses strategy x_s and the column player chooses y_j5 as the result or payoff is a^.

However, using matrix algebra, and considering the range of strategies available to each, the probabilities of choice by the row player can be described by a row vector of strategies p = [pi p₂ ... p_n], and the column player’s strategies by a column vector [q, q₂ ... q„]^T (where T represents the transpose, simply an easier way of writing the column player’s strategies).

The result of the pure strategy can be described as a special case of the mixed strategy by describing in the pure strategy case; the probability vector for the pure strategy is of the form [0 0 ... 1 ... 0], with the 1 in the ith position if the pure strategy is to choose the ith option, and similarly for the column player.

Given either a pure or a mixed strategy, our objective is to “solve” the game by finding one or more optimal strategies for each player. [See “eresources: Equations and Problems” on the Website mentioned at the beginning of the chapter.]

The row player’s strategies are p = [0.2 0.4 0.4], and the column player’s strategies are q=[0.1 0.4 0.5] (remember they must add up to 1). Then the average payoff for the row player is pAq.