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

May 16, 2026

Changelog

2026.05.16 Reworked the lower-bound claim to describe Yao's principle as a central general method rather than the only known method.
2026.05.16 Clarified the game-theory notation so maximin and minimax values are distinct from the strategies that attain them.
2026.05.16 Reframed Loomis' pure-strategy form as a best-response statement for fixed mixed strategies.
2026.05.16 Corrected the Yao minimax discussion and fixed notation/typos in the algorithm payoff matrix.
2026.05.16 Replaced the flawed perfect-matching proof with a rigorous bipartiteness query lower-bound example.

A figure facing a suspended network of glowing nodes.

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 the 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. One of the most useful general methods for lower bounding the expected performance of randomized algorithms 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 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 Robert is guaranteed to win at most the largest payoff in column $j$ no matter what Robert chooses. Since Robert wants to maximize the payoff, he looks for a row attaining the value

\mathcal{O}_R = \max_i \min_j P_{i,j}.

This is Robert’s maximin value. Similarly, since Charles wants to minimize the payoff, he looks for a column attaining the value

\mathcal{O}_C = \min_j \max_i P_{i,j}.

This is Charles’ minimax value.

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 whose smallest payoff is the largest.
Charles: For each column, find the largest payoff. Choose the strategy whose largest payoff is the smallest.

The row or column attaining these values is an optimal pure strategy for that player. For Figure 1, we have $\mathcal{O}_R = -1$ and $\mathcal{O}_C = 1$ When these two values are equal, the game is said to have a solution in pure strategies 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 finite 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}.

Later, Lynn Loomis gave an elementary proof of a closely related form of von Neumann’s theorem. The important idea for us is that, once one player fixes a mixed strategy, the opposing player’s best response can be chosen to be pure. This is because the expected payoff is linear in the opponent’s mixed strategy, and a linear function over a probability simplex reaches its optimum at an extreme point. Those extreme points are exactly the pure strategies.

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 can be viewed as 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 often want to bound its expected performance. In other settings, we may also show that a desired behavior occurs 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 them 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_i$ 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, but whose running time may vary with its random choices. 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 get the following lower-bound form of Yao’s minimax principle. For any input distribution and any randomized algorithm, the expected cost of the best deterministic algorithm against that input distribution is at most the worst-case expected cost of the randomized algorithm. 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}}$ denote 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. If we choose the best possible hard distribution, the full finite minimax principle says this lower-bound method can be tight. One mistake I often made when attempting this lower bounding technique in the beginning is not realizing that Yao’s minimax principle allows the best deterministic algorithm to “know” the distribution of inputs with which it is being tested.

Applying Yao’s Minimax Principle

In this final section, I give an example of applying Yao’s minimax principle for finding a lower bound on a randomized algorithm’s performance. My original version of this article tried to use perfect matching for this example. Perfect matching does have deep and important query-complexity lower bounds, but a correct proof is more involved than the proof I gave. I will use bipartiteness instead, because the same Yao idea can be shown cleanly on the page.

Problem 1

Consider a randomized algorithm that takes an $n$ -vertex graph as input and always correctly determines if the graph is bipartite. 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)$

1 / 8

Keep the two possible inputs on screen:

G_{0}

is bipartite, while

G_{0} + e

differs by one hidden within-part edge

e

. At the start, the shared query transcript is empty.

Proof.

To use Yao’s minimax principle, we want to construct an input distribution over $n$ -vertex graphs such that any deterministic algorithm asks, on average, $\Omega(n^2)$ questions to determine if the input graph is bipartite. Assume $n$ is even, and split the vertex set into two known parts $L$ and $R$ each of size $n / 2$

Let $G_0$ be the complete bipartite graph between $L$ and $R$ This graph is bipartite. Let $S$ be the set of all possible edges with both endpoints inside $L$ or both endpoints inside $R$ These are exactly the edges that would violate this particular bipartition. The size of $S$ is

|S| = 2 \binom{n / 2}{2} = \frac{n(n - 2)}{4} = \Omega(n^2).

Now define the input distribution $\mathcal{D}$ as follows:

With probability $1 / 2$ return $G_0$
With probability $1 / 2$ choose a uniformly random edge $e \in S$ and return $G_0 + e$

The first case is bipartite. The second case is not bipartite. To see this, suppose $e = \{u, v\}$ lies inside $L$ Since $G_0$ is complete bipartite, for any $w \in R$ the edges $\{u, w\}$ and $\{v, w\}$ already exist. Then $u, v, w$ form a triangle. The same argument works if $e$ lies inside $R$ A graph with a triangle cannot be bipartite.

Now consider any deterministic algorithm that is correct on every graph. It knows the distribution $\mathcal{D}$ and it knows the partition $L \cup R$ We will show that it must ask $\Omega(n^2)$ questions on average when the input is drawn from $\mathcal{D}$

Focus on what happens when the input is $G_0$ If the algorithm ever outputs “bipartite” before querying every edge in $S$ then there is some unqueried edge $e \in S$ But the algorithm’s transcript on $G_0$ is identical to its transcript on $G_0 + e$ because the only changed edge is one it never asked about. The algorithm would therefore also output “bipartite” on $G_0 + e$ which is incorrect. So, on the input $G_0$ every correct deterministic algorithm must query every edge in $S$ before it can safely answer.

Since the distribution $\mathcal{D}$ returns $G_0$ with probability $1 / 2$ the expected number of queries made by any correct deterministic algorithm under $\mathcal{D}$ is at least

\frac{1}{2}|S| = \frac{n(n - 2)}{8} = \Omega(n^2).

By Theorem 3, this lower bounds the worst-case expected number of queries made by any zero-error randomized algorithm for the same problem. Thus $C(n) = \Omega(n^2)$

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.

Yao, A. C. (1977). Probabilistic computations: Toward a unified measure of complexity. Proceedings of the 18th IEEE Symposium on Foundations of Computer Science, 222-227.