在可转移效用特征函数博弈(合作博弈论(中,最著名的解概念是博弈的核心,定义为任何联盟都无法改进的可行收益分配的集合。从几何上讲,核心是一个闭合凸多面体:http://www.jstor.org/stable/2630190
在这些游戏中,收益分配要么在核心,要么不在核心。TUGlab工具集有一个命令,可以计算收益分配是否在核心中:http://webs.uvigo.es/mmiras/TUGlab/但是没有命令可以告诉你某个收益分配到核心的确切距离。如果存在将核心的几何表征为闭合凸多面体,那么应该有一种方法可以将点和该多面体之间的几何距离计算为特征函数的"与核心的距离"。不幸的是,我没有找到任何论文真正向我展示我可以在 MATLAB 中实现的计算这个距离的公式或算法。
我的猜测是,斯蒂芬·卡梅隆的代码中可能有一条线索,可以计算两个多面体之间的距离。但我的问题应该比这更简单:只是一个点和一个多面体之间的距离。最后,我需要一个 MATLAB 程序,它将 a( 特征函数和 b( 收益分布作为输入,然后给出收益分布和特征函数核心之间的距离作为输出。当然,假设核心是非空的。
尽管核心概念可能很复杂,但几何平移可以将其简化一个数量级!
知道核心描述为不等式系统,您可以在数值上最小化给定点到 N-D 凸多面体表面的欧几里得距离。
假设核心的特点是不平等和平等系统为:
A.x <= b
和
Aeq.x = beq
(这部分可能并不存在于所有描述中(
可以简单地最小化距离|Cp-Gp|
其中Gp
是给定点的坐标,Cp
是最接近 Gp 的点,满足上述描述核心的约束。
一个简单的数值解决方案是使用 MATLAB 中已有的lsqlin
函数。一行代码将为您提供凸面上最近点的距离、D
和位置,Cp
如下:
[Cp,D,residual,exitflag,output,lambda] = lsqlin(speye(N),GP,A,b,Aeq,beq);
此外,如果返回的参数residual
为负数,则可以得出结论,Gp
包含在核心中。
虽然我不明白你为什么对一个点的距离感兴趣从核心到核心本身,我将给你一个快速的过程,告诉你如何得到一个近似值。下面的例子可以用我的 Matlab 重现博弈论工具箱MatTuGames,可以在以下网址下载:
http://www.mathworks.com/matlabcentral/fileexchange/35933-mattugames
首先,考虑以下五人游戏:
>> v=[2 0 1 0 0 0 4 2 0 0 1 0 0 0 2 0 0 0 1 0 0 2 4 1 1 1 4 1 2 4 8];
沙普利值通过快速计算
>> tic;sh_v=ShapleyValue(v);toc
运行时间为 0.002676 秒。
>> sh_v
sh_v =
1.7500 1.9167 1.1667 1.5000 1.6667
在下一步中,我们检查核心是否存在
>> CddCoreQ(v)
答 =
1
由于返回值为 1 (true(,因此示例游戏存在核心。此外,我们还检查凸性、平均凸性和超相加性
>> convex_gameQ(v)
答 =
0
>> average_convexQ(v)
答 =
0
>> super_additiveQ(v)
答 =
0
这些属性都不满足。接下来,我们验证 Shapley 值是否属于到核心。
>> crQ=belongToCoreQ(v,sh_v)
crQ =
0
事实并非如此。因此,我们使用Shapley值来计算近似距离核心。最后,我们计算核心的顶点,这可以通过
>> tic;crv=CddCoreVertices(v);toc
运行时间为 0.001161 秒。
>> crv
CRV =
2 2 0 2 2
4 2 0 2 0
2 4 0 2 0
2 2 0 4 0
2 0 2 4 0
4 0 2 2 0
2 0 2 2 2
2 0 4 2 0
4 0 0 2 2
>> size(crv)
答 =
9 5
现在,我们可以计算 Shapley 值到核心顶点的欧氏距离。因此,我们评估
>> for k=1:size(crv), ed(k,:)=norm(sh_v-crv(k,:)); end
>> ed
ed =
1.3385
3.0754
2.9651
3.2339
3.6686
3.5296
2.1890
3.8460
3.2339
挑出最小的距离值,其位置通过
>> [mn,id]=min(ed)
mn =
1.3385
id =
1
我们观察到,上面列表中的第一个核心顶点与Shapley值的距离最小。如果你选择那个有顶点的面,你可能会得到更好的近似值
>> crv(id,:)
答 =
2 2 0 2 2
最接近沙普利值。然后计算面部的中心,这可能会给你一个更好的近似值。
更新:
根据Mehdi Pouragha的回答,这给出了使用从核心外部到核心本身的正交投影的正确方法。我提出了一个小的 Matlab 函数来计算核心到核心外任意点的最近点。
function DC=CPCore(v,x,tol)
% CPCORE computes the closest point of the core to x.
%
%
% Usage: DC=CPCore(v,x,tol)
% Define variables:
% output:
% Cp -- Closest point of the core to x.
% D -- The Euclidean distance between the points.
% resid -- The residual.
% ef -- Exitflag.
% lambda -- Containing the Lagrange multipliers.
%
% input:
% v -- A Tu-Game v of length 2^n-1.
% x -- The reference point from which the distance
% to core should be drawn.
% tol -- Tolerance value. Its default value is set to 10^6*eps.
if nargin<3
tol=10^6*eps;
end
N=length(v);
[~, n]=log2(N);
S=1:N;
for k=1:n, A(:,k) = bitget(S,k)==1;end
v1(S)=v(S)-tol;
v1(N)=v(N);
A=-A;
B=-v1;
Aeq=ones(1,n);
beq=v(N);
[Cp,D,residual,exitflag,~,lambda] = lsqlin(eye(n),x,A,B,Aeq,beq);
Cp=Cp';
resid=residual';
DC=struct('Cp',Cp,'D',D,'resid',resid,'ef',exitflag,'lambda',lambda);
现在,我们可以从上述五人游戏中计算出核心最接近 Shapley 值的点
:>> DC=CPCore(v,sh_v)
结果是
DC =
Cp: [2.0000 1.6667 0.9167 2.0000 1.4167]
D: 0.5000
resid: [0.2500 -0.2500 -0.2500 0.5000 -0.2500]
ef: 1
lambda: [1x1 struct]
正确性可以通过以下方式检查
>> tol=10^7*eps;
>> belongToCoreQ(v,DC.Cp,tol)
ans =
1