Keishun Suzuki (Chiba University)
25 July, 2016
13. Nucleolus
Advanced Microeconomics, Spring 2016
Ch.4 Cooperative Game
Recap of the last class
• � = � ∈ ℝ3 � ≤ �� ≤ ��, � ≤ �� ≤ �, � ≤ �� ≤ �,
�� + �� + �� = ��}.
• ( ��
�, ��
�, ��
�) = ( ��. �, �, �. �).
Venture company game.
� � = �, � � = �, � � = �.
� �, � = ��, � �, � = ��, � �, � = ��.
� � = ��.
⟹The Shapley value is not in the core of the game.
permutation ��� ��� ���
� � , � � , � � 6 14 4
� � , � � , � � 6 9 9
� � , � � , � � 16 4 4
� � , � � , � � 14 4 6
� � , � � , � � 13 9 2
� � , � � , � � 14 8 2
Total 69 48 27
Shapley value 11.5 8 4.5
Marginal contribution
Introduction
• The Shapley value is unique but not always in the core.
It may be blocked by some coalitions.
• Schmeidler. (1969), "The nucleolus of a characteristic function
• We study “nucleolus” today.
It is always unique.
If the core is not empty set, nucleolus is always
in the core.
Nucleolus gives a “fair” payoff vector.
Bankruptcy Problem
• A man dies leaving an estate of size E and debts to creditors
1,…,n of �
1, … , �
�. However, � < �
1+ ⋯ + �
�.
→ How much should each creditor get?
• In the Babylonian Talmud, a strange way to distribute the
estate in 3 person’s case is written:
�� = ��� �� = ��� �� = ���
� = ��� ���/� ���/� ���/�
� = ��� �� �� ��
� = ��� �� ��� ���
•
Aumann and Maschler (1985)
• They showed that the distribution in the Talmud is the nucleolus
of the corresponding bankruptcy games as follows:
• E=100
� 1 = � 2 = � 3 = � 1,2 = � 2,3 = � 1,3 = 0,
� 1,2,3 = 100
• E=200
� 1 = � 2 = � 3 = � 1,2 = � 1,3 = 0,
� 2,3 = 100, � 1,2,3 = 200
• E=300
� 1 = � 2 = � 3 = � 1,2 = 0, � 2,3 = 200,
Excess
The excess of coalition S for a payoff vector � = (��, … , ��) is defined as � �, � = � � − ∑�∈� �� .
Definition 19. Excess of coalition S for a payoff vector �
• A large excess indicates that the payoff vector � is
difficult to accept for the players in coalition S.
They have a strong incentive to break away from S.
• The excess is non-positive for any imputations in the core
since it must be � � ≤ ∑
�∈��
�for any S.
Excess vector
• There are �
�coalitions in N-person’s game.
• We can number them as �
1, �
2, … , �
2�which is arranged
according to the values of � �, � in descending order.
� �1, � ≥ � ��, � ≥ ⋯ ≥ � ���, �
The vector that arranges �(��, �) in descending order is called the excess vector for a payoff vector x, which is defined as
�(�) = (��(�), ��, (�) … , ���(�)), where �� � = � ��, � . Definition 20. Excess vector for �
Venture company game.
� � = �, � � = �, � � = �.
� �, � = ��, � �, � = ��, � �, � = ��.
� � = ��.
Derive the excess vector for � = �
�, �
�, �
�= ( ��. �, �, �. �).
Exercise
� {�}, � =
� {�}, � =
� {�}, � =
� {�}, � =
� {�, �}, � =
� {�, �}, � =
� {�, �}, � =
� {�}, � =
�(�) =
Lexicographical order
For any two payoff vectors, x and y, such that � � ≠ � � ,
�(�) is smaller than �(�) in lexicographical order if for some 1 ≤ � ≤ 2�, we have �� � = ��(�) for � = 1, … , � − 1 and
�� � < ��(�). Then, the order is denoted by � � ≤� �(�), and we also say that x is more acceptable than y.
Definition 21. Lexicographical order
� � = −1, −2, −3, −4, −5, −6, −8, −10
� � = 3, 0, −1, −2, −3, −6, −10, −12
� � = 3, 0, −1, −2, −4, −8, −12, −16
� � �(�)
� � �(�)
� � �(�)
Nucleolus
• For any imputation, each coalition has a different value of complaint (excess).
If there is no imputation � ∈ �(�) that is more acceptable than an imputation � ∈ �(�), then x is the nucleolus in the game. Formally, we can define as follows:
� � = � ∈ � � � � ≤� � � , ∀� ∈ � � . Definition 22. Nucleolus
• Nucleolus gives an imputation that minimizes the largest excess. When such imputation is not unique, nucleolus focuses on the second largest excess.
�-core
• �� � is identical to the core.
• When ε ≤ 0, the �-core is a subset of the core.
• �′ < � ⇒ ��′ � ⊂ �� �
• When � is sufficiently small, �� � may be empty.
A set of imputations that the excess is smaller than � is called
�-core. Formally, it is given by
�� � = � ∈ � � �(�, �) ≤ �, ∀� ⊂ �, � ≠ � . Definition 23. �-core
The least core
An intersection of nonempty �-core is the least core. Formally,
�� � = �
�� � ≠�
��(�) . Definition 24. The least core
• �� � = ���(�) where �0 = min
�∈�(�) max{�(�, �)|� ⊂ �, � ≠ �}
For any game (N,v) that has a nonempty set of imputations, the nucleolus � � ∈ ��(�) for all � ∈ ℝ such that �� � ≠ �. In addition, � � ∈ �� � holds.
Proposition 9.
The proof of Proposition 9
• Suppose that � � ∉ �� � for some �. (�� � is nonempty.)
• Then, there exists some coalition S such that
� �, � � > �.
• By the definition, for an imputation � ∈ �� � , we have
� �, � ≤ � for all � ⊂ �. Then,
� � <� � � � .
• But this contradicts to the definition of nucleolus. Therefore,
� � ∈ �� � holds for any � if �� � is nonempty.
Zero-normalized Venture company game.
�′ � = �, �′ � = �, �′ � = �.
�′ �, � = ��, �′ �, � = �, �′ �, � = �.
�′ � = ��.
Setting up venture companies
• The conditions for � -core is
��′ + ��′ + ��′ = �(�)
�′ �, � − ��′ − ��′ ≤ �
�′ �, � − ��′ − ��′ ≤ �
�′ �, � − ��′ − ��′ ≤ �
−��′ ≤ �, −��′ ≤ �, −��′ ≤ �
−� ≤ ��′ ≤ � + �
−� ≤ ��′ ≤ � + �
−� ≤ ��′ ≤ � + �
The case of � = −�/�
�: (��, �, �)
��
��′ = �
��′ = �. �
��′ = �/�
−� ≤ ��′ ≤ � + �
The �-core when � = �
�: (��, �, �)
�: (�, �, ��)
�: (�, ��, �)
��
��′ = �
��′ = �
��′ = �
�-core (�=0)
The �-core when � = −�/�
�: (��, �, �)
�: (�, �, ��)
�: (�, ��, �)
��
��′ = �. �
��′ = �. �
��′ = �. �
�-core
The �-core when � = −�
�: (��, �, �)
�: (�, �, ��)
�: (�, ��, �)
��
��′ = �
��′ = �
��′ = �
���������
The nucleolus of the game
• A lower � makes �� � smaller when −1 < � < 0.
• In the game, �� � shrinks to a point in the core when � = −1.
This is the least core of the game.
Since � � ∈ �� � , this point is the nucleolus.
• The nucleolus of zero normalized venture company game is
��′ , ��′ , ��′ = (7,4,1)
• Then, the nucleolus of original game is
�(�) = (��, �, �)
Example
� � = � � = � � = �
� �, � = �, � �, � = ��, � �, � = ��.
� � = ��.
• The conditions for � -core is
�� + �� + �� = �(�)
� �, � − �� − �� ≤ �
� �, � − �� − �� ≤ �
� �, � − �� − �� ≤ �
−�� ≤ �, −�� ≤ �, −�� ≤ �
−� ≤ �� ≤ �� + �
−� ≤ �� ≤ �� + �
−� ≤ �� ≤ �� + �
The �-core when � = �
�: (��, �, �)
�: (�, �, ��)
�: (�, ��, �)
�� = ��
�� = ��
�� = �� �-core(�=0)
The �-core when � = −�
�: (��, �, �)
�: (�, ��, �)
�� = ��
�� = �
�� = ��
�-core (�=-5)
�� = �
�: (�, �, ��)
The excess of a coalition for � ∈ �� �
• �� � vanishes when � < −5.
• Therefore, �−� � = {(�, �, �� − �)|� ≤ � ≤ ��} is the least core of the game: �−� � = ��(�). (Hence, �0 = −5)
This game is an example that the least core is not a point.
• The excess of each coalition for � ∈ �−� � is
� �, � , � = � �, � − �� − �� = −� − �
� �, � , � = � �, � − �� − �� = −�
� �, � , � = � �, � − �� − �� = −�� + �
� � , � = −�� = −�, � � , � = −�� = −�,
Minimization of the 2nd largest excess
• We no longer diminish the excess of {A} and {B,C} for any imputation in the least core.
• Therefore, we next reduce the excess of other coalitions by finding
�1 = �∈�min
�0(�) max{�(�, �)|� ⊂ �, � ≠ �} where � = { � , � , �, � , {�, �}}.
• This problem can be rewritten as
�1 = min5≤�≤15 max{−5 − �, −�, −20 + �, −25 + �} .
⇒ �1 = min5≤�≤15 max{−�, −20 + �} .
Linear programming problem
−�� + �
−�
15 20 10
5
�
�
�= −��
The nucleolus of the game
• At � = 10, the second largest excess is minimized and the
value is �
1= −10 .
• Such imputation is � = (�
�, �
�, �
�) = (5, 10, 15), and this
is the nucleolus of the game since there is no imputation that
is more acceptable than � .
• The nucleolus corresponds to
−�� ≤ �� ≤ �� + ��
−�� ≤ �� ≤ �� + ��
−�� ≤ �� ≤ �� + ��
�� + �� + �� = ��
where �� = −� and �� = −��.
The position of nucleolus
�: (��, �, �)
�: (�, ��, �)
� = (�, ��, ��)
�: (�, �, ��) The least core
Graphically solving the nucleolus
�: (��, �, �)
�: (�, ��, �)
�
�: (�, �, ��)
�� = ��
�� = �
�� = ��
�� = ��
�� = ��
Bankruptcy game in Talmud
• This game is identical to the case of � = 300 of bankruptcy
game.
� � = � � = � � = �
� �, � = �, � �, � = ��, � �, � = ��.
� � = ��.
→ � = (�
�, �
�, �
�) = ( �, ��, ��) ,
�� = ��� �� = ��� �� = ���
� = ��� �� ��� ���
Literature
• Aumann and Maschler (1985):“Game Theoretic Analysis of a
bankruptcy Problem from the Talmud,” Journal of Economic
Theory, vol.36, pp.195-213.
• Chakravarty, Mitra, and Sarkar (2015): “A course on
cooperative game theory,” Cambridge University Press.
• 中山, 船木, 武藤 (2008)「協力ゲーム理論」, 勁草書房.
• 岡田 (2011) 「ゲーム理論 新版」, 有斐閣.
• 船木 (2012) 「ゲーム理論講義」, 新世社.