# Game theory question- boxes

There are two players 1 and 2, and the game begins with player 1 selecting one of the boxes marked 1 to 16. Following such a selection, the selected box, as well as all boxes in the square of which the selected box constitutes the leftmost and lowest corner, will be deleted. For example, if he selects box 7, then all the boxes, 3, 4, 7 and 8 are deleted. Similarly, if he selects box 9, then all boxes 1 to 12 are deleted. Next it is player 2’s turn to select a box from the remaining boxes. The same deletion rule applies in this case. It is then player 1’s turn again, and so on. Whoever deletes the last box loses the game? What is a winning strategy for player 1 in this game?

I can't even begin to form a payoff matrix or anything for this question, do we have to consider ALL the possible alternatives?

• You have to use dynamic programming. – Jamie Lannister Apr 29 '15 at 2:18
• forming sequential subgames? – dexter Apr 29 '15 at 2:19
• Yes. start with the case when there's one left, then when there's four, etc... and look for an invariant strategy. – Jamie Lannister Apr 29 '15 at 2:23
• It sounds like you might be getting confused by mixing concepts from combinatorial game theory with those from economic game theory. A payoff matrix suggests that players 1 and 2 make their choices simultaneously and are rewarded or penalized according to the entry in the matrix; this is an economic concept that doesn't apply to turn-based games. – Théophile Apr 29 '15 at 2:30
• There's no payoff matrix. Your strategy is a best response function that is recursive based on the instance at hand. You find this function via dynamic programming. It's analogous to the continuous case where you find an equilibrium best response function of quantity in the Cournet model. In short, you're not looking for a fixed point in a finite dimensional space but an invariant strategy in a function space. Hope that makes sense. Took me a while to get that the first time I saw it. – Jamie Lannister Apr 29 '15 at 2:46

For a square board like yours, the first player has an easy win by taking the square diagonally next to the poison square, in this case $10$. The first player can then maintain equal lengths on the vertical and horizontal legs, which forces the second player to take $13$.