<p>Computing equilibria is an active area of research. Big name complexity theorists like Lance Fortnow are working in this area. When you have continuity, computing core allocations becomes much easier as we can usually describe the core as a linear program.</p>

<p>When the feasible allocations are discrete, we run into issues of complexity. Deciding if the core is non-empty is NP-Hard. However, if you are given the grand coalition's value and all coalition-value pairs, then the problem is in P. It isn't realistic to expect this much information though.</p>

<p>Some relevant lecture notes: <a href="http://www.cs.cmu.edu/~arielpro/mfai_papers/lecture11.pdf" rel="nofollow">http://www.cs.cmu.edu/~arielpro/mfai_papers/lecture11.pdf</a></p>

CC BY-SA 3.0
2015-12-20T21:48:58.363Z
2015-12-20T21:48:58.363Z
ml0105
<p>It depends on the set of feasible allocations for the coalitions $S$. Suppose for all $S$ a best allocation exists (the sum of the individual utilities of the members of $S$ is maximal). Then as in usual cooperative games each coalition can be assigned this best utility sum as its value $v(S)$. Let us denote the utility vector each player gets from an allocation by $x$, and the sum of utilites players get from this by $x(S)$. An allocation is in the core iff
$$
\forall S\subseteq N: x(S) \geq v(S).
$$ 
This is a slight simplification of what you wrote, because instead of comparing all allocations to $x$ we first find the 'best' allocations for each coalition and only compare these to $x$.</p>

<p>If you make further assumptions about the coalition values $v$, e.g. if you assume the game is <a href="https://en.wikipedia.org/wiki/Cooperative_game#Convex_cooperative_games" rel="nofollow">convex</a> (this is true for exchange economies) then the calculation may be simplified a bit, as the core of a convex game is the Weber set.</p>

CC BY-SA 3.0
2015-12-20T16:32:24.850Z
To confirm, your characterization of core allocations (i.e $\forall S \subseteq N: x(S) \geq v(S)$) is for transferable utility games only? I.e. this characterization is what is gained by knowing it is a transferable utility game versus a non-transferable game?
möbius
CC BY-SA 3.0
2015-12-20T17:19:37.553Z
@möbius Such an additive utility vector $x$ may not exist for NTU games, What is the 'best' that coalition $S$ can achieve is not clear. Every coalition may have its own utility possibilities frontier.
Giskard
CC BY-SA 3.0
2015-12-20T10:53:55.737Z
2015-12-20T10:53:55.737Z
Giskard
<p>An allocation $x^{*}$ is said to have the core property in a game of $N$ players if there is no coalition $S \subseteq N$ that can improve upon $x^{*}$. The core of a game is the set of allocations with the core property. </p>

<p>Now, a coalition $S$ will block an allocation $x$ if there exists a feasible $\widetilde{x}$ such that $\widetilde{x} \succ_{s} x$ for all $s \in S$.</p>

<p>As a practical matter, to determine the core of a cooperative game we usually must compute the allocations that any coalition $S$ will not block (i.e. the allocations that cannot be improved upon). If we denote this allocation as $A_{S}$ then we can write the core allocation $\mathcal{C}$ as $$\mathcal{C} = \bigcap_{S \in 2^{N}} A_{S}  $$</p>

<p>Now in any game with more than two players it can be tedious to compute the core. </p>

<p>I am wondering, if I knew the game was a <em>transferable utility game</em>, is there any way to compute the core more efficiently? </p>

<p>This is mostly a question about the consequences of a game being a transferable utility game, and whether this provides any information that is useful to computing the core. Although I am familiar with the definition of transferrable utility, I was never really comfortable with what it's practical implications were for the game. </p>

<general-equilibrium><cooperative-game-theory>
Computing the core in a transferrable utility game
möbius
# Computing the core in a transferrable utility game

(Asked by: username_0 on 2015-12-19)

An allocation $x^{\*}$ is said to have the core property in a game of $N$ players if there is no coalition $S \subseteq N$ that can improve upon $x^{\*}$. The core of a game is the set of allocations with the core property.

Now, a coalition $S$ will block an allocation $x$ if there exists a feasible $\widetilde{x}$ such that $\widetilde{x} \succ\_{s} x$ for all $s \in S$.

As a practical matter, to determine the core of a cooperative game we usually must compute the allocations that any coalition $S$ will not block (i.e. the allocations that cannot be improved upon). If we denote this allocation as $A\_{S}$ then we can write the core allocation $\mathcal{C}$ as $$\mathcal{C} = \bigcap\_{S \in 2^{N}} A\_{S} $$

Now in any game with more than two players it can be tedious to compute the core.

I am wondering, if I knew the game was a *transferable utility game*, is there any way to compute the core more efficiently?

This is mostly a question about the consequences of a game being a transferable utility game, and whether this provides any information that is useful to computing the core. Although I am familiar with the definition of transferrable utility, I was never really comfortable with what it's practical implications were for the game.

**Tags:** general-equilibrium, cooperative-game-theory


---

## 2 answers

### Answer by username_2 on 2015-12-20. Score: 3 | Accepted answer

It depends on the set of feasible allocations for the coalitions $S$. Suppose for all $S$ a best allocation exists (the sum of the individual utilities of the members of $S$ is maximal). Then as in usual cooperative games each coalition can be assigned this best utility sum as its value $v(S)$. Let us denote the utility vector each player gets from an allocation by $x$, and the sum of utilites players get from this by $x(S)$. An allocation is in the core iff
$$
\forall S\subseteq N: x(S) \geq v(S).
$$
This is a slight simplification of what you wrote, because instead of comparing all allocations to $x$ we first find the 'best' allocations for each coalition and only compare these to $x$.

If you make further assumptions about the coalition values $v$, e.g. if you assume the game is [convex](https://en.wikipedia.org/wiki/Cooperative_game#Convex_cooperative_games) (this is true for exchange economies) then the calculation may be simplified a bit, as the core of a convex game is the Weber set.

> **Comments:**
> **username_0**: To confirm, your characterization of core allocations (i.e $\forall S \subseteq N: x(S) \geq v(S)$) is for transferable utility games only? I.e. this characterization is what is gained by knowing it is a transferable utility game versus a non-transferable game?  
> **username_2**: @username_0 Such an additive utility vector $x$ may not exist for NTU games, What is the 'best' that coalition $S$ can achieve is not clear. Every coalition may have its own utility possibilities frontier.  

---

### Answer by username_1 on 2015-12-20. Score: 2

Computing equilibria is an active area of research. Big name complexity theorists like Lance Fortnow are working in this area. When you have continuity, computing core allocations becomes much easier as we can usually describe the core as a linear program.

When the feasible allocations are discrete, we run into issues of complexity. Deciding if the core is non-empty is NP-Hard. However, if you are given the grand coalition's value and all coalition-value pairs, then the problem is in P. It isn't realistic to expect this much information though.

Some relevant lecture notes: <http://www.cs.cmu.edu/~arielpro/mfai_papers/lecture11.pdf>


---

