# Rationalizability, Iterated Dominance, and the Theorems of Radon and
Carathéodory

Roy Long University of Chicago Economics
Originally written February 2022. This version January 2024

(February 2022

_Stanford Economic Review 2024_ )

###### Abstract

The game theoretic concepts of rationalizability and iterated dominance are
closely related and provide characterizations of each other. Indeed, the
equivalence between them implies that in a two player finite game, the
remaining set of actions available to players after iterated elimination of
strictly dominated strategies coincides with the rationalizable actions. I
prove a dimensionality result following from these ideas. I show that for two
player games, the number of actions available to the opposing player provides
a (tight) upper bound on how a player’s pure strategies may be strictly
dominated by mixed strategies. I provide two different frameworks and
interpretations of dominance to prove this result, and in doing so relate it
to Radon’s Theorem and Carathéodory’s Theorem from convex geometry. These
approaches may be seen as following from point—line duality. A new proof of
the classical equivalence between these solution concepts is also given.

##  1 Introduction

Strategic dominance is a standard concept in game theory. It encapsulates the
intuition that in a strategic environment, one should never take some action
$a$ if in all possible scenarios (formally, all profiles of the other players’
actions), another action $a^{\prime}$ does strictly better.

In this section, we review the concepts of dominance and rationalizability,
and summarize the content of the paper.

We consider finite, two player strategic games. For $i=1,2$, player $i$’s
(pure) strategies is the set of actions $A_{i}$.

Definition: A pure strategy for player $i$, $a_{i}\in A_{i}i$ is strictly
dominated by another pure strategy $a_{i}^{\prime}$ if
$u_{i}(a_{i},a_{-i})<u_{i}(a_{i}^{\prime},a_{-i})$ for any $a_{-i}.$

Dominance can be generalized to mixed strategies, where players randomize over
actions. In this case, the expected payoff is compared.

Definition: A (pure) strategy $a_{i}\in A_{i}$ is strictly dominated by a
mixed strategy $s_{i}$ over the set $\\{a_{j}\\}$ if
$u_{i}(a_{i},a_{-i})<U_{i}(s,a_{-i})=\sum_{j}p_{j}u_{i}(a_{j},a_{-i})$ for all
$a_{-i}$ where $(p_{j})$ is a probability distribution over $\\{a_{j}\\}$
specified by $s.$

If the game is finite, the iterated elimination of strictly dominated
strategies may be performed. The simple algorithm is to repeatedly remove
strategies (for either player) which are strictly dominated by some mixed
strategy from the game, until no such strategies are left. It is easy to show
that the set of remaining strategies are those that were not strictly
dominated in the original game, and any strictly dominated strategy is removed
by this process.

More recently, the solution concept of rationalizability was developed. For
two player games the definition is as follows:

Definition: An action $a_{i}\in A_{i}$ is not rationalizabile if for any
belief $q=(q_{1},\ldots,q_{m})$ player $i$ has about player $(-i)$’s strategy
$s_{-i},$ there exists some other action $a_{i}^{\prime}\in A$ (which may
depend on $q$) such that $U_{i}(a_{i},s_{-i})<U_{i}(a_{i}^{\prime},s_{-i})$

One can also give a recursive definition of $k$-level rationalizability
($k\in\mathbb{N}$), and repeatedly remove strategies that are not
rationalizable until all remaining actions are rationalizable.

It is easy to show that any strictly dominated strategy is not rationalizable,
as one intuitively expects. It turns out that the converse is true as well,
which was first shown in 1984 independently by both Bernheim [1] and Pearce
[2].

######  Theorem 1.1.

(Pearce, Bernheim). Given a finite, two player strategic game $G,$ the set of
(pure) strategies that remain after iterated elimination of strictly dominated
strategies are precisely the strategies that are rationalizable in $G.$

###### Proof.

See Appendix. ∎

Bernheim’s proof represents strategies as payoff vectors in $\mathbb{R}^{d}$
and uses the separating hyperplane theorem. Pearce’s proof uses the minimax
theorem for zero sum games. See Fudenberg [3] or Yildiz [4] for a presentation
of the former and Obara [5] for the latter.

The central result of this paper is $\textbf{Theorem 2.1}.$ We prove a tight
bound on the minimum number of strategies needed to form a mixed strategy that
strictly dominates another strategy. There is a rich connection to convex
geometry in our analysis, and there are several representations of dominance
and rationalizability that lead to classical results in this area of
mathematics.

The methods in section 2 also yield a new proof of Theorem 1.1, mirroring the
separating hyperplane proof of the equivalence. We defer our proof to the
appendix.

In section 2, we provide a proof of Theorem 2.1 using Radon’s Theorem
motivated by a natural view of the equivalence between rationalizability and
dominance. We also show that the bound still holds when a player can have
infinitely many actions.

In section 3, we represent dominance using vectors in $\mathbb{R}^{d}.$ We
give another proof of $\textbf{Theorem 2.1},$ and discuss the mathematical
connections between the two proofs.

We may also the two approaches as resulting from a kind of point—line duality.
In section 3, we view strategies as payoff vectors (or points), while in
section 2, strategies are represented by hyperplanes.

##  2 Connections to Convex Geometry

We study the following question: Given a two player finite strategic game $G$
with action sets $A,B,$ suppose some player’s (without loss of generality
player 1) pure strategy $a_{i}\in A$ is strictly dominated by a mixed strategy
on a set of actions $\\{a_{j}\\}=A^{\prime}\subseteq A.$ Can we bound the size
of the support of this mixed strategy, $|A^{\prime}|$?

An obvious bound is $|A^{\prime}|\leq|A|,$ and furthermore
$|A^{\prime}|\leq|A|-1,$ as if $a_{i}\in A^{\prime}$ then $a_{i}$ is still
dominated by some mix on $A^{\prime}\setminus\\{a_{i}\\}.$

Interestingly, it turns out that we actually can bound $|A^{\prime}|$ by the
number of actions available to player 2, i.e. $|B|.$ This is not at all
obvious.

More precisely, we have the following result:

######  Theorem 2.1.

Let $G$ be a finite two player game, where player $1$’s set of actions is $A$
and player $2$’s set of actions is $B.$ If $a_{i}\in A$ is strictly dominated
by a mix of strategies over $\\{a_{j}\\}\subseteq A,$ then in fact $a_{i}$ is
strictly dominated by a mixed strategy $\\{a_{j}^{\prime}\\}$ consisting of at
most $\min(|A|,|B|)$ actions. An analogous bound holds for player $2.$

######  Remark 2.2.

The bound for player 1 can be improved to $\min(|A|-1,|B|)$ based on the
simple observation above. In fact, we will show that this bound is tight.

Now the result for player 1 is trivial if $|A|\leq|B|,$ but it is not
immediately clear why such a result should be true otherwise. Why does the
number of actions the opponent has affect (and moreover provides a bound on)
how a player’s pure strategies are dominated by mixes of their own strategies?

For example, if player $2$ has $|B|=4$ available actions and player $1$ has
$|A|=10$ available actions, then this tell us that if some action $a_{i}\in A$
of player $1$ is strictly dominated, it’s in fact dominated by some set of
just $4$ of player $1$’s available actions.

When $|B|=m=1$, it is trivial, as player $2$ only has one action that she must
play. When $m=2,$ this tells us that if a pure strategy is strictly dominated,
either it is dominated by another pure strategy or by a mix of two strategies.

Henceforth, we assume von Neumann Morgenstern preferences, i.e. preferences
over strategies are compared based on their expected payoffs.

To motivate this theorem, we start by first examining the case for $m=2.$
Consider the simple $3\times 2$ game, with the payoffs as listed, where rows
are player $1^{\prime}s$ actions and columns are player $2^{\prime}s$ actions.

1 $\backslash$ 2 |  L |  R
---|---|---
U |  (6,1) |  (0,3)
M |  (2,1) |  (5,0)
D |  (3,2) |  (3,1)

Figure 1: payoff matrix

Then if player $1$ has belief $(q,1-q)$ over $\\{L,R\\}$ about player $2$’s
strategy, then player $1$’s expected payoffs by playing $U,M,D$ are,
respectively:

$E_{U}=6q$
$E_{M}=2q+5(1-q)=5-3q$
$E_{D}=3$

