# Computing the core in a transferrable utility game

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.

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 (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.
• 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 Dec 20 '15 at 16:32
• @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 Dec 20 '15 at 17:19