WINNING THE ULTIMATUM GAME
We'll mainly use utility, which is just another word for satisfaction. Utility functions can help us relate the monetary amounts with the satisfaction that each player will get by receiving, or being deprived of, the said amount. From there, we define payoff as the utility of a certain outcome. That is, if we denote the payoff by \(\pi\), the utility function \(u\), and a certain action \(a\), and its outcome \(\omega(a)\), then \(\pi(a)=u(\omega(a))\).
The Game
Imagine this scenario: You and an enemy are strolling until you pick up 100 pesos. Now the two of you decide to divide the money in the following manner: You propose the division, and your enemy will decide whether he'll accept your proposal or not. If he or she accepts, you both get the proportion according to the offer. However, if he/she rejects, then both of you leave the money where you found it, and go along your way. This scenario actually provides the framework for games that involve competition, revenge and other similar cases.
Utility Functions, Payoff and Nash Equilibrium
Let's call the first and second players \(P1\) and \(P2\), respectively. In addition, we denote the fixed amount to be shared by \(x\). We will assume that the offers that \(P1\) can propose are discrete. This way, we can use a matrix of payoffs to determine the Nash Equilibrium.
Ultimatum Game With Discrete Strategies
We denote the strategies of \(P1\) by the percentage he or she will receive in his proposal. On the other hand, the strategies of accepting and rejecting an offer for \(P2\) will be denoted by \(A\) and \(R\), respectively. For argument's sake, we divide the amount in portions of 10. That is, \[\sigma_1=\{ 0,10,20,30,40,50,60,70,80,90,100\}, \]\[\sigma_2=\{A, R\}.\]Now let's go to the specifics of the payoff matrix. When \(P2\) accepts the offer of \(P1\), the payoff that they will receive is equal to the utility of the amount based from the offer. On the other hand, if \(P2\) rejects the offer, the payoff for \(P1\) will be \(u_1(0)\), the utility of gaining nothing. But for \(P2\), the payoff is equal to the utility of the deprived amount from \(P1\). Say both players have the same utility when receiving the amount, and for that we would use \(u(w)=w^{0.5}\) [2]. However, for \(P2\), there will be an added utility when he or she rejects the offer since \(P2\) acquires some satisfaction by depriving the first player of utility. Here, we will use the second utility function \(u_2(w)=w^2-0.00025w^4\) [1]. But since this utility will come from \(P1\)'s supposed satisfaction, \[u_2(w^{0.5})=w-0.00025w^2. (1)\]Hence, if \(P2\) rejects an offer where \(P1\) gets \(w\),\[ \pi_2(w,R)=u_2(\text{depriving }P1\text{ of }w)=w-0.00025w^2. \]Without evaluating for each of the utility values, our desired payoff matrix will look like the one found below.
 |
| Table 1: Payoff Matrix with Discrete Strategies |
 |