By plotting these as graphs on the domain $q\in[0,1],$ we can see that for
every $q\in[0,1],$ the $E_{D}(q)$ is less than at least one of $E_{U}(q)$ and
$E_{M}(q).$ rationalizability then tells us that $D$ is strictly dominated by
some mixed strategy of $U$ and $M.$

Let $E_{U}=f_{1},E_{M}=f_{2},E_{D}=f_{3}$ for ease of notation. Since these
functions are all linear and therefore convex, their maximum is also convex.
So by taking the upper convex hull of the lines, ie. $f_{MAX}=\max_{1\leq
i\leq 3}\\{f_{i}\\},$ the graph of $f_{3}$ lies entirely below the upper
convex hull $f_{MAX}$ and is strictly dominated by it.
Now let’s look at a different game, where player $2$ again has two actions
$B=\\{b_{1},b_{2}\\}$, and suppose player $1$ has five actions
$\\{a_{1},\ldots,a_{5}\\}$ corresponding to the following expected payoffs for
player 1, if she has belief $(q,1-q)$ over $\\{b_{1},b_{2}\\}$:

$E_{1}(q)=1.2q+0.4$
$E_{2}(q)=-1.3q+1.3$
$E_{3}(q)=0.5q+0.8$
$E_{4}(q)=-0.8q+1$
$E_{5}(q)=0.8.$

The graph below shows the expected payoffs of these strategies as a function
of the belief $q\in[0,1],$ where the black curve is $E_{2},$ the green curve
is $E_{4},$ the horizontal purple curve is $E_{5},$ the positive sloping
purple curve is $E_{1},$ and the blue curve is $E_{3}.$

Figure 2: expected payoffs given beliefs

We can see that $a_{4}$ and $a_{5}$ are strictly dominated by
$a_{1},a_{2},a_{3}$ as
$E_{4}(q),E_{5}(q)<\max\\{E_{1}(q),E_{2}(q),E_{3}(q)\\}$ for all $0\leq q\leq
1.$ For example, $a_{4}$ is strictly dominated by a mix over
$a_{1},a_{2},a_{3}$ with mixed strategy $q=(0.2,0.3,0.5),$ which results in an
expected payoff of
$0.2(1.2q+0.4)+0.3(-1.3q+1.3)+0.5(0.5q+0.8)=0.1x+0.87>0.8=E_{5}(q)$ for all
$q\in[0.1]$, and $a_{5}$ is strictly dominated by a mix over
$a_{1},a_{2},a_{3}$ with mixed strategy $q=(0.2,0.7,0.1)$ which results in an
expected payoff of
$0.2(1.2q+0.4)+0.7(-1.3q+1.3)+0.1(0.5q+0.8)=1.07-0.62q>-0.8q+1$ for all
$q\in[0,1].$

Notice that in both cases, we only need to choose two out of the three to
guarantee a mixed strategy that strictly dominates them. For example, if we
consider a mix over with $a_{1},a_{2}$ with probability distribution
$(0.3,0.7),$ then the expected payoff is
$0.3(1.2q+0.4)+0.7(-1.3q+1.3)=1.03-0.55q>-0.8q+1=E_{4}(q)$ for all
$q\in[0,1].$ Similarly, $a_{5}$ can be dominated by mixes over just
$\\{a_{1},a_{2}\\},$ as well as a mix of $\\{a_{2},a_{3}\\}.$ Graphically, we
see that for a strictly dominated action, we can choose just two of the graphs
of other functions such that the maximum of them lies strictly above the
dominated strategies’ graph.

Unfortunately, there are some edge cases where strict dominance never happens
and the graph of every $f_{i}$ is part of the upper convex hull $\max f_{i}$
at some point.

Thus, the equivalence of rationalizability and elimination of dominated
strategies gives us the following result:

######  Proposition 2.3.

(Theorem 2.1 for $d=2$) Let $f_{1},f_{2},\ldots,f_{k}:[0,1]\to\mathbb{R}$ be
linear, i.e. $f_{i}(x)=a_{i}x+b_{i}$ for all $i,$ and $q\in[0,1].$ Suppose
$g:[0,1]\to\mathbb{R}$ is also linear and satisfies: for all $x\in[0,1],$ the
$\max_{i}(f_{i}(x))>g(x).$ Then there exists weights $0\leq
r_{1},\ldots,r_{k}\leq 1$ such that $r_{1}+\cdots+r_{k}=1$ and $\sum
r_{i}f_{i}(x)>g(x)$ for all $x\in[0,1].$ In fact, it is possible to choose the
$r_{i}$ such that all but at most two of them are $0.$

In other words, if the graph of an action’s expected payoff lies strictly
below the upper convex hull (i.e. it’s strictly dominated), it is in fact
strictly dominated by a mix over a set of at most two actions.

###### Proof.

The first part of the statement follows from the equivalence of
rationalizability and iterated dominance, so we show the second part. First,
note that we may assume that $g(x)=0$ for $x\in[0,1],$ as we consider
$f_{i}^{\prime}(x)=f_{i}(x)-g(x)$ for all $i,$ which are still linear
functions and the condition becomes $\max_{i}f_{i}^{\prime}>0$ with
$g^{\prime}=0.$

First, remove all functions $f_{i}$ where $f_{i}(x)\leq g(x)$ for all
$x\in[0,1]$, as they will never be part of the upper convex hull. Now, for the
graphs of the remaining functions, either they intersect the graph of $g$ or
they don’t. If they don’t, then they lie entirely above $g,$ i.e.
$f_{k}(x)>g(x)$ for all $x\in[0,1]$, and we can just let $r_{k}=1$ and all
other $r_{i}=0.$

Otherwise, they have a unique intersection point. For simplicity, as we noted
above, we may assume $g$ is zero. Then, we can look at where each $f_{k}$
intersects $[0,1]$ on the $x$-axis. Let $L$ be the leftmost $x$-intercept in
$[0,1]$ such that the corresponding $f$ has positive slope, and $R$ be the
rightmost $x$-intercept in $[0,1]$ such that the corresponding $f$ has
negative slope. Then, it’s easy to see that $L<R$ because otherwise $\max f$
is not greater than zero at points between $L$ and $R$, so it reduces to only
having two functions $f_{1},f_{2},$ where $f_{1}=a_{1}(x+b_{1})$ and
$f_{2}=a_{2}(x+b_{2})$ where $a_{1}>0,a_{2}<0$ and $0\leq b_{1}<b_{2}\leq 1.$

Then, we have $r_{1}f_{1}+r_{2}f_{2}=r_{1}a_{1}(x+b_{1})+r_{2}a_{2}(x+b_{2})$,
and by setting $r_{1}a_{1}=-r_{2}a_{2}$, we just get a constant function which
is greater than zero ($r_{1}f_{1}+r_{2}f_{2}$ goes through the intersection
point of $f_{1},f_{2}$ which lies above the $x$-axis.) ∎

Notice that in the last step of the previous proof, we didn’t need to
explicitly construct the function $r_{1}f_{1}+r_{2}f_{2}.$ In fact, the
equivalence of rationalizability and iterated strict dominance tells us if the
graph of $g(x)$ is strictly below the upper convex hull formed by some set of
$f_{i},$ then $g$ is strictly dominated by those $f_{i},$ so in particular,
we’re guaranteed that such $r_{i}$ exists for the corresponding $f_{i}$ that
make the weighted sum greater than $g.$ The main result of the previous proof
was that we only needed to choose two of the $f_{i}$ and it would be
sufficient that the $\max f_{i}$ over those two functions would be greater
than zero at all points.

Now, we generalize the preceding intuition to higher dimensions, i.e. when
player $2$ has more than two actions. In essence, what we did in the previous
proof was this: after subtracting $g$ from all the $f_{i},$ we were left with
graphs of linear functions whose overall maximum is strictly greater than $0,$
i.e. their upper convex hull lies strictly the $x$-axis. Then, we looked at
all linear functions that intersected $[0,1].$ We can assume this because if
the linear function had an $x$-intercept outside of $[0,1],$ then its
restriction to $[0,1]$ will clearly be positive. Thus, we only needed to
consider the cases of positive and negative slope that intersected $[0,1].$
Then, if a positive sloped line intersected $[0,1]$ at $x_{0},$ the
$\max_{i}f_{i}(x)>0$ for all $x>x_{0},$ and if a negative sloped line
intersected $[0,1]$ at $x_{0},$ we know $\max_{i}f_{i}(x)>0$ for all
$x_{0}<0.$

