Game Theory and its Influence on Randomized Algorithms || Trey Manuszak

Dec 14, 2022

In my last semester of graduate school, I attended a “Randomized and Approximation Algorithms” course. It was by far the most rigorous course in my graduate studies and reminded me a great deal of the difficulty of my courses I took during my undergrad in Mathematics. There was one particular topic in the randomized algorithms section that stood out as fascinating and profound. There is only one known method of lower bounding the expected performance of randomized algorithms and it comes from famous results in game theory. This particular section did not come easy to me as I had no experience with game theory. In fact, the whole course was an uphill battle as I had not done any of the three required prerequisites that are “Combinatorial Algorithms”, “Foundations of Algorithms”, and “Theory of Computation”. Most of the class relied HEAVILY on statistics, which I had not formally taken either. I saw the course as a final boss battle to test my limits. Anyway, I wanted to break down this interesting topic as I grappled with it as someone who tried to learn it with little foundational experience.

Game Theory Basics

Game theory provides a formal language for the representation and analysis of situations where several entities take rational actions that affect each other [Bonanno, 2018]. Imagine a game of rock, paper, scissors with the standard rules between two players, Robert and Charles. We can represent this game from the perspective of Robert as what is called a payoff matrix. Each row of the matrix represents a strategy available to Robert and each column represents a strategy available to Charles. For our payoff matrix $P$ which we can find in Figure 1, the component $P_{i,j}$ represents the amount that Charles pays to Robert when Robert chooses strategy $i$ and Charles chooses strategy $j$

		Charles
		Scissors	Paper	Rock
Robert	Scissors	$0$	$1$	$- 1$
	Paper	$- 1$	$0$	$1$
	Rock	$1$	$- 1$	$0$

Figure 1: Payoff matrix for normal rock, paper, scissors game. Robert's strategies are the rows and Charles strategies are the columns.

This is an example of what is called a two-person zero-sum game. That is, the net amount won by Robert and Charles is exactly zero.

Now, notice that Robert, the row player, wants to maximize the payoff, while Charles, the column player, wants to minimize the payoff. If neither player has information about what the opposing player wants to play, and Robert chooses strategy $i$ then he is guaranteed to win at least the smallest payoff in row $i$ no matter what Charles chooses. Similarly, if Charles chooses strategy $j$ then he is guaranteed to win at most the largest payoff in column $j$ no matter what Robert’s strategy is. Since Robert wants to maximize the payoff, an optimal strategy for Robert, we denote $\mathcal{O}_R$ is to choose the strategy $i$ that maximizes $\min_j P_{i,j}$ Similarly, since Charles wants to minimize the payoff, an optimal strategy for Charles, we denote $\mathcal{O}_C$ is to choose the strategy $j$ that minimizes $\max_i P_{i,j}$

In simpler terms, each player is choosing the strategy that satisfies their respective statement from the following:

Robert: For each row, find the smallest payoff. Choose the strategy that is the largest of these.
Charles: For each column, find the largest payoff. Choose the strategy that is the smallest of these.

The strategy chosen will be their optimal strategy. For Figure 1, we have $\mathcal{O}_R = -1$ and $\mathcal{O}_C = 1$ When these two are equal, the game is said to have a solution and the value of the game is $V = \mathcal{O}_R = \mathcal{O}_C$

Now, let’s change up the payoff matrix. Say we are playing rock, paper, scissors, where the payoff is denoted in Figure 2. In red, I have highlighted the smallest payoff in each row. Robert chooses the largest of these, which is underlined in his strategies. I have highlighted yellow in each column the largest payoff. Charles will choose the strategy with the smallest of these values, which is underlined in his strategies as well. Notice that now, this game has a solution of $V = 1$ It isn’t a very fun game for Charles, since the best he can do is always pay Robert $1, but it is the best option if forced to play. Neither player has any incentive to deviate from their strategy.

		Charles
		Scissors	Paper	Rock
Robert	Scissors	$1$	$2$	$3$
	Paper	$0$	$1$	$2$
	Rock	$- 1$	$0$	$1$

Figure 2: Payoff matrix for a rock, paper, scissors game with a solution.

Up until now, we have only considered what is called pure strategies. That is, choosing exactly one strategy and sticking to it. However, what if our strategy was chosen randomly from some distribution? This is called mixed strategies. If the payoff matrix $P$ is of dimension $n \times m$ then Robert’s probability distribution is a column vector $\boldsymbol{p} = (p_1, \dots, p_n)$ from which he will choose a strategy $i$ with probability $p_i$ Similarly, Charles’ probability distribution is a column vector $\boldsymbol{q} = (q_1, \dots, q_m)$ from which he will choose a strategy $j$ with probability $q_j$ Thus, we have

