An Illustrative Example: The Core and Network Flow

From IFORS Education Resources
Jump to: navigation, search

By: Vincent Conitzer


Introduction

We will now consider an example from cooperative game theory (also known as coalitional game theory), the less-known sibling of noncooperative game theory (under which, for example, the zerosum games studied earlier fall). Consider a setting with a set A of agents. Any subset S C A, in this context also known as a coalition of agents, can work together as a team; when they do, they generate a total value (say, profit) of v(S), which they can distribute among themselves as they see fit. (There are also variants where there are limitations on how the value can be distributed, but we will not consider such variants here.) The function v is known as the characteristic function. We would like the grand coalition of all agents A to work together. If they do so, they will generate a value of v(A), which they need to distribute among themselves. Let us say that agent i receives r(i). We require that P i2A r(i) < v(A): the agents cannot distribute more value than they generate. We now ask whether this payoff vector is stable. That is, it may be the case that there is a coalition S C A such that P i2S r(s) < v(S), so that the agents in S would be better off breaking off from the grand coalition and forming a coalition on their own. (It is not hard to see that in this case, the agents in S can distribute the v(S) in such a way among themselves that each i 2 S receives more than the r(i) she received before.) Such a coalition is called a blocking coalition. The existence of a blocking coalition implies that the payoff vector is not stable, in a sense. A payoff vector that is stable, that is, one for which no blocking coalition exists, is said to be in the core.


Link to material: http://www.cs.duke.edu/courses/spring08/cps296.2/core_network_flow.pdf


Personal tools