<p>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$.  </p>

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

<blockquote>
  <p>Bloch (1996): "Sequential Formation of Coalitions in Games with Externalities and Fixed Payoff Division", <em>GEB</em></p>
</blockquote>

CC BY-SA 4.0
2018-05-09T12:45:37.947Z
This does not answer your own question. Which part of it is the closed formula?
Giskard
CC BY-SA 4.0
2018-05-09T14:01:58.400Z
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
CC BY-SA 4.0
2018-05-09T14:16:22.930Z
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
CC BY-SA 4.0
2018-05-09T14:50:49.130Z
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
CC BY-SA 4.0
2018-05-09T12:13:26.193Z
2018-05-09T12:13:26.193Z
clueless
<p>Let the set of players be $N=\{1,\dots,n\}$. </p>

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

<ul>
<li>Each player chooses a <strong>number</strong> 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.</li>
<li>Each player has to choose at least 1 player, if still available. </li>
<li>Each player moves exactly once.</li>
<li>The game is with perfect information.</li>
</ul>

<p>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&lt;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\}$.</p>

<p>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}\}$. </p>

<p>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\} &amp; \text{if } n-\sum_{j=0}^{i-1}s_j\ge 1 \\
\{0\} &amp; \text{otherwise}.
\end{cases}
\end{equation}</p>

CC BY-SA 4.0
2018-05-07T23:15:30.283Z
2018-05-07T23:59:07.387Z
2018-05-07T23:59:07.387Z
Herr K.
<p>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$.</p>

<ul>
<li>What's a proper definition of this simple game? What are the strategy sets? </li>
</ul>

CC BY-SA 4.0
2018-05-07T18:22:41.053Z
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
CC BY-SA 4.0
2018-05-07T19:33:00.903Z
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
<game-theory><extensive-games>
Proper definition of extensive form game
clueless
# Proper definition of extensive form game

(Asked by: username_0 on 2018-05-07)

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?

**Tags:** game-theory, extensive-games

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  

---

## 2 answers

### Answer by username_2 on 2018-05-07. Score: 2 | Accepted answer

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}


---

### Answer by username_0 on 2018-05-09. Score: -1

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*

> **Comments:**
> **username_1**: This does not answer your own question. Which part of it is the closed formula?  
> **username_0**: 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 username_2., no? You're right that now we don't get the same $S_i$'s as in the question, though.  
> **username_1**: 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.)  
> **username_0**: 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.  

---

