1
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – möbius
    Dec 20, 2015 at 16:32
  • $\begingroup$ @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. $\endgroup$
    – Giskard
    Dec 20, 2015 at 17:19
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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