Thus, the problem is reduced to: given a set of $1$-dimensional rays or half
lines that cover $[0,1],$ we want to show that there exists a subset of at
most two of them that also covers $[0,1].$

$0$$1$ Figure 3: Covering of $[0,1]$ by half-lines

In general, a belief player $1$ can have about player $2$ where player $2$ can
choose from $m$ possible actions $b_{1},\ldots,b_{m}$ is an $m$-tuple
$(q_{1},\ldots,q_{m})\in[0,1]^{m}$ where $\sum_{i=1}^{m}q_{i}=1.$
Letting $q_{m}=1-q_{1}-\cdots-q_{m-1},$ the set of possible beliefs is
represented by the $m-1$-dimensional simplex $S^{m-1}$ (including its
interior) of points $x=(x_{1},\ldots,x_{m-1})\in[0,1]^{m-1}$ where
$\sum_{i=1}^{m-1}x_{i}\leq 1.$ For example, when $m=2,$ this is just the line
segment $[0,1].$ When $m=3,$ this is the closed triangle region bounded by the
$x$-axis, the $y$-axis, and the line $x+y=1.$ When $m=4,$ it is a tetrahedron
with vertices at $(0,0,0),(1,0,0),(0,1,0),(0,0,1),$ and so forth.

Let us examine this for the $d=3$ case. We can plot the mixed strategies
(beliefs) of player $2$ in $q_{1}$-$q_{2}$ space, which is $S^{2},$ the right
isosceles triangle in $\mathbb{R}^{2}$ bounded by $q_{1},q_{2}\geq
0,q_{1}+q_{2}\leq 1.$ Then, the expected payoff for player $1$ by choosing
action $a_{i},$ with belief $q=(q_{1},q_{2},q_{3}=1-q_{1}-q_{2}),$ is a
function $f_{i}:S^{1}\subset[0,1]^{2}\to\mathbb{R}$ defined by
$f(q_{1},q_{2})=a_{i,1}q_{1}+a_{i,2}q_{2}+a_{i,3}(1-q_{1}-q_{2}).$ Thus, the
graph of $f_{i}$ is the restriction of a plane to $S^{1}.$

Finally, we have the graph of $g,$ which is also a plane. Again, we can
consider $f^{\prime}=f-g,$ and the resulting functions are still planes, so we
have $\max\\{f^{\prime}(x)\\}>0$ for all $x\in S^{1}.$ Now, each of the planes
$f_{i}^{\prime}$ will intersect the plane $\mathbb{R}^{2}\times\\{0\\}$ at
some line $l$ in the $q_{1}$-$q_{2}$ plane. First, if any $f_{i}^{\prime}$ is
parallel to $\mathbb{R}^{2}$, then clearly it is constant and strictly greater
than zero, and so that single function $f_{i}>g$ for all $x\in S^{2}$. This
means that the pure strategy $a_{i}$ strictly dominates $g$ so we may ignore
this case. The cross sections will be lines that intersect the closed simplex
$S^{2}$ (i.e. the closed triangle with vertices $(0,0),(0,1),(1,0)$) and we
will have open half planes $h_{1},h_{2},\ldots,h_{k}$ that cover $S^{2}.$

So in the general case, each action $a_{i}$ has an expected utility
$f_{i}:S^{m-1}\to\mathbb{R}$ whose graph is a $m-1$ dimensional hyperplane in
$\mathbb{R}^{n},$ restricted to the domain $S^{m-1}.$ After taking a
transformation $f_{i}^{\prime}=f_{i}-g,$ the condition turns into
$\max\\{f_{i}^{\prime}\\}>0.$ Then, each hyperplane $f_{i}^{\prime}$
intersects $\mathbb{R}^{m-1}\times{0}$, which cuts $\mathbb{R}^{m-1}$ into two
half spaces, where one of the (open) half spaces represents the set of points
where $f_{i}^{\prime}>0$, and the other (closed) half space represents the set
of points where $f_{i}^{\prime}\leq 0.$ Of course, we only care about the
intersection of the half spaces with the domain
$S^{m-1}\subset\mathbb{R}^{m-1}.$

(0, 1)(0, 0)(1, 0) Figure 4: A partial covering of $S^{2}$ with half planes

We are thus left with the following problem:

######  Proposition 2.4.

(Theorem 2.1, geometric form) Let $Q\subset\mathbb{R}^{d}$ be a
$d$-dimensional convex polytope (including its boundary and interior). Suppose
a set of open half spaces $h_{1},h_{2},\ldots,h_{n}$ covers $Q.$ Then, there
exists a subset of at most $d+1$ of these $h_{i}$ that also cover $Q.$

The key observation is that we want to remove redundant half spaces. If a half
space covers a region that is also covered by another set of half planes, then
we can remove the first half plane and the covered region will be the same. A
half space being covered by another half space corresponds to dominance by a
pure strategy. Being covered by a set of half spaces corresponds to being
dominated by a mixed strategy. We define a minimal configuration to be one
where no half plane can be removed and the remaining half planes still cover
the polytope, i.e. each half plane contains a point that is uniquely covered
by it.

First, we gain some intuition for this result by showing it for $d=3,$ i.e. a
covering of $S^{2}$ with half planes.

######  Proposition 2.5.

(Theorem 2.1 for $d=3$) Let $Q\subset\mathbb{R}^{2}$ be a closed convex
polygon including its interior. Suppose $n$ open half planes covers $Q.$ Then,
there exists a subset of at most $3$ half planes that cover $Q.$

###### Proof.

Suppose for contradiction that there exists a covering of the polygon $Q$ with
half planes $\\{h_{i}\\}$ such that any subset of $\\{h_{i}\\}$ that also
coves $Q$ contains at least four planes. Consider any minimal configuration
$\\{h_{j}^{\prime}\\}\subset\\{h_{i}\\}$ that covers $Q.$ By assumption,
$|\\{h_{j}\\}|\geq 4.$

Since $\\{h_{j}^{\prime}\\}$ is minimal, we cannot remove any
$h\in\\{h_{j}^{\prime}\\}$ to get a smaller subset of half planes that also
covers $Q.$ Thus, for every $h_{j}^{\prime},$ there exists some point
$p_{j}\in Q$ that is only covered by $h_{j}^{\prime}.$

Thus, we have four points $p_{1},p_{2},p_{3},p_{4}\in Q$ such that $p_{j}$ is
uniquely covered by $h_{j}^{\prime}$ for all $1\leq j\leq 4.$

There are a few possible configurations. We check the cases based on the
convex hull $H$ of $p_{1},p_{2},p_{3},p_{4}.$

Suppose $H$ is a line segment, i.e. $p_{1}p_{2}p_{3}p_{4}$ are collinear, in
that order. Then, we’ve just reduced it to the $d=2$ one dimensional case, as
each plane bisects the line at some intersection point and covers everything
to one side. So we see that there must be some plane that covers at least two
points as there are more than two planes.

Now suppose $H$ is a triangle, say $H=\triangle p_{2}p_{3}p_{4}.$ Then $p_{1}$
lies in $\triangle p_{2}p_{3}p_{4}.$ If $p_{1}$ lies strictly in the interior
of $\triangle p_{2}p_{3}p_{4},$ then clearly any half planes that cover
$p_{1}$ also intersect $\triangle p_{2}p_{3}p_{4},$ and we see that one of
those vertices are necessarily covered as well. (If the plane doesn’t cover
any of the three vertices, then the entire triangle lies on the other side of
the plane and is also not covered so $p_{1}$ is not covered, which can’t
happen.)

If $p_{2}$ lies on the boundary (one of the sides) of $\triangle
p_{2}p_{3}p_{4},$ then we need to be a bit careful but the same result holds
as in the previous subcase.

Finally, suppose $H$ contains all four points $p_{1},p_{2},p_{3},p_{4},$ so
the points form a non-degenerate convex quadrilateral, without loss of
generality $p_{1}p_{2}p_{3}p_{4}$ in clockwise order. Then, note that
$p_{1}p_{3}$ intersects $p_{2}p_{4}$ at some point $x$ inside $H,$ and again
we see that any point that covers $x$ also covers at least two of the vertices
of $H,$ so this case is covered.

The result follows, i.e. any covering of $S^{2}$ with $n$ half planes contains
a subcover using at most three half planes. ∎

For the general case in $\mathbb{R}^{d},$ we utilize Radon’s Theorem, which
states:

