<p>In his answer, domotorp suggests analyzing a special case of the game. This special case arises when the permutation is a series of increasing sequences, each of which is larger than the following one, such as (8,9,5,6,7,4,1,2,3). In this game, you start with a collection of heaps of stones, and players alternately remove one stones from a heap. The player who leaves a single heap wins. We will say the $i$th heap has $h_i$ stones in it, and assume that the $h_i$ are given in decreasing order. For example, for the permutation above, the $h_i$ are 3,3,2,1.  I tried giving the analysis of this game in the comments to domotorp's answer, but (a) I got it wrong and (b) there isn't enough room in comments to give a real proof.</p>

<p>To analyze this game, we need to compare two quantities: $s$, the number of heaps containing single stones and $t=\sum_{i\geq 2, h_i&gt;2\,} h_i -2$; note that we ignore the largest heap in the sum. This is the number of stones you would have to remove to ensure that all heaps but one contain no more than two stones. We claim that the losing positions are as follows:</p>

<ol>
<li><p>Positions where $t \leq s-2$ containing an odd number of stones.</p></li>
<li><p>Positions where $t \geq s$ containing an even number of stones.</p></li>
</ol>

<p>It is easy to show that from a losing position, you must go to a winning position, since $t - s$ can only change by at most 1 each turn, and the number of stones goes down by 1 each move.</p>

<p>To finish showing that this is correct, we need to show that from any position which is not in category (1) or (2), the first player can in one move either reach a position in category (1) or (2), or win directly. </p>

<p>There are two cases:</p>

<ol>
<li><p>Positions where $t \geq s-1$ containing an odd number of stones. Here, if $s&gt;0$, remove a stone from a heap with a single stone. If there's only one heap left, we've won. Otherwise, we now have $t \geq s$. If there are no heaps with a single stone, remove a stone from a heap with at least three stones. (Since there were an odd number of stones, this is possible). Since $s = 0$, we have $t \geq s$. </p></li>
<li><p>Positions where $t \leq s-1$ containing an even number of stones. Here, if there are any heaps with at least two stones other than the largest heap, remove a stone from one of them. If this heap has three or more stones in it, $t$ decreases by one. If it has exactly two stones in it, $s$ increases by one. We now have $t \leq s-2$. The last case is when all the heaps except one consist of single stones; in this case, it is easy to check the first player wins if there are an even number of stones. </p></li>
</ol>

<p>I've tried generalizing this strategy to the original game, and haven't figured out how to do it. </p>

CC BY-SA 3.0
2012-01-09T20:39:45.717Z
In my answer, I noted that having a solution to this special case also solves the special case with an increasing series of decreasing runs, by playing in the "dual" position obtained by transposing the Young diagram.  In particular, Eve's optimal strategy becomes "take from the largest heap, unless there are exactly two of that size", and Otto's optimal strategy becomes "take from the smallest heap".
mjqxxxx
CC BY-SA 3.0
2012-01-10T06:09:10.957Z
I am sure that this approach will lead to a perfect solution, but at the moment there still is a minor mistake, e.g. (3,1) is not losing and (3,1,1) is. The problem is that the definition of 2. should exclude this case, since we can reach a one heap position in one step. But I think this is the only problem with 2. and hopefully it is not hard to correct it.
domotorp
CC BY-SA 3.0
2012-01-10T18:17:22.410Z
@domotorp: For (3,1), *t* = 0  and *s* = 1, so *t* $\not\geq$ *s*, and criterion (2) says that it is not a losing position. For (3,1,1), *t* = 0 and *s* = 2, so *t* $\leq$ *s* $-$ 2,  and  criterion (1) says that it is a losing position. I think you missed that in the definition of *t*, you ignore the largest heap.
Peter Shor 
CC BY-SA 3.0
2012-01-11T06:35:35.227Z
Of course, I forgot that part at the end... Then this game is solved!
domotorp
CC BY-SA 3.0
2012-01-11T10:19:47.003Z
Not a complete answer, but still worth the bounty.
Jeffε
CC BY-SA 3.0
2012-01-09T17:41:14.080Z
2012-01-10T18:22:30.467Z
2012-01-10T18:22:30.467Z
Peter Shor 
<p>The "permutation game" is isomorphic to the following game:</p>

<blockquote>
  <p><strong>Disconnect.</strong> Players alternately remove vertices from a graph $G$.  The player that produces a fully disconnected graph (i.e., a graph with no edges) is the winner.</p>
</blockquote>

<p>The graph $G_{\pi}$ corresponding to a particular initial permutation $\pi\in S_n$ contains just those edges $(i,j)$ for which $i-j$ and $\pi(i)-\pi(j)$ have opposite signs.  That is, each pair of numbers in the <em>wrong</em> order in the permutation is associated with an edge.  Clearly the allowed moves are isomorphic to those in the permutation game (remove a number = remove a node), and the winning conditions are isomorphic as well (no pairs in descending order = no edges remaining).</p>

<p>A complementary view is obtained by considering playing a "dual" game on the graph complement $G^{c}_\pi = G_{R(\pi)}$, which contains those edges $(i,j)$ for which $i$ and $j$ are in the <em>correct</em> order in the permutation.  The dual game to Disconnect is:</p>

<blockquote>
  <p><strong>Reconnect.</strong> Players alternately remove vertices from a graph $G$.  The player that produces a complete graph is the winner.</p>
</blockquote>

<p>Depending on the particular permutation, one of these games may seem simpler than the other to analyze.  The advantage of graph representation is that it is clear that disconnected components of the graph are separate games, and so one hopes for some reduction in complexity.  It also makes the symmetries of the position more apparent.  Unfortunately, the winning conditions are non-standard... the permutation game will always end before all moves are used up, giving it something of a <em>misère</em> character.  In particular, the nim-value cannot be calculated as the nim-sum (binary XOR) of the nim-values of the disconnected components.</p>

<hr>

