Distance from the core of a characteristic function game (between a point and an n-dimensional closed convex polyhedron)

Question

In transferable utility characteristic function games (cooperative game theory), the most famous solution concept is the core of the game defined as the set of feasible payoff allocations that cannot be improved upon by any coalition. Geometrically the core is a closed convex polyhedron: http://www.jstor.org/stable/2630190

In these game a payoff allocation is either in the core or not. The TUGlab set of tools has a command that can compute whether or not a payoff allocation is in the core or not: http://webs.uvigo.es/mmiras/TUGlab/ But there is no command that would tell you what the exact distance of a certain payoff allocation is to the core. If there is a geometric characterization of the core as a closed convex polyhedron, then there should be a way to calculate the geometric distance between a point and that polyhedron as "distance from the core" of characteristic function. Unfortunately I have found no paper that actually shows me the formula or algorithm for computing this distance that I could implement in MATLAB.

My guess is that there may be a clue in the code by Stephen Cameron that calculates distance between two polyhedrons. But my problem should be simpler than that: just the distance between a point and a polyhedron. In the end, I need a MATLAB program that takes as input a) a characteristic function, and b) a payoff distribution, and then gives as output the distance between the payoff distribution and the core of the characteristic function. Assuming of course that the core is nonempty.

Answer 1

Complicated though the core concept may be, a geometrical translation can simplify it by an order of magnitude!

Knowing the core description as a system of inequalities, you can numerically minimize the Euclidean distance of a given point to the surface of the N-D convex polyhedron.

Assuming that the core is characterized by the system of inequalities and equalities as:

A.x <= b  

and

Aeq.x = beq

(this part may not exist in all descriptions)

one can simply minimize the distance |Cp-Gp| where Gp is the coordinates of a given point and Cp is the point closest to Gp that satisfies the above constraints describing the core.

A simple numerical solution is using the lsqlin function already available in MATLAB. A single line of code would give you the distance, D and the position of the closest point on the convex, Cp as:

[Cp,D,residual,exitflag,output,lambda] = lsqlin(speye(N),GP,A,b,Aeq,beq);

Moreover, if the returned argument residual is negative one can conclude that Gp is contained within the core.

Answer 2

Although I don't understand why you are interested in the distance of a point outside of the core to the core itself, I shall give you a quick procedure of how to get an approximation. The example below can be reproduced with my Matlab Game Theory Toolbox MatTuGames, which can be downloaded at the following URL:

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

To start with, consider the following five person game:

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

The Shapley value is quickly calculated through

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

Elapsed time is 0.002676 seconds.

>> sh_v 

sh_v =

1.7500    1.9167    1.1667    1.5000    1.6667

In the next step, we check whether the core exists or not

>> CddCoreQ(v)

ans =

 1

Since, the return value is one (true), the core exists for the example game. Furthermore, we also check on convexity, average-convexity and super-additivity

>> convex_gameQ(v)

ans =

 0

>> average_convexQ(v)

ans =

 0

>> super_additiveQ(v)

ans =

 0

None of these properties is satisfied. Next, we verify if the Shapley value belongs to the core.

>> crQ=belongToCoreQ(v,sh_v)

crQ =

 0

This is not the case. Thus, we use the Shapley value to compute an approximated distance to the core. To complete, we compute the vertices of the core, this can be accomplished by

>> tic;crv=CddCoreVertices(v);toc                      

Elapsed time is 0.001161 seconds.

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

Now, we can compute the Euclidean distance of the Shapley value to the core vertices. Hence, we evaluate

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

Single out the smallest distance value and its position is done through

>> [mn,id]=min(ed)


mn =

1.3385


id =

 1

We observe that the first core vertex in the above list has smallest distance to Shapley value. You might get a better approximation, if you choose that face with vertex

>> crv(id,:)

ans =

 2     2     0     2     2

that is closest to the Shapley value. Then compute the center of the face, which might give you a better approximation.

Update:

Based on the answer by Mehdi Pouragha, that gives the correct approach to use an orthogonal projection from a point outside of the core to the core itself. I present a small Matlab function to calculate the closest point of the core to an arbitrary point outside of the core.

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

Now, we can compute the closest point of the core to the Shapley value from the above five person game by

>> DC=CPCore(v,sh_v)

The result is

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]

Correctness can be checked out by

>> tol=10^7*eps;
>> belongToCoreQ(v,DC.Cp,tol)

ans =

 1