User lorenzo lami - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T21:53:27Z http://mathoverflow.net/feeds/user/13961 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/99853/resources-aware-combinatorial-game-theory/102235#102235 Answer by Lorenzo Lami for Resources-Aware Combinatorial Game Theory Lorenzo Lami 2012-07-14T16:27:11Z 2012-07-14T16:27:11Z <p>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).</p> <p>For a practical example (but maybe too elementary to be useful), you can have a look at <a href="http://mathoverflow.net/questions/41837/1-n-game-how-to-analyze" rel="nofollow">this game</a> and <a href="http://mathoverflow.net/questions/41837/1-n-game-how-to-analyze/90991#90991" rel="nofollow">its analysis</a>, I think it fits into the kind of games you could be interested into.</p> http://mathoverflow.net/questions/98050/the-game-of-removing-two-vertices-in-a-graph/98271#98271 Answer by Lorenzo Lami for The game of removing two vertices in a graph Lorenzo Lami 2012-05-29T12:43:28Z 2012-05-29T12:43:28Z <p>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 <em>Kayles</em> on graphs, which shouldn't be far from <em>Dawson's Kayles</em> 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.</p> http://mathoverflow.net/questions/94769/motivation-for-the-sprague-grundy-theorem/97610#97610 Answer by Lorenzo Lami for Motivation for the Sprague-Grundy theorem Lorenzo Lami 2012-05-21T23:39:42Z 2012-05-28T14:57:11Z <p>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).</p> <p>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:</p> <p>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 &lt; n_i.$$</p> <p>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$.</p> http://mathoverflow.net/questions/41837/1-n-game-how-to-analyze/90991#90991 Answer by Lorenzo Lami for 1..n game, how to analyze? Lorenzo Lami 2012-03-12T15:01:18Z 2012-05-21T23:47:34Z <p>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.</p> <p>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' &lt; m$.</p> <p>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}$).</p> <p>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$.</p> <p>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$. </p> <p>To see why this happens, just consider the associated system of inequalities:</p> <p>$$\chi_W \cdot (m_A - p) \geq m_B$$</p> <p>$$\chi_L \cdot m_A \geq m_B - p$$</p> <p>then deduce</p> <p>$$m_A - \frac{ m_B}{\chi_W} \geq p \geq m_B - \chi_L \cdot m_A$$</p> <p>Taking equalities yields the relation stated above.</p> <p>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).</p> <p>I'll add an example:</p> <p>Prizes: 10 6 4 8 5</p> <p>Minimal winning sequences: 10 8, 10 4 5, 10 6 4, 10 6 5, 6 8 5, 6 4 8, 4 8 5.</p> <p>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.</p> <p>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).</p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion Excellent uses of induction and recursion Lorenzo Lami 2012-03-30T16:49:59Z 2012-04-03T11:41:40Z <p>Can you make an example of a <strong><em>great</em></strong> proof by induction or construction by recursion?</p> <p>Given that you already have your own idea of what "great" means, here it can also be taken to mean that the chosen technique :</p> <ul> <li>is vital to the argument;</li> <li>sheds new light on the result itself;</li> <li>yields an elegant way to fulfill the task;</li> <li>conveys a powerful and simple view of an intricate matter;</li> <li>is just the only natural way to deal with the problem.</li> </ul> <p>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...</p> <p>Elementary examples are especially appreciated, but non-elementary ones are welcome too!</p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92985#92985 Answer by Lorenzo Lami for Excellent uses of induction and recursion Lorenzo Lami 2012-04-03T10:27:56Z 2012-04-03T11:41:40Z <p>The "Ercules and the Hydra" problem, as found in "L. Kirby and J. Paris. Accessible independence results for peano arithmetic. <em>London Mathematical Society</em>, 4:285 293, 1982.".</p> <p>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.</p> http://mathoverflow.net/questions/116633/sane-bound-on-number-of-moves-for-maker-breaker-game-on-mathbb-r2-for-0-1 Comment by Lorenzo Lami Lorenzo Lami 2013-01-21T16:28:53Z 2013-01-21T16:28:53Z Has anybody tried to find an explicit winning strategy for Maker in this case? http://mathoverflow.net/questions/119467/homotopy-and-fundamental-group-theory Comment by Lorenzo Lami Lorenzo Lami 2013-01-21T13:54:44Z 2013-01-21T13:54:44Z Your question would be more appropriate on [math.stackexchange.com](<a href="http://math.stackexchange.com" rel="nofollow">math.stackexchange.com</a>) rather than here: this site is for research-level math. http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92709#92709 Comment by Lorenzo Lami Lorenzo Lami 2012-04-08T22:21:09Z 2012-04-08T22:21:09Z Definitely a great advanced example! http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92714#92714 Comment by Lorenzo Lami Lorenzo Lami 2012-04-08T22:16:53Z 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! http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92971#92971 Comment by Lorenzo Lami Lorenzo Lami 2012-04-03T10:09:43Z 2012-04-03T10:09:43Z Nice pick, I should have thought about that (and about other statements not provable in PA)! http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion Comment by Lorenzo Lami Lorenzo Lami 2012-04-03T10:04:41Z 2012-04-03T10:04:41Z @Benjamin: Your proof has earned my first laughter of the day! Nice proof! http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92821#92821 Comment by Lorenzo Lami Lorenzo Lami 2012-04-01T20:14:46Z 2012-04-01T20:14:46Z Among infinite descents, why did you choose this one? http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92738#92738 Comment by Lorenzo Lami Lorenzo Lami 2012-03-31T09:36:29Z 2012-03-31T09:36:29Z Could you please provide a reference?