0

譲渡可能効用特性関数ゲーム (協力ゲーム理論) で最も有名な解の概念は、どの連合によっても改善できない実行可能なペイオフ配分のセットとして定義されるゲームのコアです。幾何学的には、コアは閉じた凸多面体です: http://www.jstor.org/stable/2630190

これらのゲームでは、ペイオフの割り当てはコアにあるか、コアにないかのいずれかです。TUGlab の一連のツールには、ペイオフの割り当てがコアにあるかどうかを計算できるコマンドが あります: http://webs.uvigo.es/mmiras/TUGlab/特定のペイオフ配分の距離はコアまでです。閉じた凸多面体としてコアの幾何学的特徴付けがある場合、点とその多面体の間の幾何学的距離を特性関数の「コアからの距離」として計算する方法があるはずです。残念ながら、MATLAB で実装できるこの距離を計算するための式またはアルゴリズムを実際に示している論文は見つかりませんでした。

私の推測では、2 つの多面体間の距離を計算する Stephen Cameron のコードに手がかりがあるかもしれません。しかし、私の問題はそれよりも単純なはずです。点と多面体の間の距離だけです。最後に、a) 特性関数、b) ペイオフ分布を入力として取り、ペイオフ分布と特性関数のコアとの間の距離を出力として与える MATLAB プログラムが必要です。もちろん、コアが空でないと仮定します。

4

2 に答える 2

0

コアの外側のポイントからコア自体までの距離に関心がある理由がわかりませんが、近似値を取得する方法の簡単な手順を説明します。以下の例は、次の URL からダウンロードできる Matlab Game Theory Toolbox MatTuGames で再現できます。

http://www.mathworks.com/matlabcentral/fileexchange/35933-mattugames

まず、次の 5 人用ゲームを考えてみましょう。

>> 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];

Shapley 値は、

>> tic;sh_v=ShapleyValue(v);toc

経過時間は 0.002676 秒です。

>> sh_v

sh_v =

1.7500    1.9167    1.1667    1.5000    1.6667

次のステップでは、コアが存在するかどうかを確認します

>> CddCoreQ(v)

ans =

 1

戻り値は 1 (true) であるため、サンプル ゲームのコアは存在します。さらに、凸性、平均凸性、超加法性もチェックします

>> convex_gameQ(v)

ans =

 0

>> average_convexQ(v)

ans =

 0

>> super_additiveQ(v)

ans =

 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)

ans =

 9     5

これで、コア頂点までの Shapley 値のユークリッド距離を計算できます。したがって、私たちは評価します

>> for k=1:size(crv), ed(k,:)=norm(sh_v-crv(k,:));  end

>> 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,:)

ans =

 2     2     0     2     2

これは Shapley 値に最も近い値です。次に、顔の中心を計算します。これにより、より適切な近似が得られる場合があります。

アップデート：

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);

ここで、上記の 5 人ゲームからコアの 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
于 2014-06-28T16:34:21.583 に答える