# Linear Programming question

I am kind of lost on this problem and would like it if I can get help on this.

Matching Pennies. In this simple two player game, the players (call them R and C) each choose an outcome, heads or tails. If both outcomes are equal, C gives a dollar to R; if the outcomes are different, R gives a dollar to C.

A. represent payoffs by a 2 x 2 matrix.

B. What is the value of the game, and what are the optimal strategies for the two players?

EDIT (per amWhy)

To better understand what is being asked here, I found the following description of the game in a discrete math text (many varieties of this problem exist):

"Consider the game of matching coins. Two players A and B each toss a coin. If the coins match i.e. both are heads or both are tails, A gets rewarded; otherwise B gets rewarded."

Translating per this problem: Two players R and C each toss a coin. If both coins match, C gives a dollar to R; otherwise, R gives a dollar to C. So in this case, if both coins match, R gains a dollar, C loses a dollar; if coins don't match, C gains a dollar, R loses a dollar.

-
Could you clarify your description of the Matching Pennies game? I take it R and C each predict an outcome. Is one coin tossed? Or do each toss a coin? What do you mean if "both outcomes": both predictions, or the actual result(s) of the tossed coin(s)? As it is currently written, I'm afraid your description renders your question rather un-anwerable. – amWhy Nov 2 '12 at 18:38
1. This does not appear to be a question about linear programming. 2. What criterion do you use for optimality? There are many (though probably they all give the same solution for this game). – Austin Mohr Nov 2 '12 at 18:41
Your question is similar to question 5 here: austinmohr.com/Math_170_(Spring_2012)_files/test1sol.pdf – Austin Mohr Nov 2 '12 at 18:45

The Nash equilibrium strategy for a 2-person zero-sum game can be computed through linear programming. In your case, the payoff-matrix is $$\begin{array}{r}H \\ T \end{array} \left[ \begin{array}{rr} -1 & 1 \\ 1 & -1 \end{array} \right]$$
or $$e_{ij} = \left\{ \begin{array}{rr} 1 & i = j \\ -1 & \mbox{otherwise} \end{array} \right.$$
The LP is $$\mbox{minimize} \ v$$ subject to $$- y_H + y_T \le v \\ y_T - y_H \le v \\ y_T + y_H = 1 \\ y_T, y_H \ge 0$$ which is clearly optimal at $y_T = y_H = {1 \over 2}$