I wrote a small program in MATLAB to compute the Shapley value using the multi-linear extension of a TU game. However, I run into trouble with the Symbolic Math Toolbox of MATLAB. In the program I have to integrate a set of functions to get the Shapley value. However, inside a MATLAB program I cannot use the int() command
Error using sym/subsindex (line 663) Ivalid indexing or function definition. When defining a function, ensure that the body of the function is a SYM object. When indexing, the input must be numeric, logical or ':'.
Error in ShapleyValueML (line 65)shv(jj)=int(dfy,0,1)
as a consequence I have to use integral() instead. In this case, I need to transcribe the set of expressions into MATLAB function handle with matlabFunction(). However, on all Linux machines (MATLAB R2014a) on which I have access this command does not work (see the discussion below). As a workaround, the MATLAB program returns the set of functions into the current workspace, there the Shapley value can be computed using the int() command.
To make the discussion more concrete, let us consider this small MATLAB program first.
function [shv,F,dfm]=ShapleyValueML(v)
N=length(v);
[~, n]=log2(N);
S=1:N;
int=0:-1:1-n;
mat=(rem(floor(S(:)*pow2(int)),2)==1);
cmat=(rem(floor(S(:)*pow2(int)),2)==0);
x=sym('x',[1 n]);
mx=1-x;
y = sym('y');
vy=ones(1,n)*y;
F=0;
shv=zeros(1,n);
dfm=cell(1,n);
for ss=1:N
pd1=x(mat(ss,:));
pd2=mx(cmat(ss,:));
pd=prod(pd1)*prod(pd2)*v(ss);
F=pd+F;
end
F=expand(F);
for jj=1:n
dF=diff(F,x(jj));
dfy=subs(dF,x,vy);
%% Does not work!! MATLAB bug???
% mf=matlabFunction(dfy);
% shv(jj)=integral(mf,0,1);
%%
%% The best would be to use:
%%
% shv(jj)=int(dfy,0,1)
%% but it cannot be used inside a program.
dfm{jj}=dfy;
end
end
The commented parts are the parts that do not work inside the program, but are needed to compute the Shapley value with that program, which is its purpose. I tested this program up to 12 players, and I was able to successfully calculate the Shapley value by a two step procedure. Hence, the above program specifies correctly the considered problem. To get a better understanding of this two step procedure and of the functionality of the above program, let us focus on a three person game. The values of the coalitions are given by the following data array
>> v = [0,0,90,0,100,120,220];
Notice that coalitions are ordered in accordance with their unique integer representations. The game is defined, we can now evaluate the multi-linear extension and the set of partial derivatives with the above program, but not the Shapley value.
>> [shv,F,dfm]=ShapleyValueML(v);
Integration of the set of partial derivatives runs over the diagonal of the unit-cube, but then we can set the variables from [x1,x2,x3] to [y,y,y], and integration runs from 0 to 1.
>> for k=1:3, shv(k)=int(dfm{k},0,1);end;
The solution of the integration is the Shapley value given by:
>> shv
shv =
65 75 80
Checking that this is indeed the Shapley value can be accomplished with a potential function approach implemented in
>> sh_v=ShapleyValue(v)
sh_v =
65 75 80
that ships with my MATLAB Game Theory Toolbox MatTuGames from
http://www.mathworks.com/matlabcentral/fileexchange/35933-mattugames
Instead of integrating with int() one can also use integral(), but then the contents like
>> dfm{1}
ans =
- 90*y^2 + 190*y
must be rewritten with matlabFunction() into a function handle. As I have mentioned above this does not work under Linux (MATLAB R2013a,R2013b,R2014a). To see this let us try to reproduce the example
>> syms x y
>> r = sqrt(x^2 + y^2);
from the documentation at the URL:
This should give
ht =
@(x,y)tanh(sqrt(x.^2+y.^2))
but I get
>> ht = matlabFunction(tanh(r))
Cell contents reference from a non-cell array object.
Error in vectorize (line 15)
c = cells{i};
Error in sym/matlabFunction>mup2mat (line 319)
res = vectorize(res(2:end-1)); % remove quotes
Error in sym/matlabFunction>mup2matcell (line 304)
r = mup2mat(c{1});
Error in sym/matlabFunction (line 123)
body = mup2matcell(funs);
Here comes now my question: Exists there an alternative procedure to get from
>> dfm{1}
ans =
- 90*y^2 + 190*y
a function handle
>> df=@(y) (- 90.*y.^2 + 190.*y)
df =
@(y)(-90.*y.^2+190.*y)
to integrate it by
>> integral(df,0,1)
ans =
65
Or to put it differently. Is there an alternative method available to change multiplication * to element-wise multiplication .*, and the power operation ^ to element-wise power.^?
Of course, any suggestions of improvement for the above MATLAB program are highly appreciated.
I think I know what the problem is; Towards the beginning of ShapleyValueML function, you have a variable named int which shadows the builtin integration function:
...
int=0:-1:1-n; %# <-- problem!
...
shv(jj)=int(dfy,0,1)
...
That explains the error coming from sym/subsindex, you were using a symbolic object as an index into the numeric array int.
Change the variable name to something else, and the commented code runs fine (the symbolic integration)! Simple as that :)