<p>For Disconnect, it is not hard to see that for any graph $G$ and any even $n$, the game $G \cup \bar{K}_n$ is equivalent to $G$ (where $\bar{K}_n$ is the edgeless graph on $n$ vertices).  To prove it, we need to show that the disjunctive sum $G + G\cup\bar{K}_n$ is a second-player win.  The proof is by induction on $|G|+n$.  If $G$ is edgeless, then the first player loses immediately (both games are over).  Otherwise, the first player can move in either $G$, and the second player can copy his move in the other one (reducing to $G&#39; + G&#39;\cup \bar{K_n}$ with $|G'|=|G|-1$); or, if $n\ge 2$, the first player can move in the disconnected piece, and the second player can do the same (reducing to $G + G\cup\bar{K}_{n-2}$).</p>

<p>This shows that any graph $G$ is equivalent to $H \cup K_p$, where $H$ is the part of $G$ with no disconnected vertices, and $p=0$ or $1$ is the <em>parity</em> of the number of disconnected vertices in $G$.  All games in an equivalence class have the same nim-value, and moreover, the equivalence relation respects the union operation: if $G \sim H \cup K_p$ and $G&#39; \sim H&#39; \cup K_{p&#39;}$ then $G \cup G&#39; \sim (H \cup H&#39;)\cup K_{p\oplus p&#39;}$.  Moreover, one can see that the games in $[H \cup K_0]$ and $[H \cup K_1]$ have different nim-values unless $H$ is the null graph: when playing $H + H \cup K_1$, the first player can take the isolated vertex, leaving $H+H$, and then copy the second player's moves thereafter. </p>

<p>I do not know any related decomposition results for Reconnect.</p>

<hr>

<p>Two special types of permutations correspond to particularly simple heap games.</p>

<ol>
<li>The first is an <em>ascending run of descents</em>, e.g., $32165487$.  When $\pi$ takes this form, the graph $G_{\pi}$ is a union of disjoint cliques, and the game of Disconnect reduces to a game on heaps: players alternately remove a single bean from a heap <em>until all heaps have size $1$</em>.</li>
<li>The second is a <em>descending run of ascents</em>, e.g., $78456123$.  When $\pi$ takes this form, the graph $G^{c}_{\pi}$ is a union of disjoint cliques, and the game of Reconnect reduces to a game on heaps: players alternately remove a single bean from a heap <em>until there is only one heap left</em>.</li>
</ol>

<p>A little thought shows that these two different games on heaps (we can call them <strong>1-Heaps</strong> and <strong>One-Heap</strong>, at some risk of confusion) are, in fact, themselves isomorphic.  Both can be represented by a game on a Young diagram (as initially proposed by @domotorp) in which players alternate removing a lower-right square until only a single row is left.  This is obviously the same game as 1-Heaps when columns correspond to heaps, and the same game as One-Heap when rows correspond to heaps.</p>

<p>A key element of this game, which extends to Disconnect and Reconnect, is that the duration is related to the final game state in a simple way.  When it is your turn, you will win if the game has an odd number of moves remaining, including the one you're about to make.  Since a single square is removed each move, this means you want the number of squares remaining at the end of the game to have the opposite parity that it has now.  Moreover, the number of squares will have the same parity on all of your turns; so you know from the outset what parity you want the final count to have.  We can call the two players Eve and Otto, according to whether the final count must be even or odd for them to win.  Eve always moves in states with odd parity and produces states with even parity, and Otto is the opposite.</p>

<p>In his answer, @PeterShor gives a complete analysis of One-Heap.  Without repeating the proof, the upshot is the following:</p>

<ul>
<li>Otto likes $1$-heaps and $2$-heaps, and can tolerate a single larger heap.  He wins if he can make all heap sizes except one $\le 2$, at least without giving Eve an immediate win of the form $(1,n)$.  An optimal strategy for Otto is to always take from the second-largest heap except when the state is $(1,1,n&gt;1)$, when he should take from the $n$.  Otto will lose if there are too many beans in big heaps to start with.</li>
<li>Eve dislikes $1$-heaps.  She wins if she can make all heap sizes $\ge 2$.  An optimal strategy for Eve is to always take from a $1$-heap, if there are any, and never take from a $2$-heap.  Eve will lose if there are too many $1$-heaps to start with.</li>
</ul>

<p>As noted, this gives optimal strategies for 1-Heaps as well, although they are somewhat more awkward to phrase (and I may well be making an error in primary-to-dual "translation").  In the game of 1-Heaps:</p>

<ul>
<li>Otto likes one or two large heaps, and can tolerate any number of $1$-heaps.  He wins if he can make all but the two largest heaps be $1$-heaps, at least without giving Eve an immediate win of the form $(1,1,\dots,1,2)$.  An optimal strategy for Otto is to always take from the third-largest heap, or from the smaller heap when there are only two heaps.</li>
<li>Eve dislikes a gap between the largest and second-largest heaps.  She wins if she can make the two largest heaps the same size.  An optimal strategy for Eve is to always take from the largest heap, if it is unique, and never if there are exactly two of the largest size.</li>
</ul>

<p>As @PeterShor notes, it isn't clear how (or if) these analyses could be extended to the more general games of Disconnect and Reconnect.</p>

CC BY-SA 3.0
2011-12-30T01:43:23.857Z
I think that this kind of games are collectively referred to as “vertex deletion games.”  But I agree with you that the winning condition is quite nonstandard in that it refers to the global property of the graph instead of local properties such as the degree of a vertex.
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-30T04:41:39.770Z
The constructed graph is called a permutation graph (http://en.wikipedia.org/wiki/Permutation_graph) in the literature.  Some structural properties might help.
Yoshio Okamoto
CC BY-SA 3.0
2011-12-30T04:52:20.320Z
@Yoshio: That's a good point.  The permutation game is isomorphic to the graph game, but the starting graphs aren't arbitrary.  So even if the general graph game is hard to analyze, it's possible that when restricted to this subclass of graphs, it becomes simpler.
mjqxxxx
CC BY-SA 3.0
2011-12-30T11:34:45.473Z
in terms of the computational problem of determining the winner i guess the more appropriate term might be "reduction"; that captures the fact that the graph game might imply a harder problem.
Sasho Nikolov
CC BY-SA 3.0
2011-12-30T11:35:29.003Z
On the other hand, the more general formulation might be easier to prove hard.  Variants of vertex-deletion games are known to be PSPACE-hard, for example: http://www.emis.ams.org/journals/INTEGERS/papers/a31int2005/a31int2005.pdf
Jeffε
CC BY-SA 3.0
2012-01-02T20:44:19.700Z
I've added a question on this kind of game specifically over at math.SE (http://math.stackexchange.com/questions/95895/analyzing-a-class-of-vertex-deletion-games).  Incidentally, since permutation graphs are circle graphs, an alternate formulation is the following: Players take turns removing chords from an initial set; the player that leaves a non-intersecting set of chords is the winner.
mjqxxxx
CC BY-SA 3.0
2011-12-30T00:23:04.047Z
2012-01-10T06:15:47.047Z
2012-01-10T06:15:47.047Z
mjqxxxx
<p>I've implemented an $O(2^n n)$ solution for quick hypothesis checking. <a href="http://ideone.com/Owg32" rel="nofollow">Feel free to play with it</a>. If you don't have C++ compiler locally, you can run it on different inputs remotely using "upload with new input" link.</p>

<p>@JɛﬀE It happened that (1,4,3,2) has value *1, not *2 as you suggested.</p>

CC BY-SA 3.0
2012-01-07T18:28:19.160Z
Oops, my mistake.  Fixed the question:  g(1,3,2) = mex{g(1,3), g(1,2), g(3,2)} = mex{0, 0, *1} = *2.
Jeffε
CC BY-SA 3.0
2012-01-07T18:51:34.277Z
@JɛﬀE It's interesting that for $n \le 10$ SG-value of any position is not greater than 2. I'm trying to prove that now for arbitrary $n$, although I dunno how will that help.
Dmytro Korduban
CC BY-SA 3.0
2012-01-17T20:37:29.310Z
@maldini: it gives hope that the game has some nice properties, which might make it tractable. I wonder what happens to the game generalized to graphs, or the game just generalized to perfect graphs.
Peter Shor 
CC BY-SA 3.0
2012-01-07T11:55:37.400Z
2012-01-07T11:55:37.400Z
Dmytro Korduban
<p>Edit 5th of Jan: In fact the One Heap Game described below is a special case of the problem, i.e. when the numbers follow each other in a specific way such that the first group is bigger than the second group which is bigger than the third etc. and the numbers in each group are increasing. E.g. 8, 9, 4, 5, 6, 7, 2, 3, 1 is such a permutation. So I propose to solve this special case first.</p>

<p>Disclaimer: I no longer claim that the below proof is correct, see e.g. the comment of Tsuyoshi which shows that deleting a number from a permutation will give a diagram not obtainable by deleting a square from the diagram of the permutation. I left the answer here to show that this approach does not work, plus since it contains another simple game.</p>

<p>The game has a very simple other formulation thanks to Young Tableaux. I am sure that it can be analyzed from there as other games and it will yield a linear time algorithm.</p>

<p>First define the following game on Young Diagrams: At each turn, if the current diagram is horizontal (all squares in one line), the current player loses and the other player wins; otherwise, the current player removes one of the bottom-right squares, and play passes to the other player.</p>

<p>Now order the sequence of numbers into a Young Tableaux. The main claim is that the winner of the original game is the same as the winner as the diagram game starting with this shape. To see this, notice that whenever the players delete a number, the diagram of the new sequence can be achieved by deleting a bottom-right square of the diagram. Moreover, any such diagram can be achieved by deleting the number from the respective bottom-right square. These statements follow from standard Young Tableaux theory.</p>

<p>Although this diagram game is simple enough, it is trivially equivalent to the following game, which seems more standard:</p>

<p>One Heap Game: The players are given some heaps with some pebbles in each. At each turn, if their is only one heap left, the current player loses and the other player wins; otherwise, the current player removes a pebble from a heap, and play passes to the other player.</p>

<p>If there is a simple solution to the heap game (and I strongly believe there is one) we also get a solution to the original game: Just put the sequence in a Young Tableaux, and transform its diagram into heaps.</p>

<p>Unfortunately I do not see which heap positions are winning/how to determine the Sprague–Grundy values. I checked a few cases by hand, and the following are the losing positions with at most 6 pebbles:</p>

<p>one heap; (1,1,1); (2,2); (3,1,1); (2,1,1,1); (1,1,1,1,1); (4,2); (3,3); (2,2,2).</p>

<p>Anyone can solve this game?</p>

<p>Edit: Peter Shor can, see his answer!</p>

CC BY-SA 3.0
2011-12-30T13:32:40.563Z
Can you give at least one example showing how a particular permutation is turned into a Young Tableau and how the same game (number removal until an ascending sequence is reached) is played on the Tableau?  In particular I don't understand what it means to remove "one of the bottom-right squares".
mjqxxxx
CC BY-SA 3.0
2011-12-30T15:13:15.380Z
Eg. 1324 becomes (124,3), now Alice deletes 3 to make it (124) and wins. Hm, but if she deletes 2, then it becomes (14,3), strange, I thought deleting a number from a sequence is equivalent to deleting a square from the tableau. Then maybe my whole reasoning is incorrect...
domotorp
CC BY-SA 3.0
2011-12-30T16:06:32.423Z
Yes, it doesn't seem like it quite works: to get the correct tableau after a number is removed, you sometimes need to propagate some numbers back up to earlier rows.
mjqxxxx
CC BY-SA 3.0
2011-12-30T20:28:41.807Z
@domotorp: Your counterexample isn't a counterexample.  If Alice deletes 2, then the Young tableau of the permutation becomes (134;).  So deleting 2 has precisely the same effect on the Young diagram as deleting 3, which makes sense, because 124 and 134 are the same permutation.
Jeffε
CC BY-SA 3.0
2011-12-30T21:42:27.073Z
@JɛﬀE: No, it is a counterexample.  Of course the Young tableaux can be used to represent permutations; the question is whether you can actually play the game by modifying the tableaux directly, and whether the legal moves are easy to represent in that format.  The original idea was that a legal move on the tableau would be just "remove a square" (and I guess move the rest of that row to the left?)  $(124,3)$ is a counterexample because removing $2$ doesn't give $(14,3)$; instead, removing a single square affects multiple rows.
mjqxxxx
CC BY-SA 3.0
2011-12-31T03:10:36.573Z
Here is a counterexample to a weaker claim that removing a number from a permutation corresponds to a removing one of the bottom-right cells from the corresponding Young _diagram_ (instead of Young _tableau_).  Let n=5, and consider a position specified by the permutation [4,1,3,5,2] (that is, σ(1)=4, σ(2)=1, and so on), and remove 3 from it.  The corresponding Young diagram before the move is 5=3+1+1, but the corresponding Young diagram after the move is 4=2+2, which is not obtained from removing one cell from 3+1+1.
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-31T11:32:01.607Z
And the permutation [5,4,1,2,3] has the same Young diagram as [4,1,3,5,2], but you cannot reach the Young diagram 4=2+2 from it. So the game depends on more than the shape of the Young tableau.
Peter Shor 
CC BY-SA 3.0
2012-01-01T10:37:49.127Z
Hooray for constructive misunderstanding!
Jeffε
CC BY-SA 3.0
2012-01-03T12:28:41.030Z
@JɛﬀE: Yeah, this is much more useful than a proof of mere existence of misunderstanding.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-06T11:57:06.020Z
And it even gives an easier problem, as I have discovered today! (see edit at top)
domotorp
CC BY-SA 3.0
2012-01-06T18:40:55.000Z
Here's what I believe is the strategy for domotorp's game. If all heaps are of size 1 or 2, with at least one heap of size 1, the losing positions are those with an odd number of size-1 heaps. The winning strategy is to always take a stone from a size-2 heap. This guarantees that the last heap has exactly one stone in it. (Continued.)
Peter Shor 
CC BY-SA 3.0
2012-01-06T18:41:28.480Z
If all the heaps are of size at least 2, then the losing positions are those with an even number of odd-size heaps. The winning strategy is to take a stone from a size-1 heap, if one exists, and otherwise from any odd-size heap. This guarantees that the last heap always has an even number of stones in it. If there are heaps of both size 1 and size $\geq$ 3, then it comes down to a race between the two players, with one player trying to get rid of the heaps of size 1, and the other trying to get rid of heaps of size $\geq 3$.
Peter Shor 
CC BY-SA 3.0
2012-01-07T04:23:53.927Z
@Peter: I am not sure your argument is correct. If all heaps are of size 1 or 2, then the losing positions are when we have an odd number AND at least three size-1 heaps. I do not know the answer to the general version.
domotorp
CC BY-SA 3.0
2012-01-07T04:31:41.073Z
@domotorp: I have edited my answer to note the equivalence of the permutation game to a heap game in the special case of permutations like $894567231$.  Interestingly, the same heap game (with a dual starting position) can be used to analyze the permutation game for the reversal of such a permutation, e.g., $132765498$.
mjqxxxx
CC BY-SA 3.0
2012-01-07T10:59:31.703Z
@mjq: Interesting, thx!
domotorp
CC BY-SA 3.0
2012-01-09T04:17:15.163Z
@Peter is basically correct.  One of the players (Eve) wants the game to end with an even-sized heap; the other (Otto) wants the game to end with an odd-sized heap.  Eve wins if she can make all heaps $\ge 2$ (since after that she can remove $1$-heaps as fast as they are created).  Otto wins if he can make all heaps $\le 2$ (since after that he can create $1$-heaps as fast as they are destroyed, until all heaps are $1$-heaps).  Optimal play for Eve is to destroy $1$-heaps whenever possible, and never create any.  Optimal play for Otto is to always take from the largest heap.
mjqxxxx
CC BY-SA 3.0
2012-01-09T15:41:22.420Z
@mjq: Why is it good for Eve to destroy all 1-heaps? I think the game is more complicated than that.
domotorp
CC BY-SA 3.0
2012-01-09T17:50:36.763Z
@domotorp: I've posted a corrected version of my comments as an answer (it only answers your special case, but it's way too long to put in comments).
Peter Shor 
CC BY-SA 3.0
2011-12-30T11:58:50.690Z
2012-01-11T06:37:54.623Z
2012-01-11T06:37:54.623Z
domotorp
<p>This is a restatement of an <a href="https://cstheory.stackexchange.com/questions/9507/permutation-game">earlier question</a>.</p>

<p>Consider the following <a href="http://en.wikipedia.org/wiki/Impartial_game" rel="nofollow noreferrer">impartial</a> <a href="http://en.wikipedia.org/wiki/Perfect_information" rel="nofollow noreferrer">perfect information</a> game between two players, Alice and Bob.  The players are given a permutation of the integers 1 through n.  At each turn, if the current permutation is increasing, the current player loses and the other player wins; otherwise, the current player removes one of the numbers, and play passes to the other player.  Alice plays first.  For example:</p>

<ul>
<li><p>(1,2,3,4) — Bob wins immediately, by definition.</p></li>
<li><p>(4,3,2,1) — Alice wins after three turns, no matter how anyone plays.</p></li>
<li><p>(2,4,1,3) — Bob can win on his first turn, no matter how Alice plays.</p></li>
<li><p>(1,3,2,4) — Alice wins immediately by removing the 2 or the 3; otherwise, Bob can win on his first turn by removing the 2 or the 3.</p></li>
<li><p>(1,4,3,2) — Alice <em>eventually</em> wins if she takes the 1 on her first turn; otherwise, Bob can win on his first turn by <em>not</em> removing the 1.</p></li>
</ul>

<p>Is there a polynomial-time algorithm to determine which player wins this game from a given starting permutation, assuming <a href="http://en.wikipedia.org/wiki/Solved_game#Perfect_play" rel="nofollow noreferrer">perfect play</a>?  More generally, because this is a standard impartial game, every permutation has a <a href="http://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem" rel="nofollow noreferrer">Sprague–Grundy value</a>; for example, (1,2,4,3) has value <a href="http://en.wikipedia.org/wiki/Star_%28game_theory%29" rel="nofollow noreferrer">*1</a> and (1,3,2) has value *2.  How hard is it to compute this value?</p>

<p>The obvious backtracking algorithm runs in O(n!) time, although this can be reduced to $O(2^n poly(n))$ time via dynamic programming.</p>

CC BY-SA 3.0
2011-12-29T13:36:14.053Z
Seems to me that the naive algorithm runs in O(2^n⋅poly(n)) time.
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-29T13:53:58.587Z
From your examples, it is obvious that Alice always wins if the sequence is descending and Bob always wins if the sequence is ascending. This problem reminds me of analyzing sorting algorithms, which have been extensively studied and allow you to use a wide arsenal of tools.
chazisop
CC BY-SA 3.0
2011-12-29T14:09:16.103Z
@chazisop: “Alice always wins if the sequence is descending”: That is the case if and only if n is even.
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-29T23:23:47.917Z
@JɛﬀE in case 3,  how does Bob win on his first turn ?
Suresh Venkat
CC BY-SA 3.0
2011-12-30T01:32:17.077Z
@Suresh: In the case of (2,4,1,3), the graph representation is the linear graph on 4 vertices (2-1-4-3).  If Alice removes an end node, this leaves the linear graph on 3 vertices; Bob wins by removing the center vertex (so 3 is answered by 1, and 2 is answered by 4).  If Alice removes an interior node, this leaves two connected vertices and an isolated node; Bob wins by removing either of the two connected vertices (so 1 is answered by 3 or 4, and 4 is answered by 1 or 2).
mjqxxxx
CC BY-SA 3.0
2012-01-03T00:20:56.623Z
@TsuyoshiIto You are correct, of course. However I am still curious whether or not this game can be analyzed from a sorting algorithm perspective.
chazisop
CC BY-SA 3.0
2012-01-30T20:31:21.313Z
@TsuyoshiIto: Sorry, what exactly is the 'naive' algorithm here?
Randomblue
<gt.game-theory><combinatorial-game-theory>
Permutation game redux
Jeffε
# Permutation game redux

(Asked by: username_0 on 2011-12-29)

This is a restatement of an [earlier question](https://cstheory.stackexchange.com/questions/9507/permutation-game).

Consider the following [impartial](http://en.wikipedia.org/wiki/Impartial_game) [perfect information](http://en.wikipedia.org/wiki/Perfect_information) game between two players, Alice and Bob. The players are given a permutation of the integers 1 through n. At each turn, if the current permutation is increasing, the current player loses and the other player wins; otherwise, the current player removes one of the numbers, and play passes to the other player. Alice plays first. For example:

* (1,2,3,4) — Bob wins immediately, by definition.
* (4,3,2,1) — Alice wins after three turns, no matter how anyone plays.
* (2,4,1,3) — Bob can win on his first turn, no matter how Alice plays.
* (1,3,2,4) — Alice wins immediately by removing the 2 or the 3; otherwise, Bob can win on his first turn by removing the 2 or the 3.
* (1,4,3,2) — Alice *eventually* wins if she takes the 1 on her first turn; otherwise, Bob can win on his first turn by *not* removing the 1.

Is there a polynomial-time algorithm to determine which player wins this game from a given starting permutation, assuming [perfect play](http://en.wikipedia.org/wiki/Solved_game#Perfect_play)? More generally, because this is a standard impartial game, every permutation has a [Sprague–Grundy value](http://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem); for example, (1,2,4,3) has value [\*1](http://en.wikipedia.org/wiki/Star_%28game_theory%29) and (1,3,2) has value \*2. How hard is it to compute this value?

The obvious backtracking algorithm runs in O(n!) time, although this can be reduced to $O(2^n poly(n))$ time via dynamic programming.

**Tags:** gt.game-theory, combinatorial-game-theory
> **Comments:**
> **username_1**: Seems to me that the naive algorithm runs in O(2^n⋅poly(n)) time.  
> **username_2**: From your examples, it is obvious that Alice always wins if the sequence is descending and Bob always wins if the sequence is ascending. This problem reminds me of analyzing sorting algorithms, which have been extensively studied and allow you to use a wide arsenal of tools.  
> **username_1**: @chazisop: “Alice always wins if the sequence is descending”: That is the case if and only if n is even.  
> **username_3**: @JɛﬀE in case 3,  how does Bob win on his first turn ?  
> **username_4**: @Suresh: In the case of (2,4,1,3), the graph representation is the linear graph on 4 vertices (2-1-4-3).  If Alice removes an end node, this leaves the linear graph on 3 vertices; Bob wins by removing the center vertex (so 3 is answered by 1, and 2 is answered by 4).  If Alice removes an interior node, this leaves two connected vertices and an isolated node; Bob wins by removing either of the two connected vertices (so 1 is answered by 3 or 4, and 4 is answered by 1 or 2).  
> **username_2**: @TsuyoshiIto You are correct, of course. However I am still curious whether or not this game can be analyzed from a sorting algorithm perspective.  
> **username_5**: @TsuyoshiIto: Sorry, what exactly is the 'naive' algorithm here?  

---

## 4 answers

### Answer by username_6 on 2012-01-09. Score: 7

In his answer, domotorp suggests analyzing a special case of the game. This special case arises when the permutation is a series of increasing sequences, each of which is larger than the following one, such as (8,9,5,6,7,4,1,2,3). In this game, you start with a collection of heaps of stones, and players alternately remove one stones from a heap. The player who leaves a single heap wins. We will say the $i$th heap has $h\_i$ stones in it, and assume that the $h\_i$ are given in decreasing order. For example, for the permutation above, the $h\_i$ are 3,3,2,1. I tried giving the analysis of this game in the comments to domotorp's answer, but (a) I got it wrong and (b) there isn't enough room in comments to give a real proof.

To analyze this game, we need to compare two quantities: $s$, the number of heaps containing single stones and $t=\sum\_{i\geq 2, h\_i>2\,} h\_i -2$; note that we ignore the largest heap in the sum. This is the number of stones you would have to remove to ensure that all heaps but one contain no more than two stones. We claim that the losing positions are as follows:

1. Positions where $t \leq s-2$ containing an odd number of stones.
2. Positions where $t \geq s$ containing an even number of stones.

It is easy to show that from a losing position, you must go to a winning position, since $t - s$ can only change by at most 1 each turn, and the number of stones goes down by 1 each move.

To finish showing that this is correct, we need to show that from any position which is not in category (1) or (2), the first player can in one move either reach a position in category (1) or (2), or win directly.

There are two cases:

1. Positions where $t \geq s-1$ containing an odd number of stones. Here, if $s>0$, remove a stone from a heap with a single stone. If there's only one heap left, we've won. Otherwise, we now have $t \geq s$. If there are no heaps with a single stone, remove a stone from a heap with at least three stones. (Since there were an odd number of stones, this is possible). Since $s = 0$, we have $t \geq s$.
2. Positions where $t \leq s-1$ containing an even number of stones. Here, if there are any heaps with at least two stones other than the largest heap, remove a stone from one of them. If this heap has three or more stones in it, $t$ decreases by one. If it has exactly two stones in it, $s$ increases by one. We now have $t \leq s-2$. The last case is when all the heaps except one consist of single stones; in this case, it is easy to check the first player wins if there are an even number of stones.

I've tried generalizing this strategy to the original game, and haven't figured out how to do it.

> **Comments:**
> **username_4**: In my answer, I noted that having a solution to this special case also solves the special case with an increasing series of decreasing runs, by playing in the "dual" position obtained by transposing the Young diagram.  In particular, Eve's optimal strategy becomes "take from the largest heap, unless there are exactly two of that size", and Otto's optimal strategy becomes "take from the smallest heap".  
> **username_7**: I am sure that this approach will lead to a perfect solution, but at the moment there still is a minor mistake, e.g. (3,1) is not losing and (3,1,1) is. The problem is that the definition of 2. should exclude this case, since we can reach a one heap position in one step. But I think this is the only problem with 2. and hopefully it is not hard to correct it.  
> **username_6**: @domotorp: For (3,1), *t* = 0  and *s* = 1, so *t* $\not\geq$ *s*, and criterion (2) says that it is not a losing position. For (3,1,1), *t* = 0 and *s* = 2, so *t* $\leq$ *s* $-$ 2,  and  criterion (1) says that it is a losing position. I think you missed that in the definition of *t*, you ignore the largest heap.  
> **username_7**: Of course, I forgot that part at the end... Then this game is solved!  
> **username_0**: Not a complete answer, but still worth the bounty.  

---

### Answer by username_4 on 2011-12-30. Score: 7

The "permutation game" is isomorphic to the following game:

> **Disconnect.** Players alternately remove vertices from a graph $G$. The player that produces a fully disconnected graph (i.e., a graph with no edges) is the winner.

The graph $G\_{\pi}$ corresponding to a particular initial permutation $\pi\in S\_n$ contains just those edges $(i,j)$ for which $i-j$ and $\pi(i)-\pi(j)$ have opposite signs. That is, each pair of numbers in the *wrong* order in the permutation is associated with an edge. Clearly the allowed moves are isomorphic to those in the permutation game (remove a number = remove a node), and the winning conditions are isomorphic as well (no pairs in descending order = no edges remaining).

A complementary view is obtained by considering playing a "dual" game on the graph complement $G^{c}\_\pi = G\_{R(\pi)}$, which contains those edges $(i,j)$ for which $i$ and $j$ are in the *correct* order in the permutation. The dual game to Disconnect is:

> **Reconnect.** Players alternately remove vertices from a graph $G$. The player that produces a complete graph is the winner.

Depending on the particular permutation, one of these games may seem simpler than the other to analyze. The advantage of graph representation is that it is clear that disconnected components of the graph are separate games, and so one hopes for some reduction in complexity. It also makes the symmetries of the position more apparent. Unfortunately, the winning conditions are non-standard... the permutation game will always end before all moves are used up, giving it something of a *misère* character. In particular, the nim-value cannot be calculated as the nim-sum (binary XOR) of the nim-values of the disconnected components.

---

For Disconnect, it is not hard to see that for any graph $G$ and any even $n$, the game $G \cup \bar{K}\_n$ is equivalent to $G$ (where $\bar{K}\_n$ is the edgeless graph on $n$ vertices). To prove it, we need to show that the disjunctive sum $G + G\cup\bar{K}\_n$ is a second-player win. The proof is by induction on $|G|+n$. If $G$ is edgeless, then the first player loses immediately (both games are over). Otherwise, the first player can move in either $G$, and the second player can copy his move in the other one (reducing to $G' + G'\cup \bar{K\_n}$ with $|G'|=|G|-1$); or, if $n\ge 2$, the first player can move in the disconnected piece, and the second player can do the same (reducing to $G + G\cup\bar{K}\_{n-2}$).

This shows that any graph $G$ is equivalent to $H \cup K\_p$, where $H$ is the part of $G$ with no disconnected vertices, and $p=0$ or $1$ is the *parity* of the number of disconnected vertices in $G$. All games in an equivalence class have the same nim-value, and moreover, the equivalence relation respects the union operation: if $G \sim H \cup K\_p$ and $G' \sim H' \cup K\_{p'}$ then $G \cup G' \sim (H \cup H')\cup K\_{p\oplus p'}$. Moreover, one can see that the games in $[H \cup K\_0]$ and $[H \cup K\_1]$ have different nim-values unless $H$ is the null graph: when playing $H + H \cup K\_1$, the first player can take the isolated vertex, leaving $H+H$, and then copy the second player's moves thereafter.

I do not know any related decomposition results for Reconnect.

---

Two special types of permutations correspond to particularly simple heap games.

1. The first is an *ascending run of descents*, e.g., $32165487$. When $\pi$ takes this form, the graph $G\_{\pi}$ is a union of disjoint cliques, and the game of Disconnect reduces to a game on heaps: players alternately remove a single bean from a heap *until all heaps have size $1$*.
2. The second is a *descending run of ascents*, e.g., $78456123$. When $\pi$ takes this form, the graph $G^{c}\_{\pi}$ is a union of disjoint cliques, and the game of Reconnect reduces to a game on heaps: players alternately remove a single bean from a heap *until there is only one heap left*.

A little thought shows that these two different games on heaps (we can call them **1-Heaps** and **One-Heap**, at some risk of confusion) are, in fact, themselves isomorphic. Both can be represented by a game on a Young diagram (as initially proposed by @domotorp) in which players alternate removing a lower-right square until only a single row is left. This is obviously the same game as 1-Heaps when columns correspond to heaps, and the same game as One-Heap when rows correspond to heaps.

A key element of this game, which extends to Disconnect and Reconnect, is that the duration is related to the final game state in a simple way. When it is your turn, you will win if the game has an odd number of moves remaining, including the one you're about to make. Since a single square is removed each move, this means you want the number of squares remaining at the end of the game to have the opposite parity that it has now. Moreover, the number of squares will have the same parity on all of your turns; so you know from the outset what parity you want the final count to have. We can call the two players Eve and Otto, according to whether the final count must be even or odd for them to win. Eve always moves in states with odd parity and produces states with even parity, and Otto is the opposite.

In his answer, @PeterShor gives a complete analysis of One-Heap. Without repeating the proof, the upshot is the following:

* Otto likes $1$-heaps and $2$-heaps, and can tolerate a single larger heap. He wins if he can make all heap sizes except one $\le 2$, at least without giving Eve an immediate win of the form $(1,n)$. An optimal strategy for Otto is to always take from the second-largest heap except when the state is $(1,1,n>1)$, when he should take from the $n$. Otto will lose if there are too many beans in big heaps to start with.
* Eve dislikes $1$-heaps. She wins if she can make all heap sizes $\ge 2$. An optimal strategy for Eve is to always take from a $1$-heap, if there are any, and never take from a $2$-heap. Eve will lose if there are too many $1$-heaps to start with.

As noted, this gives optimal strategies for 1-Heaps as well, although they are somewhat more awkward to phrase (and I may well be making an error in primary-to-dual "translation"). In the game of 1-Heaps:

* Otto likes one or two large heaps, and can tolerate any number of $1$-heaps. He wins if he can make all but the two largest heaps be $1$-heaps, at least without giving Eve an immediate win of the form $(1,1,\dots,1,2)$. An optimal strategy for Otto is to always take from the third-largest heap, or from the smaller heap when there are only two heaps.
* Eve dislikes a gap between the largest and second-largest heaps. She wins if she can make the two largest heaps the same size. An optimal strategy for Eve is to always take from the largest heap, if it is unique, and never if there are exactly two of the largest size.

As @PeterShor notes, it isn't clear how (or if) these analyses could be extended to the more general games of Disconnect and Reconnect.

> **Comments:**
> **username_1**: I think that this kind of games are collectively referred to as “vertex deletion games.”  But I agree with you that the winning condition is quite nonstandard in that it refers to the global property of the graph instead of local properties such as the degree of a vertex.  
> **username_8**: The constructed graph is called a permutation graph (http://en.wikipedia.org/wiki/Permutation_graph) in the literature.  Some structural properties might help.  
> **username_4**: @Yoshio: That's a good point.  The permutation game is isomorphic to the graph game, but the starting graphs aren't arbitrary.  So even if the general graph game is hard to analyze, it's possible that when restricted to this subclass of graphs, it becomes simpler.  
> **username_9**: in terms of the computational problem of determining the winner i guess the more appropriate term might be "reduction"; that captures the fact that the graph game might imply a harder problem.  
> **username_0**: On the other hand, the more general formulation might be easier to prove hard.  Variants of vertex-deletion games are known to be PSPACE-hard, for example: http://www.emis.ams.org/journals/INTEGERS/papers/a31int2005/a31int2005.pdf  
> **username_4**: I've added a question on this kind of game specifically over at math.SE (http://math.stackexchange.com/questions/95895/analyzing-a-class-of-vertex-deletion-games).  Incidentally, since permutation graphs are circle graphs, an alternate formulation is the following: Players take turns removing chords from an initial set; the player that leaves a non-intersecting set of chords is the winner.  

---

### Answer by username_10 on 2012-01-07. Score: 3

I've implemented an $O(2^n n)$ solution for quick hypothesis checking. [Feel free to play with it](http://ideone.com/Owg32). If you don't have C++ compiler locally, you can run it on different inputs remotely using "upload with new input" link.

@JɛﬀE It happened that (1,4,3,2) has value \*1, not \*2 as you suggested.

> **Comments:**
> **username_0**: Oops, my mistake.  Fixed the question:  g(1,3,2) = mex{g(1,3), g(1,2), g(3,2)} = mex{0, 0, *1} = *2.  
> **username_10**: @JɛﬀE It's interesting that for $n \le 10$ SG-value of any position is not greater than 2. I'm trying to prove that now for arbitrary $n$, although I dunno how will that help.  
> **username_6**: @maldini: it gives hope that the game has some nice properties, which might make it tractable. I wonder what happens to the game generalized to graphs, or the game just generalized to perfect graphs.  

---

### Answer by username_7 on 2011-12-30. Score: 3

Edit 5th of Jan: In fact the One Heap Game described below is a special case of the problem, i.e. when the numbers follow each other in a specific way such that the first group is bigger than the second group which is bigger than the third etc. and the numbers in each group are increasing. E.g. 8, 9, 4, 5, 6, 7, 2, 3, 1 is such a permutation. So I propose to solve this special case first.

Disclaimer: I no longer claim that the below proof is correct, see e.g. the comment of Tsuyoshi which shows that deleting a number from a permutation will give a diagram not obtainable by deleting a square from the diagram of the permutation. I left the answer here to show that this approach does not work, plus since it contains another simple game.

The game has a very simple other formulation thanks to Young Tableaux. I am sure that it can be analyzed from there as other games and it will yield a linear time algorithm.

First define the following game on Young Diagrams: At each turn, if the current diagram is horizontal (all squares in one line), the current player loses and the other player wins; otherwise, the current player removes one of the bottom-right squares, and play passes to the other player.

Now order the sequence of numbers into a Young Tableaux. The main claim is that the winner of the original game is the same as the winner as the diagram game starting with this shape. To see this, notice that whenever the players delete a number, the diagram of the new sequence can be achieved by deleting a bottom-right square of the diagram. Moreover, any such diagram can be achieved by deleting the number from the respective bottom-right square. These statements follow from standard Young Tableaux theory.

Although this diagram game is simple enough, it is trivially equivalent to the following game, which seems more standard:

One Heap Game: The players are given some heaps with some pebbles in each. At each turn, if their is only one heap left, the current player loses and the other player wins; otherwise, the current player removes a pebble from a heap, and play passes to the other player.

If there is a simple solution to the heap game (and I strongly believe there is one) we also get a solution to the original game: Just put the sequence in a Young Tableaux, and transform its diagram into heaps.

Unfortunately I do not see which heap positions are winning/how to determine the Sprague–Grundy values. I checked a few cases by hand, and the following are the losing positions with at most 6 pebbles:

one heap; (1,1,1); (2,2); (3,1,1); (2,1,1,1); (1,1,1,1,1); (4,2); (3,3); (2,2,2).

Anyone can solve this game?

Edit: Peter Shor can, see his answer!

> **Comments:**
> **username_4**: Can you give at least one example showing how a particular permutation is turned into a Young Tableau and how the same game (number removal until an ascending sequence is reached) is played on the Tableau?  In particular I don't understand what it means to remove "one of the bottom-right squares".  
> **username_7**: Eg. 1324 becomes (124,3), now Alice deletes 3 to make it (124) and wins. Hm, but if she deletes 2, then it becomes (14,3), strange, I thought deleting a number from a sequence is equivalent to deleting a square from the tableau. Then maybe my whole reasoning is incorrect...  
> **username_4**: Yes, it doesn't seem like it quite works: to get the correct tableau after a number is removed, you sometimes need to propagate some numbers back up to earlier rows.  
> **username_0**: @domotorp: Your counterexample isn't a counterexample.  If Alice deletes 2, then the Young tableau of the permutation becomes (134;).  So deleting 2 has precisely the same effect on the Young diagram as deleting 3, which makes sense, because 124 and 134 are the same permutation.  
> **username_4**: @JɛﬀE: No, it is a counterexample.  Of course the Young tableaux can be used to represent permutations; the question is whether you can actually play the game by modifying the tableaux directly, and whether the legal moves are easy to represent in that format.  The original idea was that a legal move on the tableau would be just "remove a square" (and I guess move the rest of that row to the left?)  $(124,3)$ is a counterexample because removing $2$ doesn't give $(14,3)$; instead, removing a single square affects multiple rows.  
> **username_1**: Here is a counterexample to a weaker claim that removing a number from a permutation corresponds to a removing one of the bottom-right cells from the corresponding Young _diagram_ (instead of Young _tableau_).  Let n=5, and consider a position specified by the permutation [4,1,3,5,2] (that is, σ(1)=4, σ(2)=1, and so on), and remove 3 from it.  The corresponding Young diagram before the move is 5=3+1+1, but the corresponding Young diagram after the move is 4=2+2, which is not obtained from removing one cell from 3+1+1.  
> **username_6**: And the permutation [5,4,1,2,3] has the same Young diagram as [4,1,3,5,2], but you cannot reach the Young diagram 4=2+2 from it. So the game depends on more than the shape of the Young tableau.  
> **username_0**: Hooray for constructive misunderstanding!  
> **username_1**: @JɛﬀE: Yeah, this is much more useful than a proof of mere existence of misunderstanding.  
> **username_7**: And it even gives an easier problem, as I have discovered today! (see edit at top)  
> **username_6**: Here's what I believe is the strategy for domotorp's game. If all heaps are of size 1 or 2, with at least one heap of size 1, the losing positions are those with an odd number of size-1 heaps. The winning strategy is to always take a stone from a size-2 heap. This guarantees that the last heap has exactly one stone in it. (Continued.)  
> **username_6**: If all the heaps are of size at least 2, then the losing positions are those with an even number of odd-size heaps. The winning strategy is to take a stone from a size-1 heap, if one exists, and otherwise from any odd-size heap. This guarantees that the last heap always has an even number of stones in it. If there are heaps of both size 1 and size $\geq$ 3, then it comes down to a race between the two players, with one player trying to get rid of the heaps of size 1, and the other trying to get rid of heaps of size $\geq 3$.  
> **username_7**: @Peter: I am not sure your argument is correct. If all heaps are of size 1 or 2, then the losing positions are when we have an odd number AND at least three size-1 heaps. I do not know the answer to the general version.  
> **username_4**: @domotorp: I have edited my answer to note the equivalence of the permutation game to a heap game in the special case of permutations like $894567231$.  Interestingly, the same heap game (with a dual starting position) can be used to analyze the permutation game for the reversal of such a permutation, e.g., $132765498$.  
> **username_7**: @mjq: Interesting, thx!  
> **username_4**: @Peter is basically correct.  One of the players (Eve) wants the game to end with an even-sized heap; the other (Otto) wants the game to end with an odd-sized heap.  Eve wins if she can make all heaps $\ge 2$ (since after that she can remove $1$-heaps as fast as they are created).  Otto wins if he can make all heaps $\le 2$ (since after that he can create $1$-heaps as fast as they are destroyed, until all heaps are $1$-heaps).  Optimal play for Eve is to destroy $1$-heaps whenever possible, and never create any.  Optimal play for Otto is to always take from the largest heap.  
> **username_7**: @mjq: Why is it good for Eve to destroy all 1-heaps? I think the game is more complicated than that.  
> **username_6**: @domotorp: I've posted a corrected version of my comments as an answer (it only answers your special case, but it's way too long to put in comments).  

---