######  Theorem 2.6.

(Radon) Let $P$ be a set of $n\geq d+2$ distinct points in $\mathbb{R}^{d}.$
Then, $P$ can be partitioned into two nonempty subsets $V_{1}$ and $V_{2}$
such that the convex hulls of $V_{1}$ and $V_{2}$ intersect.

###### Proof.

See appendix. ∎

For the general case in $\mathbb{R}^{d},$ let $Q\subset\mathbb{R}^{d}$ be a
convex polytope (i.e. including the boundary and interior). Suppose there are
$n\geq d+2$ half spaces $h_{1}\ldots h_{n}$ which cover $Q,$ such that each
half space contains a point $p_{i}\in Q$ that is only covered by $h_{i}.$

By Radon’s Theorem (as $n\geq d+2$), we can partition
$P=\\{p_{1},\ldots,p_{n}\\}$ into two sets $P_{1}$ and $P_{2}$ such that their
convex hulls $H(P_{1}),H(P_{2})$ intersect. Consider a point $x\subset
H_{1}(P_{1})\cap H(P_{2})$ in this intersection, which lies in the original
polytope $Q$ by convexity: as $P_{1},P_{2}\subset P\subset Q,$ we have
$H(P_{1}),H(P_{2})\subset H(P)\subset H(Q)=Q.$

However, $x$ cannot be covered by any $h_{i}$ with corresponding $p_{i}$ in
$P_{1},$ as $x$ is in $H_{2},$ and so any such $h_{i}$ would have to intersect
$H_{2}$ and contain some other point in $P_{2}.$ Analogously $x$ cannot be
covered by any $h_{i}$ with $p_{i}$ in $P_{2}.$ So $x\in Q$ is not covered by
$\bigcup h_{i},$ which is a contradiction. This uses the fact that for an open
half space, if a set of points all lie on the other side, then their convex
hull also lies entirely on the other side.

So letting $Q=S^{n-1},$ the $n-1$-dimensional simplex, we have proven Theorem
2.1. $\blacksquare$

An immediate result of Theorem 2.1 is that it gives us a characterization of
which actions can be removed by iterated strict dominance, i.e. which ones are
rationalizable. Indeed, as we’ve shown, if $f_{i}$ lies under the upper convex
hull of $f_{1},\ldots,f_{m},$ then $f_{i}$ is strictly dominated. In practice,
we should be able to solve this with linear programming. If $f_{i}$ is part of
the upper convex hull at any point $q\in S^{m-1},$ then $f_{i}(q)\geq
f_{k}(q)$ for all $1\leq k\leq m,$ so no mixed strategy beats $f_{i}$ with
belief $q.$ Finally, we point out the case of weak dominance. When $m=2,$ it’s
easy to see that either the graph of the function lies strictly below the
upper convex hull, coincides with the upper convex hull on some set that
contains an interval, or intersects the upper convex hull exactly at a single
point. The last case is when the action is weakly dominated. For $m=3,$ we see
that weak dominance can result in a weak set (where the graph of the function
coincides with the upper convex hull) of a point or a line, and so forth.

We also note that Theorem 2.1 still holds even if one player has infinitely
many actions.

######  Corollary 2.7.

Let $G$ be a two player game where player $2$ has a finite number of actions
$B=\\{b_{1},\ldots,b_{m}\\}$, and player $1$ has infinitely many actions
$A=\\{a_{i}\\}_{i\in I}$ for some index set $I.$ Then, if some action $a_{i}$
is strictly dominated by a mixed strategy over a set of actions
$\\{a_{j}\\}=A^{\prime}\subset A,$ in fact $a_{i}$ is strictly dominated by a
mixed strategy over a finite set of at most $m$ actions.

###### Proof.

We simply note that we are covering $Q=S^{n-1}$ with open half spaces
$h_{a_{j}},$ and since $Q$ is compact (closed and bounded), $\bigcup_{a_{j}\in
A^{\prime}}h_{a_{j}}$ forms an open cover of $Q,$ so there exists a finite
subcollection $a_{1}^{\prime},a_{2}^{\prime},\ldots,a_{k}^{\prime}\in
A^{\prime}$ such that $\bigcup_{a_{j}^{\prime}\in
A^{\prime}}h_{a_{j}^{\prime}}$ also covers $Q.$ Then by the previous result,
we again know that there exists a subset of at most $m$ of these
$h_{a_{j}^{\prime}}$ that covers $Q,$ and we are done. ∎

##  3 A Linear Algebra Perspective

Now, let us turn to a completely different representation of dominance. This
approach yields a more natural, geometric, interpretation of Theorem 2.1,
which can be seen fundamentally as a dimensionality result.

Again suppose player $2$ has $m$ actions $b_{1},\ldots,b_{m}.$ We view the
payoffs for player $1$ as a matrix $A=(a_{ij})$ (linear transformation), and
each action $a_{i}$ as a row vector $v_{i}=(a_{i,1},\ldots,a_{i,m}).$

Assuming von-Neumann Morgenstern Preferences, by taking a positive affine
transformation, we may first transform the matrix to $A^{\prime}=A+cJ$, where
$J$ is the $n\times m$ matrix with all $1$’s and $c$ is a positive constant,
so that all coordinates are strictly positive.

We view each payoff action as a vector in $\mathbb{R}^{m}.$ Then, if we play a
mixed strategy over some actions $\\{a_{j}\\}$ with probabilities
$\\{p_{j}\\},$ then in vector form this represents $\sum p_{j}v_{j},$ where
$\sum p_{j}=1.$

In other words, if we take the convex hull of all the $v_{j},$ along with the
origin, the possible mixed strategies over these vectors is represented by the
outer boundary $B$ of the convex hull $H.$

Similarly, we see that the convex polytope formed by taking the convex hull of
the vectors is exactly the region

$\left\\{\sum_{i=1}^{m}\lambda_{i}v_{i}\mid
0\leq\lambda_{1},\ldots,\lambda_{m}\leq 1\text{ and
}\sum_{i=1}^{m}\lambda_{i}\leq 1\right\\},$

i.e. the region contained by the affine hull of the vectors
$v_{1},\ldots,v_{m}.$

The natural connection here is that the characterization of probability
distributions over $m$ elements using the simplex and the linear algebra
formulation of convex hull of points using linear combinations are very
similar, which leads to a re-interpretation of the probabilities/weights as
coefficients of vectors.

With this formulation in mind, we now prove several preliminary results about
strict dominance.

######  Proposition 3.1.

A pure strategy $a_{i}$ is strictly dominated by another pure strategy $a_{j}$
if and only if the $k$th component of $v_{i}$ is strictly less than the $k$th
component of $v_{i}$ for all $1\leq k\leq m.$

###### Proof.

First, suppose that for some strategies $a_{i},a_{j},$ that $a_{i,k}<a_{j,k}$
for all components $1\leq k\leq m.$ Clearly for any belief
$q=(q_{1},\ldots,q_{m})\in[0,1]^{m},\sum q_{k}=1$ we have
$\sum_{k=1}^{m}q_{k}(a_{i,k}-a_{j,k})<0$ because each term is less than or
equal to zero and not all of them are zero, so
$\sum_{k=1}^{m}q_{k}a_{i,k}<\sum_{k=1}^{m}q_{k}a_{j,k},$ i.e.
$E(a_{i})<E(a_{j}),$ and $a_{i}$ is strictly dominated by $a_{j}.$

Now, suppose $v_{i}=(a_{i,1},\ldots,a_{i,m})$ is strictly dominated by
$v_{j}=(a_{j,1},\ldots,a_{j,m}).$ Then, for all possible beliefs
$q=(q_{1},\ldots,q_{m}),$ we must have
$\sum_{k=1}^{m}q_{k}a_{i,k}<\sum_{k=1}^{m}q_{k}a_{j,k},$ so
$\sum_{k=1}^{m}q_{k}(a_{i,k}-a_{j,k})<0.$ By letting
$q=(1,0,\ldots,0),(0,1,0,\ldots,0),\ldots,(0,\ldots,0,1),$ we see that
$a_{i,k}<a_{j,k}$ for all $1\leq k\leq m.$ ∎

It turns out that more generally, if we consider strict dominance by a mixed
strategy, we can treat the mixed strategy as a pure strategy vector and
compare them as if we were comparing two pure strategies’ vectors. This leads
us to the following proposition.

######  Proposition 3.2.

