|
来源
Coalitional Game Theory for Communication Networks
前置知识
由于详细解释需要一些博弈论的知识，如TU、core等，所以这里只作初解，大致解释下什么叫做Nucleolus方法。 这里我们讨论的是TU canonical games，不理解也没关系，当成最普通的博弈情景就行了。
理解
Nucleolus，本质就是最小化合作博弈中联盟（coalition）的最大不满意程度的一种分配方法。本质是min-max。
概念
合作博弈：字面上理解。联盟 coalition：一次博弈中组队的几个人，构成一个coalition，常用
S
S
S表示。归因 imputation：对博弈中所有人的一种分配方式，常用
x
x
x表示，是一个vector，其中
x
j
x_j
xj代表对第j个人分配的数值。联盟值：评价联盟
S
S
S的价值（worth），也有时候被称为特征函数，常用
v
(
S
)
v(S)
v(S)表示。在本文讨论的情况下v是一个实数值。超出 excess（翻译的可能不准）：一个联盟对某一个分配的不满意程度。
e
(
x
,
S
)
=
v
(
S
)
−
∑
j
∈
S
x
j
e(x,S)=v(S)-\sum_{j \in S} x_j
e(x,S)=v(S)−∑j∈Sxj，即联盟S的价值与联盟中所有人分配的值的差值。可以看出，excess越小，不满意程度越低；若一次博弈中所有S的excess都是0或负值，则这样的x是存在于core中的。（最后一句话可以不用理解）
O
(
x
)
O(x)
O(x)：一次博弈中所有excess所构成的vector，以非增的顺序排列。
≺
l
e
x
\prec_{lex}
≺lex 顺序小于 lexographically less：定义的一种符号。若
y
≺
l
e
x
z
y\prec_{lex} z
y≺lexz，其中yz都是k维向量，则存在
l
∈
{
1
,
.
.
.
,
k
}
l \in \{1,...,k\}
l∈{1,...,k}，使得
y
1
=
z
1
,
.
.
.
y
l
−
1
=
z
l
−
1
,
y
l
<
z
l
y_1=z_1,...y_{l-1}=z_{l-1},y_l |