\begin{aligned} \mathcal{O}_R &= \max_{\boldsymbol{p}} \min_{\boldsymbol{q}} \boldsymbol{p}^T P \boldsymbol{q}, \\ \mathcal{O}_C &= \min_{\boldsymbol{q}} \max_{\boldsymbol{p}} \boldsymbol{p}^T P \boldsymbol{q}. \end{aligned}

Now, John von Neumann found the following theorem in his early work in game theory. In simple terms, it says that every two-person zero-sum game has a solution when using mixed strategies.

Theorem 1 von Neumann's Minimax Theorem

For any two-person zero-sum game specified by a payoff matrix $P$

\max_{\boldsymbol{p}} \min_{\boldsymbol{q}} \boldsymbol{p}^T P \boldsymbol{q} = \min_{\boldsymbol{q}} \max_{\boldsymbol{p}} \boldsymbol{p}^T P \boldsymbol{q}.

Shortly after, Lynn Loomis found that von Neumann’s theorem allowed for less strict strategies of play. It says in simple terms that for a two-person zero-sum game, having one player use a mixed strategy and the other use a pure strategy is sufficient for a solution to the game.

Theorem 2 Loomis' Pure-Strategy Form

For any two-person zero-sum game specified by a payoff matrix $P$

\max_{\boldsymbol{p}} \min_j \boldsymbol{p}^T P \boldsymbol{e}_j = \min_{\boldsymbol{q}} \max_i \boldsymbol{e}_i^T P \boldsymbol{q}.

Randomized Algorithms

Now, we have the necessary foundations of game theory set in place to start talking about its profound influence on randomized algorithms. First, I should note that a randomized algorithm can be modeled by a probabilistic Turing machine. That is, a Turing machine that also takes as input a tape of uniformly random bits. Or, it is a probability distribution on deterministic algorithms. Remember that, we’ll come back to this idea.

Why might we prefer a randomized algorithm? It is easy for an adversary to devise an input such that a deterministic algorithm performs in its worst-case. But, it will be difficult for an adversary to foil a randomized algorithm, as the steps of execution, and thus performance, will differ with each execution. When we analyze randomized algorithm performance, we usually want to bound its expected performance. Moreover, we usually show that it achieves this bound with high probability. Specifically, for a problem of size $n$ we say that some property is true with high probability if it is true with probability $1 - 1 / n^k$ for some constant $k \geq 1$

Now, Andrew Yao took the above ideas from Loomis and von Neumann and applied it to randomized algorithms in what is known famously as Yao’s minimax principle. The idea is this. Let the columns represent all deterministic algorithms that give a correct solution to the problem. The algorithm designer is selecting these strategies. Then, view the rows as the set of all possible inputs of fixed size. The adversary is selecting these inputs as their strategy to the game. For an input $x_i$ and an algorithm $A_j$ the performance of $A_j$ on input $x_j$ is $T(x_i, A_j)$ which is component $P_{i,j}$ of the payoff matrix. I say “performance” generally, because we may be measuring the complexity of the algorithm with respect to time, space, communication cost, etc. See Figure 3 for the pictorial representation of the game.

		Algorithm Designer
		$A_{1}$	$\dots$	$A_{m}$
Input Designer	$x_{1}$	$T (x_{1}, A_{1})$	$\dots$	$T (x_{1}, A_{m})$
	$⋮$	$⋮$	$⋱$	$⋮$
	$x_{n}$	$T (x_{n}, A_{1})$	$\dots$	$T (x_{n}, A_{m})$

Figure 3: Payoff matrix for a game between an algorithm designer and input designer, where the components are the performance of the algorithm chosen on the input chosen.

As before, the column player, the algorithm designer, wants to minimize the payoff. Likewise, the row player, the input adversary, wants to maximize the payoff. The optimal pure strategy for the algorithm designer is the optimal deterministic algorithm. An optimal pure strategy for the input adversary is a specific input. A mixed strategy for the algorithm designer is a Las Vegas randomized algorithm, or a randomized algorithm that always produces a correct answer. Remember, we require the columns to be deterministic algorithms that must provide a correct solution. A mixed strategy for the input adversary is a distribution on the inputs.

Listen up! This is the climax of the article and realization of Yao! Following the results of Theorem 1 and Theorem 2 above, we find that the expected performance of the best deterministic algorithm over the worst distribution of inputs is less or equal than the expected performance over the best distribution of all deterministic algorithms on the worst input. Yao’s minimax principle is mathematically defined in Theorem 3.