Consider a mixed strategy over actions $\\{a_{j}\\}$ with probability
distribution $\\{\lambda_{j}\\},$ which we represent as
$u=\sum\lambda_{j}v_{j}.$ Then, a pure strategy $a_{i}$ is strictly dominated
by the mixed strategy over $\\{a_{j}\\}$ if and only if the $k$th component of
$v_{i}$ is strictly less than the $k$th component of $u,$ i.e. $v_{i}$ is
strictly dominated by the pure strategy vector representation of $\\{a_{j}\\}$
with lottery $\\{\lambda_{j}\\}.$

###### Proof.

Let $q\in[0,1]^{m}$ be any belief player $1$ can have about player $2$’s
possible strategy. Then, the expected payoff with the pure strategy $a_{i}$ is
simply the dot product $E(a_{i})=\langle v_{i},q\rangle,$ and the expected
payoff by playing the mixed strategy is

$E(\\{a_{j}\\})=\sum\lambda_{j}\langle
v_{j},q\rangle=\sum\langle\lambda_{j}v_{j},q\rangle=\left\langle\sum\lambda_{j}v_{j},q\right\rangle=\langle
u,q\rangle,$

as with probability $\lambda_{j},$ player $1$ plays action $a_{j},$ in which
case the expected payoff is $\langle v_{j},q\rangle.$ Thus, we see that
$E(a_{i})<E(\\{a_{j}\\})$ if and only if $\langle v_{i},q\rangle<\langle
u,q\rangle$ for all possible beliefs $q,$ which from the previous claim is
equivalent to the components of $v_{i}$ being strictly less than the
components of $u.$ ∎

Now, we can start classifying which types of pure strategies are dominated by
a mix over other strategies. Let’s look at a set of pure strategies
$\\{a_{j}\\}$ with corresponding vectors $\\{v_{j}\\}.$ For example, consider
the four vectors in $\mathbb{R}^{2}$ as below. Then, a good geometric
intuition for whether a vector $v$ is strictly dominated by some mix over
$\\{v_{j}\\}$ is if the vector is contained in the convex hull formed.

For example, consider the following payoffs for player $1$ in a game where
player $2$ has two actions and player $1$ has three actions. A =
$\begin{pmatrix}1&5\\\ 5&1\\\ 2&2\\\ \end{pmatrix}$

We see that $a_{3}=(2,2)$ is strictly dominated by a mix of over $a_{1},a_{2}$
with equal probability for both actions, i.e. the mixed vector is
$v^{\prime}=\frac{1}{2}(1,5)+\frac{1}{2}(5,1)=(3,3)$ which strictly dominates
$(2,2).$

If we graph them, we see that $(2,2)$ lies between (inside) the vectors
$(1,5)$ and $(5,1),$ i.e. the point $(2,2)$ lies inside the convex hull or
triangle with vertices $(0,0),(1,5),(5,1).$ So a good intuitive guess is that
points that lie within the convex hull formed by the vectors $(1,5),(5,1)$
will be dominated by some mix of the two.

$x$$y$mixed strategiesdominating (2, 2)(1, 5)(5, 1)(2, 2) Figure 5: vector
representation of dominance

And indeed, this easily follows from the previous claims.

######  Proposition 3.3.

If a strategy vector $v_{i}$ lies inside the convex hull (affine hull) of the
vectors $H\left(\bigcup v_{j}\right)$ (but not on the outer faces/boundary),
then the corresponding strategy $a_{i}$ is strictly dominated by a mix over
$\\{a_{j}\\}.$

###### Proof.

By the linear combination definition of convex hull, this means that we can
write $v_{i}=\sum\lambda_{j}v_{j},$ where $0\leq\lambda_{j}\leq 1$. Remove all
vectors that have trivial contribution so we may assume that all
$\lambda_{j}>0.$ Note that $\sum\lambda_{j}=s<1$ as the the vector $v_{i}$
does not lie on the outer boundary of the convex hull, so we may extend
$v_{i}$ to a vector $u=\lambda v_{i}$ with $\lambda>1$ that intersects the
outer boundary of the convex hull.

In particular, let
$u=\sum\lambda_{j}^{\prime}v_{j}=\sum\frac{\lambda_{j}}{s}v_{j}$ which
represents a mixed strategy of $\\{a_{j}\\}$ with probability distribution
$\\{\lambda_{j}/s\\}$ as $\sum\frac{\lambda_{j}}{s}=1.$ Note that
$\lambda_{j}<\frac{\lambda_{j}}{s}$ for all terms in the sum. Then have

$E(\\{a_{j}\\})=\langle
u,q\rangle=\left\langle\sum\frac{\lambda_{j}}{s}v_{j},q\right\rangle>\langle\sum\lambda_{j}v_{j},q\rangle=\langle
v,q\rangle=E(a_{i}),$

and $a_{i}$ is dominated by this mix over $\\{a_{j}\\}$ as claimed. ∎

######  Proposition 3.4.

(Characterization of strategies that are strictly dominated by a mix over a
given set)
Let $\\{v_{j}\\}$ be a set of pure strategy vectors corresponding to the
actions $\\{a_{j}\\}.$ Consider the boundary $B,$ or the affine hull of the
$\\{v_{j}\\}$ defined by

$B=\left\\{\sum\lambda_{j}v_{j}:0\leq\lambda_{j}\leq
1,\sum\lambda_{j}=1\right\\},$

which represents the set of all possible mixed strategies over $\\{a_{j}\\}.$
Then the set

$X_{B}=\bigcup_{b\in B}\\{v:v_{(k)}<b_{(k)}\,\forall\,1\leq k\leq m\\}$

defines the set of pure strategies that are strictly dominated by some mix of
$\\{a_{j}\\}.$ i.e. $v$ is strictly dominated by a mix over $\\{v_{j}\\}$ if
and only if $v\in X_{B}.$

Figure 6: covering of green convex hull by blue triangles

Before using this characterization to provide another proof of Theorem 2.1,
let us return to the case of points that lie strictly within the convex hull
of some set of actions’ vectors. We will use this to find an elegant and
natural interpretation of Theorem 2.1. For now, we work with the closed convex
hull (i.e. including the boundary $B$). The result is the same for open hull
in the case of points that lie strictly within $H.$

Let’s look at four points $v_{1},v_{2},v_{3},v_{4}.$ as shown below.

Then, the region of vectors that are strictly dominated by a mix of
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ is the region on the following page.

We can also look at the pairs of vectors, which bound triangular regions
(above right).

These triangular regions represent the regions that are strictly dominated by
two vectors. More specifically, the convex hulls are a subset of what points
are strictly dominated by that set of vectors.

Now, the motivation for Theorem 2.1 becomes clear: the polygon region formed
by the convex hull of the vectors $\\{v_{1},v_{2},v_{3},v_{4}\\}$ is equal to
the union of the convex hulls of pairs of the vectors.

Figure 7: convex hull is covered by the union of triangles over all pairs of
vectors

Formally, if $H(S)$ denotes the convex hull of a set of points $S,$ then our
preceding observation is:

$\displaystyle H(O,v_{1},v_{2},v_{3},v_{4})$
$\displaystyle=H(O,v_{1},v_{2})\cup H(O,v_{1},v_{3})\cup
H(O,v_{1},v_{4})\cup\ldots\cup H(O,v_{3},v_{4})$ $\displaystyle=\bigcup_{1\leq
i,j\leq 4}H(O,v_{i},v_{j})$

Similarly, if we have have $n$ points in $\mathbb{R}^{3},$ i.e.
$v_{1},\ldots,v_{n}$ in $\mathbb{R}^{3},$ it’s easy to see that taking the
union over all triples of points, i.e.
$H(O,v_{1},\ldots,v_{n})=\bigcup_{i,j,k}H(O,v_{i},v_{j},v_{k})$ yields the
entire convex hull. This is very intuitively clear. We are essentially
considering all tetrahedrons with a fixed vertex $O$, and by shifting the
vertices around, we use these tetrahedra to cover the entire interior of the
polyhedra.

More generally, a non-degenerate set of $d+1$ points in $\mathbb{R}^{d}$
should determine a $d$-dimensional figure, and by varying across different
points in the set, we should be able to cover all $d$-dimensional points in
the convex hull, which is the following statement: Given $n$ nonzero points
$v_{1},\ldots,v_{n}$ in $\mathbb{R}^{d},$ representing vectors extending from
$O,$ then we have:
$H(O,v_{1},\ldots,v_{n})=\bigcup_{S_{d}\in\binom{[n]}{d}}H(O,v_{k_{1}},\ldots,v_{k_{d}}),$
where $S_{d}$ varies over all subsets of
$[n]=\\{1,\ldots,n\\}$ with $d$ elements.

