Permutation game redux This is a restatement of an earlier question.

Consider the following impartial 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?  More generally, because this is a standard impartial game, every permutation has a Sprague–Grundy value; for example, (1,2,4,3) has value *1 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.
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&#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}$).

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&#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. 

I do not know any related decomposition results for Reconnect.



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


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$.
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&gt;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.