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

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].

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.

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:

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.

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}.$

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:

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.

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].$

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}.$

We are thus left with the following problem:

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.

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

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.

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

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.

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.

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.

And indeed, this easily follows from the previous claims.

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.

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

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}.$

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

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$