# Proper definition of extensive form game

Consider the following game: Let $N := \{1,2,3,4\}$ denote a set of agents. Going from 1 to 4 each agent can decide how many of the remaining agents he wants to integrate into a coalition. The strategy sets are given by $S_1 := \{1,2,3,4\}$, $S_2 := \{1,2,3\}$, $S_3 := \{(1,1),(1,2),(2,1),(2,2)\}$ and $S_4 := \{(1,1,1)\}$. I want to generalize the game for $|N| = n$. So basically agent 1 picks a number $s_1 \in N$. Then agent $1 + s_1$ picks a number $s_{1+s_1} \in \{1,\ldots,n-s_1\}$ and so forth. Eventually there exists an agent who integrates all the remaining agents $\exists j \in N : s_j = 1+n-j$.

• What's a proper definition of this simple game? What are the strategy sets?
• What do you mean by 'proper definition'? Also, aren't your strategy sets already given? Are you looking for a closed formula for the strategy sets? – Giskard May 7 '18 at 18:22
• Well, by proper I orginally meant a tuple of nodes, edges, histories etc. But that's probably overkill anyway. For my purpose it would suffice to have a closed formula of strategy sets $S_i$ for $i \in \{1,\ldots,n\}$, where $A_i = \{1,\ldots,n+1-i\}$ denote the action sets. – clueless May 7 '18 at 19:33

Let the set of players be $N=\{1,\dots,n\}$.

According to my understand your description of the game, I take the following statements to be true:

• Each player chooses a number of players to integrate, not players with specific identities. As a result, the player making the choice may or may not be included in the coalition.
• Each player has to choose at least 1 player, if still available.
• Each player moves exactly once.
• The game is with perfect information.

Under the above interpretation, player $i$'s ($i\ge2$) action space would be $A_i=\{0,1,\dots,n+1-i\}$, as, in principle, $i$ could choose at most $n+1-i$ other players (when all players $j<i$ chose $1$) and at least $0$ (when all previous players have exhausted the player list). An exception applies to the first player, where the option $0$ is not feasible. Thus $A_1=\{1,\dots,n\}$.

Player 1's strategy space would be $S_1=\{1,\dots,n\}$. Player 2's would be $S_2=\{1,\dots,n-s_1\}$, since after $s_1$ players are picked by player 1, there are only $n-s_1$ players left to be picked by player 2. Carrying this argument forward, player $i$'s strategy space would be $S_i=\{1,\dots,n-s_1-\cdots-s_{i-1}\}$.

Generalizing from the above reasoning and taking into account boundary cases, let history at stage $i$ be $h^i=(s_0,s_1,\dots,s_{i-1})$, where we set $s_0=0$. (In general, though, stages should be indexed by a parameter different from the player index. But in your game, since each player moves exactly once, we can use the same index for stages as well as players to economize notation.) The history dependent strategy space for player $i$ would thus be \begin{equation} S_i(h^i)= \begin{cases} \{1,\dots,n-\sum_{j=0}^{i-1}s_j\} & \text{if } n-\sum_{j=0}^{i-1}s_j\ge 1 \\ \{0\} & \text{otherwise}. \end{cases} \end{equation}

I was carefully rereading the underlying paper (Bloch, 1996) and found what I was looking for. Let $N = \{1,\ldots,n\}$ denote the set of agents and let $\Pi_{\{1, \ldots, i-1\}}$ denote the set of coalition structures of $\{1, \ldots, i-1\}$ for all $i \in \{2,\ldots,n\}$. A strategy in the game of coalition size is a mapping $s_i : \Pi_{\{1, \ldots, i-1\}} \to \{1, \ldots, n-(i-1)\}$ for all $i \in \{2,\ldots,n\}$. Further $s_1 \in N$.

Example with $n=4$. With some abuse of notation (saving curly brackets) we get \begin{align} &s_1 \in \{1,2,3,4\}\\ &s_2:\{1\} \to \{1,2,3\}\\ &s_3:\{\{1,2\},\{12\}\} \to \{1,2\}\\ &s_4:\{\{1,2,3\},\{12,3\},\{1,23\},\{123\}\} \to \{1\} \end{align}

Bloch (1996): "Sequential Formation of Coalitions in Games with Externalities and Fixed Payoff Division", GEB

• This does not answer your own question. Which part of it is the closed formula? – Giskard May 9 '18 at 12:45
• What do you mean by closed formula then? In my opinion it is the mapping $s_i : \Pi_{\{1,\ldots,i-1\}} \to \{1,\ldots,n-(i-1)\} =: S_i$. That's precisely the $S_i$ of Herr K., no? You're right that now we don't get the same $S_i$'s as in the question, though. – clueless May 9 '18 at 14:01
• I would not call a definition of $S_i$ that says all elements of the set are mapping such that... a closed form. I was also a bit frustrated that you did not reveal the underlying paper in your original question and that in your answer you used none of the elements that you gave in your clarifying comment. I did some reading though and I realize now that there is no exact definition for closed form solutions. If you edit your answer I will remove the downvote. (The system does not let me change the vote without edits.) – Giskard May 9 '18 at 14:16
• It was not my intention to hide the paper. I was just confused. I'm not too familiar with extensive form games and was just thinking that a strategy set contains all potential moves at every node. Which is obviously not the case here. So I thought of reframing the game without the set of partitions, because you don't need them to define the game. – clueless May 9 '18 at 14:50