Friday, 18 April 2014

No game, no life --- game theory case analysis

No game no life is a recent anime that highlights the world that takes game contract as the highest principle, and game theory plays a superior role in the story in a very natural way. Now I would like to analysis one of the game in episode 2 as follows. For simplicity I would use Bob and Alice --- the common name in cryptography --- to describe the whole story.

Bob "Hey Alice let's play paper-scissor-rocks :) I will always play paper."
Alice "What if you don't play paper?"
Bob "If I play don't play paper you win if it's a draw [under original rules] and you draw if you lose [under original rules]. If I win you have to obey my order."
Alice "What if I get a draw?"
Bob "Then you will have to do my little favour :P"
Alice "What favour?"
Bob:



The payout table is as follows



It turned out that Alice had scissor and Bob had rock --- a draw --- with consequences equivalent to a lose as Bob defined. The analysis from Alice: based on random choices there are a 2/3 chance to win for rocks and scissors, but Bob claimed to play scissor so she'd better play scissor. Bob made a conclusion that the risk for Alice is invariant despite the rules:



--------------------------------------------------

Consider the following payout matrix.

$P_1 = \begin{bmatrix}1&0&1\\1&1&0\\-1&1&0\end{bmatrix}$, $P_2 = \begin{bmatrix}1&-1&1\\1&1&-1\\-1&1&-1\end{bmatrix}$

Where $P_1$ is the matrix that Alice thought to be but $P_2$ is the real one. The matrix $P$ is defined as follows: $[P]_{ij}$ is the amount you win if you play the j-th option (vertical) and the opp plays the i-th option (horizontal). (Some textbooks may switch between you and your opp but it's just a matter of perspective on whether you, the analyzer is taking part in the game.)

By strong duality we know that the optimal strategy for both Bob and Alice should have the same expectation. Now suppose Alice has a probability vector $\vec{x}$ to play the three choices with payout matrix $P$. Then the expected outcome for Bob is given by $P\vec{x}$ for different choices from Bob. He as the payer would of course want to minimize the paid. Then we can set up the following linear program for Alice, to maximize the gain when Bob minimizes her gain among the three choices.

$\max (\min ([P\vec{x}]_i)) ~~~\text{subject to}~~~\sum [\vec{x}]_i = 1, \vec{x}\geq \vec{0}$.

And by adding dummy variable we have:

$\max z ~~~\text{subject to}~~~P\vec{x} - z\vec{b}\geq \vec{0},~\sum [\vec{x}]_i = 1,~\vec{x}\geq \vec{0}$

Where $\vec{b} = (1,1,1)^T$. This will be the optimal strategy for Alice.

Using $P_1$ we have $\vec{x}^* = (0,0.5,0.5)^T$ with expected gain $0.5$. Using $P_2$ we have the same optimal vector, but the expected gain is zero. It can be concluded that Alice had the perception that she has an advantage in the game, while actually she had not.

The matrix with four -1 and five 1, turns out to be a fair game (mathematically).

-----------------------------------------------

Gambling at high stakes are of course a totally different game. There are not enough games for one to apply central limit theorem so that the result converges so that they can play in the most probable way. In these games all factors including the psychological status shall be considered and here Alice obviously did not have a good enough mind to do such analysis, so she eventually lose the game.

Can you think of other non-trivial matrix which is fair as well?

Sunday, 6 April 2014

Standard tricks for integration

To access the document version of the notes please go to the "Notes Corner" or my personal site directly.

Why do I make the list

For most of the textbook the tricks are usually classified into (1) standard result (the most obvious stuff) (2) substitution and (3) by part. For normal students a systematic way is required to learn which trick (in detail) to be used and how against different integral. I tried to list all the standard tricks via a standard form so that readers may realize the pairing up between tricks and integrals.

Abstract

This document aims to provide standard tricks to do proper integration. Most of them are making good use of various identities, which should have been well known to readers. The following list is a selection of integrals, that provides the most common tricks to tackle inegral. It is expected that readers should try to learn and apply the tricks, rather than to recite the integration formulae. Here we only cover indefinite integral, that maximizes the extend to find a closed form of a given integral, but there are many more tricks also applicable for definte integral and readers may want to master them as well.

About the content

There are 9 sections in the list, namely (1) Basic theory (2) differential results (3) ordinary substitution (4) By part (5) Trigonometric substitution (6) Fractions (7) Recursion (8) Complex method (9) tan x/2 substitution.

The first 7 parts are somewhat expected for an AL student or first year undergraduates, and the last two are still standard tricks but less common. I found one related questions from AL Pure 2003 about the tan x/2 substitution, but the substitution is instructed in the paper so that it's not very fun, though.

If there are any typos, or any tricks that you think I should/should not include here, just tell me here.

Chris
Apr., 2014