In game theory, suppose we have a set of players $\mathcal{N}=\{1, 2, \ldots, n\}$, a set of actions $\mathcal{A}_i$ of player $i\in\mathcal{N}$, and a payoff function $u_i$ of player $i\in\mathcal{N}$ defined as $u_i:\mathcal{A}_1\times\mathcal{A}_2\times\ldots\mathcal{A}_n\mapsto\mathbb{R}$.

Further, suppose that the action set of a player $i\in\mathcal{N}$ changes every time $i$ chooses an action.

Example: For example, say $\mathcal{A}_i=\mathcal{A}\,\forall\,i$. Now, if player $i$ chooses $a_i\in\mathcal{A}$, then player $j\neq i$ can choose an action $a_j$ from $\mathcal{A}\backslash\{a_i\}$. If player $j$ does choose $a_j$, then player $k\neq i$ and $k\neq j$ can choose an action $a_k$ from $\mathcal{A}\backslash\{a_i, a_j\}$ and so on.

How do we define such games? Is there any reference to such games? Is there anyway to model these kind of games?


This is equivalent to a serial dictatorship in an assignment problem. This mechanism is discussed in many papers. You could have a look at Strategyproof multiple assignment using quotas (Papai, 2000), Coalitional strategy-proof and resource-monotonic solutions for multiple assignment problems (Ehlers and Klaus, 2003) or Strategy-proof, efficient, and nonbossy quota allocations (Hatfield, 2009). They're all regarding basically the same question: the multiple assignment problem. Each shows that serial dictatorships are the only mechanisms with some desirable properties in this context. For your purposes however, all that matters is that they define serial (or, slightly differently, sequential) dictatorships. Those papers come to mind for me because they relate to my own interests. There might be better references for your interests.

You might ask why this is not really in game theory literature, but rather assignment / matching. I think the reason is the game you describe is not interesting if $u_i = f(a_i)$, because each agent will just pick her preferred remaining action. If $u_i = f(a_i,a_{-i})$, then it's potentially an interesting game. I haven't seen that case analyzed. In fact, I've never seen the game you describe analyzed in game theory stuff.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.