User lorenzo lami - MathOverflow

Answer by Lorenzo Lami for Resources-Aware Combinatorial Game Theory

2012-07-14T16:27:11Z

By including both players' money into the state of the game, you can analize it using some tools in combinatorial game theory, specifically partizan game tools: even if the original game would naturally be a symmetric game, including both players' money inevitably breaks its symmetry except for a handful of positions, so I would suggest symmetric games aren't the ones you are looking for (so Nim and the theory of nimbers would be of little use).

For a practical example (but maybe too elementary to be useful), you can have a look at this game and its analysis, I think it fits into the kind of games you could be interested into.

Answer by Lorenzo Lami for The game of removing two vertices in a graph

2012-05-29T12:43:28Z

If you haven't already, take a look at "Kayles on the way to the stars" by R. Fleischer, G. Trippen. It is a paper about the analysis of the game of Kayles on graphs, which shouldn't be far from Dawson's Kayles on graphs, which is similar to what you're looking for. Please note that the authors adopted the rule of removing nodes rather than edges.

Answer by Lorenzo Lami for Motivation for the Sprague-Grundy theorem

2012-05-21T23:39:42Z

The Sprague-Grundy theorem provides a surjective homomorphism $\mathcal{G}$ from the commutative monoid of symmetric games onto the group $On_2$ (the ordinals with the nim sum). The point of this quotient is that $\ker \mathcal{G}$ is exactly the class of $\mathcal{P}$ games. So you can see how the Sprague-Grundy theorem defines a partition on all games, which are many. In fact, you can think of a symmetric game as a well founded set (formally a biset with equal side-sets, as presented in On Numbers and Games by J. H. Conway); in this light we are partitioning the whole Von Neumann hierarchy $\mathbb{V}$, where each class is indeed very well populated (it is a proper class).

This bridge theorem, as already outlined, allows to compute the outcome of a game just by computing the nimber of each of its components; this is the main use and its original purpose. But it can also be useful the other way round:

If $n_1 + \cdots + n_k = t \neq 0$, where $+$ is the nim sum, then $$\exists i \in \{ 1, \dots ,k \} \mbox{ such that } n_i + t < n_i.$$

A proof is as follows: since $t \neq 0$, $n_1 + \cdots + n_k$ is a $\mathcal{N}$-position in Nim so there must be a winning move from, say, $n_1$ to $\bar{n}_1$ such that $\bar{n}_1 + n_2 + \cdots + n_k =0$. Since in Nim the only legal moves are to decrease numbers it follows that $n_1 > \bar{n}_1$. But, since $On_2$ satisfies $\forall x\ x+x=0$, adding $n_2 + \cdots + n_k + t$ to each side of the previous equation yields (after cancellations) $\bar{n}_1 + t = n_2 + \cdots + n_k + t = n_1$.

Answer by Lorenzo Lami for 1..n game, how to analyze?

2012-03-12T15:01:18Z

I will be assuming that money starts at 1 for each player and players can bid any real number. I'll also assume that prizes are real numbers.

First, it should be noted that in each position with prizes $p_1 , \dots , p_n$ and accumulated scores $s_A, s_B$, if one player wins with money $m$ then he can win with any amount $m'>m$ and if that player loses with money $m$ he also loses with $m' < m $.

Let's assume that there is no partition of the prizes into two classes which yield the same sum; the above argument shows that there is a "singular value" which is the separator of the classes of winning and losing position for a player (such existence is guaranteed in $\mathbb{R}$).

There is a practical rule to find out what that value is in general, but let's start with simple positions: if player $A$ has to win $n$ times in a row in order to win, it is easy to see that the winning condition is $ \frac{1}{n} \cdot m_A \geq m_B$.

To analyse a general position, given that the win-the-prize option has a winning condition of the form $\chi_W \cdot m_A \geq m_B$ and the lose-the-prize option has a winning condition of the form $\chi_L \cdot m_A \geq m_B$, the position the player $A$ is in has a winning condition of $ \frac{1+\chi_L}{1+ \frac{1}{\chi_W}} m_A \geq m_B$.