Theorem 3 Yao's Minimax Principle

Let $\Pi$ be a problem with a finite set $\mathcal{X}$ of fixed size input instances, and a finite set of deterministic algorithms $\mathcal{A}$ that give a correct result to $\Pi$ For input $X \in \mathcal{X}$ and algorithm $A \in \mathcal{A}$ let $T(X, A)$ denote the performance of algorithm $A$ on input $X$ For probability distributions $\boldsymbol{p}$ over $\mathcal{X}$ and $\boldsymbol{q}$ over $\mathcal{A}$ let $X_{\boldsymbol{p}}$ denote a random input chosen according to $\boldsymbol{p}$ and $A_{\boldsymbol{q}}$ dentoe a random algorithm chosen according to $\boldsymbol{q}$ Then, for all distributions $\boldsymbol{p}$ over $\mathcal{X}$ and $\boldsymbol{q}$ over $\mathcal{A}$

\min_{A \in \mathcal{A}} \mathbb{E} \left[ T(X_{\boldsymbol{p}}, A) \right] \leq \max_{X \in \mathcal{X}} \mathbb{E} \left[ T(X, A_{\boldsymbol{q}}) \right].

The RHS is the expected performance of our randomized algorithm on the worst possible input. Thus, to lower bound this complexity, we can choose a distribution $\boldsymbol{p}$ over the input space and prove a lower bound on the expected running time of deterministic algorithms for that distribution. One mistake I often made when attempting this lower bounding technique in the beginning is not realizing that Yao’s minimax principle implies that the best deterministic algorithm “knows” the distribution of inputs with which it is being tested on.

Applying Yao’s Minimax Principle

In this final section, I give an example of applying Yao’s minimax principle for finding a lower bound of a randomized algorithm’s performance. In this example, we will be bounding its expected running time. First, we note that the definition of a perfect matching on a graph $G = (V, E)$ with $|V| = n$ where $n$ is even, is a set of $n / 2$ edges, no two of which share a common vertex.

Problem 1

Consider a randomized algorithm that takes an $n$ -vertex graph as input and correctly determines if the graph has a perfect matching. At each step, the algorithm may ask a question of the form “Is there an edge between vertex $i$ and vertex $j$ The cost of asking the question is 1, and this is the only operation with a cost. The complexity $C(n)$ of the algorithm is the maximum over all $n$ -vertex graphs $G$ of the expected number of questions asked when the input graph is $G$ We want to prove $C(n) = \Omega(n^2)$

Proof.

To use Yao’s minimax principle, we want to construct an input distribution over all $n$ -vertex graphs such that any deterministic algorithm asks, on average, $\Omega(n^2)$ questions to determine if the input graph has a perfect matching. Let $P$ be the set of all graphs with perfect matchings on $n$ vertices. Let $Q$ be the set of all graphs with matchings of size $n / 2 - 1$ on $n$ vertices. We will create the input distribution so that we sample a graph from $P$ with probability $1 / 2$ and sample from $Q$ with probability $1 / 2$

Remember, a deterministic algorithm will know what this input distribution is, so sampling strictly from one of these sets with probability $1$ will allow the deterministic algorithm to solve the problem trivially. But, now that the deterministic algorithm does not immediately know the solution, it will deterministically ask if a fixed vertex, say $v_1$ is connected to any other vertex until it finds one. On average, this costs at least $n / 2$ questions. If we condition on the event that $v_1$ is connected to another vertex, say $v_2$ then the deterministic algorithm will check if a vertex, say $v_3$ which is different from $v_1$ and $v_2$ is connected to any of the remaining vertices. Remember, this is a deterministic algorithm, so it will have some predefined non-random logic for the order of selecting these vertices. This second step will take an average of at least $(n - 2) / 2$ questions. In general, the $k$ th step takes, on average, at least $(n - 2k) / 2$ questions, conditioned on the event that $k$ pairs of vertices have already been successfully matched.

Now, if we condition on the event that the input graph was sampled from $P$ then on average, it will take at least

\sum_{k = 0}^{\frac{n - 2}{2}}\frac{n - 2k}{2} = \Omega(n^2)

questions. Since we sampled from $P$ with probability $1 / 2$ then it also takes an average $C(n) = \Omega(n^2)$ questions.

References

Bonanno, G. (2018). Game Theory: Volume 1: Basic Concepts. North Charleston, SC: Createspace Independent Publishing Platform.

Motwani, R., & Raghavan, P. (1995). Randomized Algorithms. Cambridge, England: Cambridge University Press.