• 検索結果がありません。

Nucleolus Recent site activity Keishun Suzuki, 鈴木慶春

N/A
N/A
Protected

Academic year: 2018

シェア "Nucleolus Recent site activity Keishun Suzuki, 鈴木慶春"

Copied!
32
0
0

読み込み中.... (全文を見る)

全文

(1)

Keishun Suzuki (Chiba University)

25 July, 2016

13. Nucleolus

Advanced Microeconomics, Spring 2016

Ch.4 Cooperative Game

(2)

Recap of the last class

� = � ∈ ℝ3 � ≤ � ≤ ��, � ≤ � ≤ �, � ≤ � ≤ �,

+ + = ��}.

• ( ��

, ��

, ��

) = ( ��. �, �, �. �).

Venture company game.

 � � = �, � � = �, � � = �.

 � �, � = ��, � �, � = ��, � �, � = ��.

 � � = ��.

⟹The Shapley value is not in the core of the game.

(3)

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

(4)

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.

(5)

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:

= ��� � = ��� � = ���

� = ��� ���/� ���/� ���/�

� = ��� �� �� ��

� = ��� �� ��� ���

(6)

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,

(7)

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.

(8)

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

(9)

Venture company game.

 � � = �, � � = �, � � = �.

 � �, � = ��, � �, � = ��, � �, � = ��.

 � � = ��.

Derive the excess vector for � = �

,

,

= ( ��. �, �, �. �).

Exercise

� {�}, � =

� {�}, � =

� {�}, � =

� {�}, � =

� {�, �}, � =

� {�, �}, � =

� {�, �}, � =

� {�}, � =

�(�) =

(10)

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

� � �(�)

� � �(�)

� � �(�)

(11)

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.

(12)

�-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

(13)

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.

(14)

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.

(15)

Zero-normalized Venture company game.

 �′ � = �, �′ � = �, �′ � = �.

 �′ �, � = ��, �′ �, � = �, �′ �, � = �.

 �′ � = ��.

Setting up venture companies

The conditions for -core is

+ + = �(�)

�, � − � − � ≤ �

�, � − � − � ≤ �

�, � − � − � ≤ �

−� ≤ �, −� ≤ �, −� ≤ �

−� ≤ � ≤ � + �

−� ≤ � ≤ � + �

−� ≤ � ≤ � + �

(16)

The case of � = −�/�

�: (��, �, �)

��

=

= �. �

= �/�

−� ≤ � ≤ � + �

(17)

The �-core when � = �

�: (��, �, �)

�: (�, �, ��)

�: (�, ��, �)

��

=

=

=

�-core (�=0)

(18)

The �-core when � = −�/�

�: (��, �, �)

�: (�, �, ��)

�: (�, ��, �)

��

= �. �

= �. �

= �. �

�-core

(19)

The �-core when � = −�

�: (��, �, �)

�: (�, �, ��)

�: (�, ��, �)

��

=

=

=

���������

(20)

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

�(�) = (��, �, �)

(21)

Example

 � � = � � = � � = �

 � �, � = �, � �, � = ��, � �, � = ��.

 � � = ��.

The conditions for -core is

+ + = �(�)

� �, � − � − � ≤ �

� �, � − � − � ≤ �

� �, � − � − � ≤ �

−� ≤ �, −� ≤ �, −� ≤ �

−� ≤ � ≤ �� + �

−� ≤ � ≤ �� + �

−� ≤ � ≤ �� + �

(22)

The �-core when � = �

�: (��, �, �)

�: (�, �, ��)

�: (�, ��, �)

= ��

= ��

= �� �-core(�=0)

(23)

The �-core when � = −�

�: (��, �, �)

�: (�, ��, �)

= ��

=

= ��

�-core (�=-5)

=

�: (�, �, ��)

(24)

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

� �, � , � = � �, � − � − � = −� − �

� �, � , � = � �, � − � − � = −�

� �, � , � = � �, � − � − � = −�� + �

� � , � = −� = −�, � � , � = −� = −�,

(25)

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 + �} .

(26)

Linear programming problem

−�� + �

−�

15 20 10

5

= −��

(27)

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 � = −��.

(28)

The position of nucleolus

�: (��, �, �)

�: (�, ��, �)

� = (�, ��, ��)

�: (�, �, ��) The least core

(29)

Graphically solving the nucleolus

�: (��, �, �)

�: (�, ��, �)

�: (�, �, ��)

= ��

=

= ��

= ��

= ��

(30)

Bankruptcy game in Talmud

This game is identical to the case of � = 300 of bankruptcy

game.

 � � = � � = � � = �

 � �, � = �, � �, � = ��, � �, � = ��.

 � � = ��.

→ � = (�

,

,

) = ( �, ��, ��) ,

= ��� � = ��� � = ���

� = ��� �� ��� ���

(31)

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) 「ゲーム理論講義」, 新世社.

(32)

Final exam

• Final Exam (1 Aug)

 General equilibrium: 20 points

 Cooperative game: 30 points

• Questionnaire

参照

関連したドキュメント

Suzuki, “Generalized distance and existence theorems in complete metric spaces,” Journal of Mathematical Analysis and Applications, vol. Ume, “Some existence theorems generalizing

She reviews the status of a number of interrelated problems on diameters of graphs, including: (i) degree/diameter problem, (ii) order/degree problem, (iii) given n, D, D 0 ,

pole placement, condition number, perturbation theory, Jordan form, explicit formulas, Cauchy matrix, Vandermonde matrix, stabilization, feedback gain, distance to

– proper &amp; smooth base change ← not the “point” of the proof – each commutative diagram → Ð ÐÐÐ... In some sense, the “point” of the proof was to establish the

Gupta, “Solvability of a three-point nonlinear boundary value problem for a second order ordinary differential equation,” Journal of Mathematical Analysis and Applications,

Zhao, “The upper and lower solution method for nonlinear third-order three-point boundary value problem,” Electronic Journal of Qualitative Theory of Diff erential Equations, vol.

John Baez, University of California, Riverside: [email protected] Michael Barr, McGill University: [email protected] Lawrence Breen, Universit´ e de Paris

It is known that if the Dirichlet problem for the Laplace equation is considered in a 2D domain bounded by sufficiently smooth closed curves, and if the function specified in the