To see why this happens, just consider the associated system of inequalities:

$$\chi_W \cdot (m_A - p) \geq m_B $$

$$\chi_L \cdot m_A \geq m_B - p$$

then deduce

$$ m_A - \frac{ m_B}{\chi_W} \geq p \geq m_B - \chi_L \cdot m_A $$

Taking equalities yields the relation stated above.

This way, starting form the end of the auction tree you can go backward and find out all the $\chi$ for each position, until you get to the first one. Note that exacxtly meeting the inequality does not guarantee a win, it depends on who is going first on that auction (i.e. who won the last auction).

I'll add an example:

Prizes: 10 6 4 8 5

Minimal winning sequences: 10 8, 10 4 5, 10 6 4, 10 6 5, 6 8 5, 6 4 8, 4 8 5.

Results: In the starting position, $\chi=1$. After the first auction, the losing and winning $\chi$ are respectively $\frac{4}{7}$ and $\frac{7}{4}$; after the second auction the $\chi$ are $\frac{3}{1}$ if you won both 10 and 6, $\frac{4}{3}$ if you won 10 and lost 6, $\frac{3}{4}$ if you lost 10 and won 6, $\frac{1}{3}$ if you lost both.

Note that in the general case where there could be ties, the $\chi$s may not be one the inverse of the other, resulting in a $\chi>1$ for the starting position, which means the first player has no way to win (but still has a way to draw). In fact, I think that every time there is a partition in two subsets so that each yields the same sum, it is not possible for the first player to win (he can just draw).

Excellent uses of induction and recursion

2012-03-30T16:49:59Z

Can you make an example of a great proof by induction or construction by recursion?

Given that you already have your own idea of what "great" means, here it can also be taken to mean that the chosen technique :

is vital to the argument;
sheds new light on the result itself;
yields an elegant way to fulfill the task;
conveys a powerful and simple view of an intricate matter;
is just the only natural way to deal with the problem.

Here induction and recursion are meant in the broadest sense of the words, they can span from induction on natural numbers to well-founded recursion to transfinite induction, and so on...

Elementary examples are especially appreciated, but non-elementary ones are welcome too!

Answer by Lorenzo Lami for Excellent uses of induction and recursion

2012-04-03T10:27:56Z

The "Ercules and the Hydra" problem, as found in "L. Kirby and J. Paris. Accessible independence results for peano arithmetic. London Mathematical Society, 4:285 293, 1982.".

Using transfinite induction, it is possible to show that Hercules will always kill the hydra (with a finite number of blows) regardless of the strategy chosen to chop off hydra's heads. Moreover, this fact is not provable within Peano Arithmetic.

Comment by Lorenzo Lami

2013-01-21T16:28:53Z

Has anybody tried to find an explicit winning strategy for Maker in this case?

Comment by Lorenzo Lami

2013-01-21T13:54:44Z

Your question would be more appropriate on [math.stackexchange.com](math.stackexchange.com) rather than here: this site is for research-level math.

Comment by Lorenzo Lami

2012-04-08T22:21:09Z

Definitely a great advanced example!

Comment by Lorenzo Lami

2012-04-08T22:16:53Z

It's a great nontrivial exercise for those learning induction; it's also a nice, entertaining fact for those who already know induction well. Great answer!

Comment by Lorenzo Lami

2012-04-03T10:09:43Z

Nice pick, I should have thought about that (and about other statements not provable in PA)!

Comment by Lorenzo Lami

2012-04-03T10:04:41Z

@Benjamin: Your proof has earned my first laughter of the day! Nice proof!

Comment by Lorenzo Lami

2012-04-01T20:14:46Z

Among infinite descents, why did you choose this one?

Comment by Lorenzo Lami

2012-03-31T09:36:29Z

Could you please provide a reference?