1. 7-1 Coalitional Game Theory: Taste
  2. 7-2 Coalitional Game Theory: Definitions
  3. 7-3 The Shapley Value
  4. 7-4 The Core
  5. 7-5 Comparing the Core and Shapley value in an Example

Game Theory

Week 7: Coalitional Games

https://www.coursera.org/learn/game-theory-1/home/week/7

7-1 Coalitional Game Theory: Taste

举例：政治伙伴、商业合作联盟、建筑团队

7-2 Coalitional Game Theory: Definitions

  • Transferable utility assumption:

    可传递效用假设：

    1. the payoffs to a coalition may be freely redistributed among its members

      联盟的收益可以在其成员之间自由重新分配

    2. satisfied whenever there is a universal currency that is used for exchange in the system

      满足只要有用于系统交换的通用货币

    3. means that each coalition can be assigned a single value as its payoff

      意味着每个联盟可以分配一个单一的价值作为其收益

  • Coalitional game with transferable utility

    带可传递效用的联盟型博弈（合作博弈 Cooperative game）

    a pair \((N, v)\), where

    • \(N\) is a finite set of players, indexed by i

    • \(v : 2^N \mapsto \mathbb{R}\) associates with each coalition \(S \subseteq N\) a real-valued payoff \(v(S)\) that the coalition’s members can distribute among themselves. We assume that \(v(\emptyset) = 0\)

  • Superadditive game

    超可加的博弈

    A game \(G = (N, v)\) is superadditive if for all \(S, T \subset N\), if \(S \cap T = \emptyset\), then \(v(S \cup T) \ge v(S) + v(T)\)

7-3 The Shapley Value

\(\psi(N, v)\) is a vector of payoffs to each agent, explaining how they divide the payoff of the grand coalition, \(\psi_i(N, v)\) is \(i\)'s payoff.

  1. Axiom (Symmetry)

    For any \(v\), if \(i\) and \(j\) are interchangeable then \(\psi_i(N, v) = \psi_j(N, v)\)

  2. Axiom (Dummy player)

    For any \(v\), if \(i\) is a dummy player then \(\psi_i(N, v) = v({i})\)

  3. Axiom (Additivity)

    For any two \(v_1\) and \(v_2\), \(\psi_i(N, v_1 + v_2) = \psi_i(N, v_1) + \psi_i(N, v_2)\) for each \(i\), where the game \((N, v_1 + v_2)\) is defined by \((v_1 + v_2)(S) = v_1(S) + v_2(S)\) for every coalition \(S\)

  • Shapley value

    Given a coalitional game \((N, v)\), the Shapley value divides payoffs among players according to:

    \[\phi_i(N, v) = \frac{1}{N!} \sum_{S \subseteq N \backslash \{i\}} \lvert S \rvert ! (\lvert N \rvert - \lvert S \rvert - 1)! \left[ v(S \cup \{i\}) - v(S) \right]\]

  • Theorem

    Given a coalitional game \((N, v)\), there is a unique payoff division \(x(v) = \phi(N, v)\) that divides the full payoff of the grand coalition and that satisfies the Symmetry, Dummy player and Additivity axioms: the Shapley Value

7-4 The Core

  • Core

    核心

    A payoff vector \(x\) is in the core of a coalitional game \((N, v)\) if and only if

    \[\forall S \subseteq N, \sum_{i \in S} x_i \ge v(S)\]

The core can be empty, and not unique.

核心可以为空，也可以不唯一。

  • Simple game

    简单博弈

    A game \(G = (N, v)\) is simple if for all \(S \subset N\), \(v(S) \in {0, 1}\)

  • Veto player

    否决选手

    A player \(i\) is a veto player if \(v(N \backslash \{i\}) = 0\)

  • Theorem

    In a simple game the core is empty iff there is no veto player.

    在一个简单博弈中，当且仅当没有否决选手，核心为空。

    If there are veto players, the core consists of all payoff vectors in which the nonveto players get 0.

    如果有否决选手，则核心由所有非否决权者收益为 0 的分配向量组成。

Example: Airport Game

  • Convex game

    凸博弈

    A game \(G = (N, v)\) is convex if for all \(S, T \subset N\), \(v(S \cup T) \ge v(S) + v(T) - v(S \cap T)\)

  • Theorem

    Every convex game has a nonempty core.

    每个凸博弈都有非空核心。

  • Theorem

    In every convex game, the Shapley value is in the core.

    对于每个凸博弈，Shapley 值都在核心中。

7-5 Comparing the Core and Shapley value in an Example

UN security council: represent it as a cooperative game

举例：联合国安理会（可以看作合作博弈）