It is now easy to show that the generalization of our intuitive observation
follows from $\textbf{Carathéodory's Theorem}.$

######  Theorem 3.5.

(Carathéodory) If a point $x\in\mathbb{R}^{d}$ lies in the convex hull of a
set $P,$ then $x$ can be written as the convex combination of at most d + 1
points in $P.$ i.e. there is a subset $P^{\prime}\subset P$ consisting of
$d+1$ or fewer points such that $x\in H(P^{\prime}).$

###### Proof.

See appendix. ∎

For our proof, we need a variant known as Conical Carathéodory’s Theorem

######  Theorem 3.6.

(Carathéodory’s Theorem for Conical Hull) Let $n\geq d+1$ and
$v_{1},\ldots,v_{n}$ be $n$ distinct nonzero vectors in $\mathbb{R}^{d}.$
Consider the conical hull formed by this set. Then, if a nonzero point $x$ is
in the conical hull, $x$ can be written as the conical combination of at most
$d$ of the $v_{i}.$

###### Proof.

See appendix. ∎

######  Corollary 3.7.

Furthermore, if $x$ also lies in the convex hull $H(O,v_{1},\ldots,v_{n}),$
i.e. $x$ is a convex combination of the $v_{i}$ (and $O=0,$ so sum of
coefficients of the $v_{i}$ is less than or equal to one), then $x$ can be
written as the convex combination of at most $d$ of the $v_{i},$ and $O.$

###### Proof.

See appendix. ∎

Finally, we can finish the second proof of $\textbf{Theorem 2.1}.$ Let
$v_{1},\ldots,v_{n}$ be the vector payoffs for player $1.$ Let
$H=H(O,v_{1},\ldots,v_{n})$ be the convex hull of the set of vectors, and let
$B$ be the outer boundary of $H.$

From the characterization of these points, we know that a vector
$v\in\mathbb{R}^{n}$ is strictly dominated by a mix over a subset of
$\\{v_{j}\\}=v_{1},\ldots,v_{n}$ if and only if there exists some $b\in B$
such that $v_{(k)}<b_{(k)}$ for all components $1\leq k\leq m.$ But $B\subset
H,$ and we know from the corollary following Carathéodory’s Theorem that all
points in $H$ can be represented as the affine sum of at most $d$ distinct
vectors. Thus, if $v_{i}$ is strictly dominated by some such $b,$ we can write
$b$ as the affine linear combination of at most $d$ of the $\\{v_{j}\\},$
which means that $v_{i}$ is strictly dominated by a mix over those $v_{j},$
and in particular, is dominated by at most $d$ of the other vectors as
claimed. $\blacksquare$

We conclude by showing that the bound in Theorem 2.1 is tight in the following
sense:

######  Proposition 3.8.

For every pair $(n,m)\in\mathbb{Z}^{2}_{\geq 2}$ there exists a game $G_{n,m}$
with $|A|=n$ and $|B|=m,$ and a strategy $a_{i}\in A$ that is strictly
dominated by a mixed strategy over a set $\\{a_{j}\\}=A^{\prime}$ of size
$|A^{\prime}|=\min(|A|-1,|B|),$ and $a_{i}$ is not strictly dominated by a
mixed strategy over any smaller set of actions. An analogous statement holds
for player 2.

###### Proof.

We again represent pure strategies in their vector forms, with a pure strategy
$a_{i}$ is associated to a vector $v_{i}\in\mathbb{R}^{m},$ and a mixed
strategy over $\\{a_{j}\\}$ associated to a convex combination
$\sum_{j}\lambda_{j}v_{j}.$

First suppose $|A|-1<|B|.$ Then, consider

$\displaystyle v_{1}$ $\displaystyle=(n,0,0,\ldots,0,1,\ldots,1)$
$\displaystyle v_{2}$ $\displaystyle=(0,n,0,\ldots,0,1,\ldots,1)$
$\displaystyle v_{3}$ $\displaystyle=(0,0,n,\ldots,0,1,\ldots,1)$
$\displaystyle\ldots$ $\displaystyle v_{n-1}$
$\displaystyle=(0,0,0,\ldots,n,1,\ldots,1)$ $\displaystyle v_{n}$
$\displaystyle=(1,1,1,\ldots,1,0,\ldots,0)$

where the $k$-th coordinate of $v_{k}$ is $n$ and the $j$-th coordinate is
zero for $1\leq j\leq n-1$ and is one for $j\geq n,$ for each $1\leq k\leq
n-1,$ and the first $n-1$ coordinates of $v_{n}$ are zero. Then, we see that
$v_{n}$ is strictly dominated by the mixed strategy

$\tfrac{1}{n-1}v_{1}+\tfrac{1}{n-1}v_{2}+\cdots+\tfrac{1}{n-1}v_{n-1}=(\tfrac{n}{n-1},\tfrac{n}{n-1},\ldots,\tfrac{n}{n-1},1,\ldots,1)\gg(1,1,1,\ldots,1,0,\ldots,0),$

but $v_{n}$ is clearly not strictly dominated by a mixed strategy over any
smaller set as each $v_{k}$ for $1\leq k\leq n-1$ is needed in the mixed
strategy.

Now, suppose that $|B|\leq|A|-1.$ Then, consider

$\displaystyle v_{1}$ $\displaystyle=(2m,0,0,\ldots,0)$ $\displaystyle v_{2}$
$\displaystyle=(0,2m,0,\ldots,0)$ $\displaystyle v_{3}$
$\displaystyle=(0,0,2m,\ldots,0)$ $\displaystyle\ldots$ $\displaystyle v_{m}$
$\displaystyle=(0,0,0,\ldots,2m)$ $\displaystyle v_{m+1}$
$\displaystyle=(1,1,1,\ldots,1)$ $\displaystyle v_{k}$
$\displaystyle=(0,0,0,\ldots,0)\,\,\,\forall m+1<k\leq n$

We see that $v_{m+1}$ is strictly dominated by the mixed strategy

$\tfrac{1}{m}v_{1}+\tfrac{1}{m}v_{2}+\cdots+\tfrac{1}{m}v_{m}=(2,2,2,\ldots,2)\gg(1,1,1,\ldots,1),$

but $v_{m}$ is clearly not strictly dominated by any mixed strategy over a set
of $m-1$ or fewer actions, as $v_{k}$ for $k\geq m+2$ are all zero vectors,
and each $v_{k}$ for $k\leq m$ is needed as $v_{k}$ is the only vector that
has a positive $k$-th coordinate.

∎

##  4 Appendix

The appendix provides proofs of Caratheodory’s and Radon’s Theorems, as well
as a new proof of Theorem 1.1 using the representation of dominance in section
2 and half-spaces.

We begin the proof of Theorem 1.1 with the following covering lemma.

######  Lemma 4.1.

(Rotation covering) Suppose two half spaces $a\cdot x<0$ ($A$) and $b\cdot
x<0$ ($B$) together cover a compact convex set $S$ in $\mathbb{R}^{n}$. Then
there exists $\lambda\in[0,1]$ such that the half space $C$ given by $(\lambda
a+(1-\lambda)b)\cdot x<0$ also covers $S.$

###### Proof.

Suppose neither $A$ nor $B$ covers $S$ by itself so $\lambda\in(0,1).$ Also
assume that $a$ and $b$ are not parallel (linearly dependent) as that case can
be easily handled.

Thus the hyperplanes $a\cdot x=0$ and $b\cdot x=0$ intersect at an $n-2$
dimensional subspace $P.$ Note that $P$ lies entirely outside of $S.$

These two hyperplanes divide $\mathbb{R}^{n}$ into four quadrant regions based
on the signs of $a\cdot x$ and $b\cdot x.$ For the region where $a\cdot x<0$
and $b\cdot x<0$ clearly $(\lambda a+(1-\lambda)b)\cdot x<0.$ So consider the
other two regions. The parts of $S$ in them are $S_{A}=(S\cap A)\setminus B$
and $S_{B}=(S\cap B)\setminus A$ which lie in two different quadrants. By
assumption that neither $A$ nor $B$ alone cover $S,$ both $S_{A},S_{B}$ are
nonempty. Also $S_{A},S_{B}$ are compact and convex.

Consider the plane $C_{\lambda}$: $(\lambda a+(1-\lambda)b)\cdot x=0$ as
$\lambda$ increases from zero to one. Note that $C_{0}$ intersects $S_{A}$ and
$C_{1}$ intersects $S_{B}.$ Suppose for contradiction that $C_{\lambda}$
always intersects at least one of $S_{A}$ and $S_{B}.$ As $S_{A},S_{B}$ are
both closed, this means for some $\lambda^{*}$ the plane intersects both
$S_{A}$ and $S_{B},$ say at points $p$ and $q.$

We claim that the line segment $\overline{pq}$ intersects $P.$ Note that
$C_{\lambda^{*}}\subset P\cup Q_{1}\cup Q_{2}$ where $Q_{1}=\\{x:a\cdot x\geq
0,b\cdot x<0\\}$ and $Q_{2}=\\{x:b\cdot x\geq 0,a\cdot x<0\\}$ where we used
$\lambda\in(0,1).$ Since $p\in Q_{1},q\in Q_{2},$ as as we move from $p$ to
$q$ along the segment, the signs of $a\cdot x$ and $b\cdot x$ each change
(from nonnegative to negative, or vice versa). But this can only happen at
$P$, which means that $\overline{pq}$ intersects $P$ at some point $z.$

However as $p,q\in S$, by convexity, this means $z\in S.$ This contradicts the
fact that $P$ does not intersect $S.$ ∎

######  Theorem 4.2.

(Equivalence of rationalizability and dominance) Given a finite, two player
strategic game $G,$ the set of (pure) strategies that remain after iterated
elimination of strictly dominated strategies are precisely the strategies that
are rationalizable in $G.$

###### Proof.

It is easy to show that any strictly dominated strategy is not rationalizable,
so we focus on the reverse implication. As before, let player 1 have
strategies $\\{a_{1},\ldots,a_{m}\\}$ and we denote by
$S^{n}=\\{x\in\mathbb{R}^{n}\mid x_{1}+\cdots+x_{n}=1,x_{i}\geq 0\,\,\forall
i\\}$ the $n-1$ dimensional simplex of probability vectors where $n$ is the
number of actions of player 2. Thus, a belief player 1 has about player 2 is
some $q\in S^{n}.$

As in the framework of section 2, we can represent each pure strategy $a_{j}$
as a linear function $f_{j}:S^{n}\to\mathbb{R},$ whose image is a restricted
hyperplane in $\mathbb{R}^{n+1}$. Suppose the pure strategy $a_{i}$
represented by $f_{i}=g$ is not rationalizable. Again by taking
$f_{j}^{\prime}=f_{j}-g$ for all $j$ we may assume that $g$ is identically $0$
on $S^{n}$. For a slight abuse of notation, in the following we write $a_{i}$
to mean the payoff vector $(a_{i,1},\ldots,a_{i,n})$, so the expected payoff
of playing the $i$-th action under belief $q$ is $f_{j}(q)=a_{i}\cdot q$.

For a given $f_{j}$ the set of beliefs $q$ for which $a_{j}$ yields strictly
higher payoff than $a_{i}$ are those that satisfy $f_{j}(q)=a_{j}\cdot q>0$,
ie. the intersection of an open half-space in $\mathbb{R}^{n}$ with $S^{n}.$
Let this half-space be $H_{j}$.

If $a_{i}$ is a never best response, then the union of these $H_{j}$ over all
$j\neq i$ must cover $S^{n}$ entirely. Similarly, for a mixed strategy
$\sigma=r_{1}a_{1}+\cdots+r_{m}a_{m}$, the beliefs for which $\sigma$ yields
higher payoff than $a_{i}$ are those $q$ satisfying
$(r_{1}a_{1}+\cdots+r_{m}a_{m})\cdot q>0$, which is also a half-space
$H_{\sigma}$. Then, $\sigma$ strictly dominates $a_{i}$ iff the half-space
$H_{\sigma}$ covers $S^{n}$.

The proof of the theorem follows from Lemma 4.2, which allows us to repeatedly
replace a pair of (pure or mixed) strategies with a single mixed strategy,
such that the union of the remaining half-spaces still covers $S^{n}$. This
reduces the number of strategies while maintaining the covering invariant.
Eventually, the process terminates with a single half-space $H^{*}$ that
covers $S^{n}$ by itself, which corresponds to a mixed strategy $\sigma$ that
dominates $a_{i}$.

Indeed, suppose we have $m-1$ half spaces $p_{j}\cdot x<0\,$ $(H_{j})$ for
$j\in[m]\setminus\\{i\\}$ in $\mathbb{R}^{n}$ each representing a pure
strategy $a_{j}$, and their union covers the compact convex set of probability
vectors $S^{n}$. We can now take two half spaces $p_{1}\cdot x<0$ and
$p_{2}\cdot x<0$ and since $H_{1}\cup H_{2}$ covers the convex compact set
$S^{n}\setminus(H_{3}\cup\cdots\cup H_{m})$, there exists some $\lambda$ such
that the half space $(\lambda p_{1}+(1-\lambda)p_{2})\cdot x<0$ covers
$S^{n}\setminus(H_{3}\cup\cdots\cup H_{m}),$ and we can replace $H_{1},H_{2}$
with this halfspace instead. Thus, we have reduced the total number of half
spaces while still covering $S^{n}.$ Iterating this process, we eventually
have a single half space of the form
$\lambda_{1}a_{1}+\cdots+\lambda_{m}a_{m}<0$ which covers $S^{n}.$ Since we
take convex combinations in each step, the weights are such that
$\lambda_{1}+\cdots+\lambda_{m}=1$ with all $\lambda_{i}\geq 0$, so this
defines a mixed strategy $\sigma$ which strictly dominates $a_{i}$.

∎

######  Theorem 4.3.

(Radon) Let $P$ be a set of $n\geq d+2$ distinct points in $\mathbb{R}^{d}.$
Then, $P$ can be partitioned into two nonempty subsets $V_{1}$ and $V_{2}$
such that the convex hulls of $V_{1}$ and $V_{2}$ intersect.

###### Proof.

Consider any set $X=\\{x_{1},\ldots,x_{d+2}\\}\subset\mathbb{R}^{d}$ of $d+2$
points.

Then there exists multipliers $a_{1},\ldots,a_{d+2}$, not all zero, such that:

$\sum_{i=1}^{d+2}a_{i}x_{i}=0,\,\,\,\,\,\,\,\,\,\,\sum_{i=1}^{d+2}a_{i}=0.$

Take some particular nontrivial solution $a_{1},\ldots,a_{d+2}$. Let
$Y\subseteq X$ be the set of points with positive multipliers and
$Z=X\setminus Y$ be the set of points with negative or zero multiplier.
Observe that $Y$ and $Z$ forms a partition of $X$ into two subsets with
intersecting convex hulls.

Indeed, $H(Y)$ and $H(Z)$ necessarily intersect because they each contain the
point

$p=\sum_{x_{i}\in Y}\frac{a_{i}}{A}x_{i}=\sum_{x_{i}\in
Z}\frac{-a_{i}}{A}x_{i},$

where $A=\sum_{x_{i}\in Y}a_{i}=-\sum_{x_{i}\in Z}a_{i}$. So we have expressed
$p$ as convex combination of points in $Y$ and also as a convex combination of
points in $Z$, which means that $p$ lies in the intersection of the convex
hulls.

∎

######  Theorem 4.4.

(Carathéodory) If a point $x\in\mathbb{R}^{d}$ lies in the convex hull of a
set $P,$ then $x$ can be written as the convex combination of at most d + 1
points in $P.$ i.e. there is a subset $P^{\prime}\subset P$ consisting of
$d+1$ or fewer points such that $x\in H(P^{\prime}).$

###### Proof.

Suppose $x$ can be written as a convex combination of $k>d+1$ of the points
$x_{i}\in P.$ Without loss of generality, they are $x_{1},\ldots,x_{k}.$ Thus,
we can write $x=\sum_{j=1}^{k}\lambda_{j}x_{j},$ where $0<\lambda_{j}\leq 1$
and $\sum_{j=1}^{k}\lambda_{j}=1.$

Then, consider $x_{2}-x_{1},\ldots,x_{k}-x_{1},$ which is a linearly dependent
set, so there exists $\mu_{j}$ for $2\leq j\leq k$ not all zero such that
$\sum_{j=2}^{k}\mu_{j}(x_{j}-x_{1})=0$ and not all are zero. Then, if we set
$\mu_{1}=-\sum_{j=2}^{k}\mu_{j},$ this means that
$\sum_{j=1}^{k}\mu_{j}x_{j}=0$ as well as $\sum_{j=1}^{k}\mu_{j}=0,$ and not
all of the $\mu_{j}$ are equal to zero, so there exists some $\mu_{j}>0.$

Now let $\alpha=\min_{1\leq j\leq
k}\left\\{\frac{\lambda_{j}}{\mu_{j}}:\mu_{j}>0\right\\}=\frac{\lambda_{i}}{\mu_{i}}.$
Note that $\alpha>0.$ Then, we have
$x=\sum_{j=1}^{k}\lambda_{j}x_{j}-\alpha\sum_{j=1}^{k}\mu_{j}x_{j}=\sum_{j=1}^{k}(\lambda_{j}-\alpha\mu_{j})x_{j}$.
Since $\alpha>0,$ then $\lambda_{j}-\alpha\mu_{j}\geq 0$ for all $j.$
Also,
$\sum_{j=1}^{k}(\lambda_{j}-\alpha\mu_{j})=\sum_{j=1}^{k}\lambda_{j}-\alpha\sum_{j=1}^{k}\mu_{j}=1-\alpha\cdot
0=1.$
However, by definition, $\lambda_{i}-\alpha\mu_{i}=0.$ Thus, $x=\sum_{1\leq
j\leq k,j\neq i}(\lambda_{j}-\alpha\mu_{j})x_{j},$ where every
$\lambda_{j}-\alpha\mu_{j}$ is non-negative and their sum is one.

In other words, $x$ is a convex combination of $k-1$ points in $P.$ Repeating
this process, we can write $x$ as a convex combination of at most $d+1$ points
in $P,$ as desired. ∎

######  Theorem 4.5.

(Carathéodory’s Theorem for Conical Hull) Let $n\geq d+1$ and
$v_{1},\ldots,v_{n}$ be $n$ distinct nonzero vectors in $\mathbb{R}^{d}.$
Consider the conical hull formed by this set. Then, if a nonzero point $x$ is
in the conical hull, $x$ can be written as the conical combination of at most
$d$ of the $v_{i}.$

###### Proof.

Suppose $x$ is expressed as the conical combination of $k>d$ of the $v_{i},$
without loss of generality, $v_{1},\ldots,v_{k}.$ Then,
$x=\sum_{j=1}^{k}\lambda_{j}v_{j},$ where $\lambda_{j}>0$ for all $1\leq j\leq
k.$ Since $k>d,$ then $v_{1},\ldots,v_{k}$ is linearly dependent, so there
exists $\mu_{j},$ not all equal to zero, such that
$\sum_{j=1}^{k}\mu_{j}v_{j}=0.$ By multiplying each $\mu_{j}$ by $-1$ if
necessary, we can ensure that at least one of these $\mu_{j}$ must be
positive. Without loss of generality, we may also assume that
$\sum_{j=1}^{k}\mu_{j}\geq 0$ because if the sum were less than zero (then
there would exist some negative $\mu_{j}),$ we could multiply each $\mu_{j}$
by $-1.$ Now, note that for any $\alpha,$ we have
$\sum_{j=1}^{k}(\lambda_{j}-\alpha\mu_{j})v_{j}=\sum_{j=1}^{k}\lambda_{j}v_{j}-\alpha\sum_{j=1}^{k}\mu_{j}v_{j}=x.$
We want to choose some $\alpha$ such that $\lambda_{i}-\alpha\mu_{i}=0$ for
some $i,$ and all $\lambda_{j}-\alpha\mu_{j}\geq 0.$

Indeed, if we let $\alpha=\min_{1\leq j\leq
k}\left\\{\frac{\lambda_{j}}{\mu_{j}}:\mu_{j}>0\right\\}=\frac{\lambda_{i}}{\mu_{i}}>0,$
then we do have $\lambda_{j}-\alpha\mu_{j}\geq 0$ for all $j.$ If $\mu_{j}\leq
0,$ then since $\lambda_{j}>0,$ we have $\lambda_{j}-\alpha\lambda_{j}\geq 0.$
And if $\mu_{j}>0,$ we have
$0<\alpha=\frac{\lambda_{i}}{\mu_{i}}\leq\frac{\lambda_{j}}{\mu_{j}},$ and
again $\lambda_{j}-\alpha\lambda_{j}\geq 0.$ Thus,
$x=\sum_{j=1}^{k}(\lambda_{j}-\alpha\mu_{j})v_{j}$ represents a conical
combination using at most $k-1$ of the $v_{i},$ as all
$\lambda_{j}-\alpha\mu_{j}\geq 0,$ and $\lambda_{i}-\alpha\mu_{i}=0.$ We can
repeat this process until we are left with at most $d$ of the $v_{i},$ and so
$x$ is the conical combination of at most $d$ of the $v_{i}$ as desired. ∎

######  Corollary 4.6.

Furthermore, if $x$ also lies in the convex hull $H(O,v_{1},\ldots,v_{n}),$
i.e. $x$ is a convex combination of the $v_{i}$ (and $O=0,$ so sum of
coefficients of the $v_{i}$ is less than or equal to one), then $x$ can be
written as the convex combination of at most $d$ of the $v_{i},$ and $O.$

###### Proof.

If $x$ lies in the convex hull $H(O=v_{0},v_{1},\ldots,v_{k})$, that means
that $x=\sum_{j=0}^{k}\lambda_{j}v_{j},$ where $\lambda_{j}>0$ and
$\sum_{j=0}^{k}\lambda_{j}=1.$ Since $O=0,$ this is the same as saying that
$\sum_{j=1}^{k}\lambda_{j}\leq 1.$ Again, if $k>d,$ then we can write
$\sum_{j=1}^{k}\mu_{j}v_{j}=0,$ where we can assume that
$\sum_{j=1}^{k}\mu_{j}\geq 0.$ But then in the preceding proof, we have that
$\sum_{j=1}^{k}(\lambda_{j}-\alpha\mu_{j})=\sum_{j=1}^{k}\lambda_{j}-\alpha\sum_{j=1}^{k}\mu_{j}\leq\sum_{j=1}^{k}\lambda_{j}\leq
1,$ as $\alpha>0$ and $\sum_{j=1}^{k}\mu_{j}\geq 0.$ Again, recall that
$\lambda_{i}-\alpha\mu_{i}=0,$ and each of the $\lambda_{j}-\alpha\mu_{j}\geq
0.$

Thus, $x$ lies in the convex hull of
$H(v_{0},v_{1},\ldots,v_{i-1},v_{i+1},\ldots,v_{k}).$ Like before, by
repeating this process, we can show that $x$ lies in the convex hull $H^{*}$
of at most $d$ of the nonzero $v_{i},$ along with $v_{0},$ i.e. $x\in
H(v_{0},v_{j_{1}},\ldots,v_{j_{d}}).$ ∎

Acknowledgements

I would like to thank Scott Gehlbach at the University of Chicago Political
Science department (and Harris’ Political Economy program) for teaching me
game theory during my first year SSI Formal Theory class. Prof. Gehlbach
introduced the concepts of iterated dominance and rationalizability to me, and
this paper grew out of some observations I made from examples in his class. I
would also like to thank various UChicago economics and computer science
professors for kindly taking a look at the paper and giving feedback during
Winter/Spring 2022. Roger Myerson also provided some important suggestions
about improving the details of the paper, and the last proposition showing the
bound is tight is partly motivated by his observation.

References

[1] Bernheim, D. (1984) Rationalizable Strategic Behavior. Econometrica 52:
1007-1028.

[2] Pearce, D. (1984) Rationalizable Strategic Behavior and the Problem of
Perfection. Econometrica 52: 1029-1050.

[3] Fudenberg, D. and Tirole, J. (1993) Game Theory. Cambridge: MIT Press.

[4] Yildiz, M. Rationalizability lecture notes.
https://dspace.mit.edu/handle/1721.1/99213

[5] Obara, I. Rationalizability and Iterated Elimination of Dominated
Strategies
http://www.econ.ucla.edu/iobara/Rationalizability201B.pdf