| Table 2: Payoff Matrix with Evaluated Values |
There is actually another approach to the ultimatum game. It is a set of strategies called the cake-cutting algorithm for two players. It involves a cut-and-choose optimization, where the first player cuts the cake into whichever way he finds fair and the other chooses the half that he prefers. This algorithm accounts for the fact that distributions unequal in size can still be considered an equilibrium.
Some Applications
- In an episode of the television show Numb3rs, the mathematician explains to an FBI agent how sometimes, when under pressure, one can act illogically. To put a prison situation in context, he brings out $100, and explains the ultimatum game. The FBI agent divides the money 70:30, where she gives herself $70. The mathematician says that he will reject the offer. He emphasizes that one's desire for revenge can affect the choices he makes, and the seeming punishment that the other person will receive might be enough for the player.
- Let the Spratlys group of islands be our fixed amount, and assume that the only competing countries are the Philippines and China. Being that China is the more powerful nation, they can be the one who proposes some amount to the Philippines. The question now is, what is the amount of land that China would propose to ultimately end the debate, assuming that both countries want to maximize their payoffs?
Based from our findings, the split should have been 50-50. But we are actually forgetting several key information. The Philippines doesn't have the luxury to reject something like these islands because of the vast resources that they contain. In addition, we are not familiar with China's motivations behind the acquisition of these islands, so we may not be able to model it well.
A possibly more appropriate way of analyzing this is through the leader-follower environment, rather than Nash Equilibrium. This serves as a dynamic approach to the Spratlys problem, where the more powerful country, China, moves first, and we base our strategies on that move.
Victor Andrew Antonio is a Lecturer at the Ateneo de Manila University. He obtained his B.S. in Mathematics at the Ateneo de Manila University in 2012 and is currently taking his M.S. in Mathematics at the same university.
REFERENCES:
[1] Bowers Jr., et al. Actuarial Mathematics. 1997. The Society of Actuaries, Schaumburg, Illinois, USA.[2] Norstad, J. An Introduction to Utility Theory. 1999. 1-27.
OLYMPIAD CORNER
from the Austrian Mathematical Olympiad, 2007
Problem: Let \(0 < x_0, x_1, x_2, \ldots, x_{669} < 1\) be pairwise different real numbers. Show that a pair \((x_i, x_j)\) exists such that \[ 0 < x_i x_j ( x_j - x_i ) < \frac{1}{2007} \]holds.
Without loss of generality, we assume \(0 < x_0 < x_1 < \ldots <x_{669} < 1\).
Let \(a(i, j) = x_i x_j( x_j - x_i)\). Note that \[ ( x_i - x_j )^2 > 0 \Rightarrow {x_i}^2 + {x_j}^2 > 2x_i x_j \]Hence \[ \begin{align*} 3a(i, j) &= 3x_i x_j (x_j - x_i) \\ &= (2x_i x_j + x_i x_j)(x_j - x_i) \\ &< ({x_i}^2 + x_i x_j + {x_j}^2)(x_j - x_i) \\ &= {x_j}^3 - {x_i}^{3} \end{align*} \]for all indices \(i\) and \(j\). We therefore have \[ \sum_{i=1}^{669} 3a(i-1, i) < \sum_{i=1}^{669}({x_i}^{3}-{x_{i-1}}^3) ={x_{669}}^3 - {x_0}^3 < 1 \] and thus there exists an index \(i\) such that \[ 3a(i-1, i) < \frac{1}{669} \Rightarrow a(i-1, i) < \frac{1}{2007}. \]
Solution:
Without loss of generality, we assume \(0 < x_0 < x_1 < \ldots <x_{669} < 1\).
Let \(a(i, j) = x_i x_j( x_j - x_i)\). Note that \[ ( x_i - x_j )^2 > 0 \Rightarrow {x_i}^2 + {x_j}^2 > 2x_i x_j \]Hence \[ \begin{align*} 3a(i, j) &= 3x_i x_j (x_j - x_i) \\ &= (2x_i x_j + x_i x_j)(x_j - x_i) \\ &< ({x_i}^2 + x_i x_j + {x_j}^2)(x_j - x_i) \\ &= {x_j}^3 - {x_i}^{3} \end{align*} \]for all indices \(i\) and \(j\). We therefore have \[ \sum_{i=1}^{669} 3a(i-1, i) < \sum_{i=1}^{669}({x_i}^{3}-{x_{i-1}}^3) ={x_{669}}^3 - {x_0}^3 < 1 \] and thus there exists an index \(i\) such that \[ 3a(i-1, i) < \frac{1}{669} \Rightarrow a(i-1, i) < \frac{1}{2007}. \]
PROBLEMS
- Sherlock and Mycroft play a game which involves flipping a single fair coin. The coin is flipped repeatedly until one person wins. Sherlock wins if the sequence TTT (tails-tails-tails) shows up first while Mycroft wins if the sequence HTT (heads-tails-tails) shows up first. Who among the two has a higher probability of winning?
- In \(\Delta ABC\), \(D\) is the midpoint of \(AB\), \(E\) and \(F\) are on \(AC\) and \(BC\) respectively. Prove that the area of \(\Delta DEF\) is not greater than the sum of the areas of \(\Delta ADE\) and \(\Delta BDF\).
- Let \(n \geq 3\) be an odd number. Show that there is a number in the set \[ \{ 2^n - 1, 2^2 - 1, \ldots, 2^{n-1} - 1 \} \]which is divisible by \(n\).
We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions may be submitted to the PEM facilitators on the deadline date or online via mactolentino@math.admu.edu.ph. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is 12:00 PM January 12, 2013.
SOLUTIONS
(for December 1, 2012)
- Let \(S(x)\) be the sum of the digits of the positive integer \(x\) in its decimal representation. Show that \(\frac{S(3x)}{S(x)}\) is bounded, or provide a counterexample that says otherwise. (Modified problem from the Mathematical Olympiad Summer Program, 1998)(partial credit for Clyde Wesley Ang [Chiang Kai Shek College], Hans Jarett Ong [Chiang Kai Shek College], Jan Kedrick Ong [Chiang Kai Shek College] and Farrell Eldrian Wu [MGC New Life Christian Academy])SOLUTION:Let \(M(x) = \frac{S(3x)}{S(x)}\). Since \(x\) is a positive integer, it is easy to see that \(M(x)\) is bounded below by 0. We now find an upper bound for \(M(x)\).
Suppose we let \(a_k\ldots a_1\) and \(b_{k+1}b_k\ldots b_1\) be the decimal representations of \(x\) and \(3x\) respectively; that is, \[ x = a_1 + a_2*10 + a_2*10^2 \ldots a_k*10^{k-1}, \] \[ 3x = b_1 + b_2*10 + \ldots + b_{k+1}*10^k. \]If for each multiplication operation \(3a_i\) we denote the carry by \(c_i\), we obtain the set of equations\[ \begin{align*}
3a_1 &= 10c_1 + b_1 \\
3a_2 + c_1 &= 10c_2 + b_2 \\
\vdots \quad & \quad \quad \vdots \\
3a_{k-1} + c_{k-2} &= 10c_{k-1} + b_{k-1} \\
3a_k + c_{k-1} &= 10b_{k+1} + b_k.
\end{align*} \] Taking the sum, we have \[ 3\sum a_i + \sum c_i = 10\sum c_i + \sum b_i + 9b_{k+1} \] \[ 3 = \frac{\sum b_i + 9b_{k+1} + 9\sum c_i}{\sum a_i} \Leftrightarrow 3 = M(x) + 9\left(\frac{b_{k+1} + \sum c_i}{\sum a_i}\right), \]where the terms on the right side are nonnegative. Furthermore, \(x=1\) yields \(M(x) = 3\). Hence, \(0 < M(x) \leq 3\) and is thus bounded. - From the \(xy\)-plane, select five distinct points that have integer coordinates. Find the probability that there is a pair of points among the five whose midpoint has integer coordinates. (15th Philippine Mathematical Olympiad, Area Stage)(solved by Jecel Manabat [Valenzuela City Sci HS], Jan Kedrick Ong [Chiang Kai Shek College], Jazzrine Tagle [Valenzuela City Science High School] and Farrell Eldrian Wu [MGC New Life Christian Academy]; partial credit for Clyde Wesley Ang [Chiang Kai Shek College], Kimberly Co [St. Stephen's], Hans Jarett Ong [Chiang Kai Shek College], Carl Joshua Quines [Valenzuela City Science HS] and Terence Tsai [Chiang Kai Shek College])SOLUTION:A pair of points will have a midpoint with integer coordinates if both their \(x\) and \(y\) coordinates share the same parity. There are at most four ordered pairs with distinct parities, namely (odd, odd), (even, even), (odd, even) and (even, odd). Since there are five points, there will always be a pair of points that share the same parity and will thus have a midpoint with integer coordinates. Thus, the probability that a pair of points will have a midpoint with integer coordinates is equal to 1.
- Let \(ABCD\) be a convex quadrilateral. Prove that \(AC \perp BD\) if and only if \(AB^2+CD^2=AD^2+BC^2\). (Hungary Mathematical Competition, 1912)(solved by Farrell Eldrian Wu [MGC New Life Christian Academy]; partial credit for Clyde Wesley Ang [Chiang Kai Shek College], Kimberly Co [St. Stephen's], Hans Jarett Ong [Chiang Kai Shek College], Jan Kedrick Ong [Chiang Kai Shek College] and Terence Tsai [Chiang Kai Shek College])SOLUTION:Suppose that \(AC\perp BD\) and let \(O\) be the point of intersection of \(AC\) and \(BD\). Then \[ \begin{align*}
{AB}^2+{DC}^2 &= ({AO}^2+{BO}^2)+({CO}^2+{DO}^2) \\
&= ({AO}^2+{DO}^2)+({BO}^2+{CO}^2) \\
&= {AD}^2 + {BC}^2.
\end{align*} \]Now suppose that \({AB}^2+{DC}^2={AD}^2+{BC}^2\) or equivalently, \({AB}^2-{AD}^2={BC}^2-{DC}^2\). Let \(A'\) and \(C'\) be the perpendicular projections of \(A\) and \(C\) on \(BD\) (respectively). Then we have \[ \begin{align*}
{AB}^2 - {AD}^2 &= {A'B}^2 - {A'D}^2 &= BD(A'B-A'D), \\
{BC}^2 - {DC}^2 &= {BC'}^2 - {C'D}^2 &= BD(BC'-C'D),
\end{align*} \]therefore \(BA' - A'D = BC' - C'D\), implying that \(A'\) and \(C'\) are coincident, hence \(AC \perp BD\).
ERRATA
Renzo Tan [Chiang Kai Shek College] was not credited for answering problems 4 and 6.
