(* :Title: ParaTuGames.m
    : Release Date : 03.12.2014      
    : Preliminary version:
      For testing only.
*)
(* :Context: ParaTuGames` *)

(* :Summary:	
    This package provides some extensions to the package TuGame for 
    modeling and calculating solutions and properties for cooperative games with 
    transferable utilities in parallel. 
*)			

(* :Author:		
    Holger Ingmar Meinhardt
    Department of Economics
    University of Karlsruhe (KIT)
    holger.meinhardt@wiwi.uni-karlsruhe.de
*)

(* :Package Version: 0.1 *)

(* 
   :Mathematica Version: 8.x, 9.x, 10.x

*)
(*:Keywords:
   Dual Game, Superadditive Game, Convex Game, Strong Convex Game, Average-Convex Game,
   Kernel, balancing Maximum Excesses.
*)

(* :Sources:
   
   Theo Driessen, Cooperative Games, Solutions and Applications, Kluwer Academic
   Publishers, Dordrecht, 1988.

   E. Inarra and J. Usategui, The Shapley value and average convex games, 
   IJGT, 22, 13-29, 1993.

   M. Maschler, The Bargaining Set, Kernel and Nucleolus, Handbook of Game
   Theory, Chapter 18, 591-647, 1992.

   M. Maschler, B. Peleg and L.S. Shapley, Geometric Properties of Kernel,  
   Nucleolus and related Concepts, in Mathematics of Operations Research, 
   Vol4 Nov. 1979, p. 303-338.

   J-E. Martinez-Legaz, Dual Representation of Cooperative Games based on 
   Fenchel-Moreau Conjugation, Optimization, pp. 291-319, Vol. 36, 1996.

   H. I. Meinhardt, An LP approach to compute the pre-kernel for cooperative games, 
   Computers and Operation Research, Vol 33/2 pp. 535-557,2006.

   H. I. Meinhardt, The Pre-Kernel as a Tractable Solution for Cooperative Games:
   An Exercise in Algorithmic Game Theory, forthcoming in: Theory and Decision Library C,
   Springer Publisher, Heidelberg. pp. 1-247, 2013.  

   A. Meseguer-Artola, Using the Indirect Function to characterize the Kernel of a TU-Game,
   Departament d'Economia i d'Historia Economica, 1997. 
   
   R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970.

   R.E. Stearns, Convergent Transfer Schemes for N-Person Games,
   Transaction American Mathematical Society, 449-459, 1968.

   Hal Varian (Ed.). Economics and Financial Modeling with Mathematica, 
   Springer, 1992. 
*)


(* 
   :History:
*)

Needs["coop`CooperativeGames`"];
Needs["TuGames`"];
Needs["TuGamesAux`"];

Which[$OperatingSystem === "MacOSX", Needs["VertexEnum`"],
      $OperatingSystem === "Windows", Needs["vertex`VertexEnum`"],
      True, Needs["VertexEnum`"]
]

ParaAntiPreKernel::usage = 
"ParaAntiPreKernel[game,payoff,options] computes an anti-pre-kernel solution by relying on
 the anti of Algorithm 7.2.1 of Meinhardt (2013)."

ParaAntiPreKernelQ::usage = 
"AntiPreKernelQ[game,payoff] checks whether the vector 'payoff' is an element of the anti-pre-kernel. 
 AntiPreKernelQ checks also the efficiency condition in contrast to the function MinExcessBalanced.";

ParaAntiPreKernelQ::usage = 
"ParaAntiPreKernelQ[game,payoff] checks whether the vector 'payoff' is an element of the anti-pre-kernel. 
 ParaAntiPreKernelQ checks also the efficiency condition in contrast to the function MinExcessBalanced.";

ParaAvConvexQ::usage = 
"ParaAvConvexQ[game] checks the average-convexity of the game.
 It returns 'True' or 'False'. Calling the function with the option will return
 the sum of the marginal contributions for each coalition S w.r.t. to each 
 superset S union {j}. These values must be non-negative.";

ParaConvexQ::usage = 
"ParaConvexQ[game] checks if the Tu-game is convex. It returns the value 'True' or 'False'.";

ParaSuperAdditiveQ::usage = 
"ParaSuperAdditiveQ[game] checks if a game is superadditive.";

ParaPreKernel::usage =
"ParaPreKernel[game,payoff,options] computes a pre-kernel element by iteratively solving
 a system of linear equations in parallel mode. (cf. Algorithm 8.2.1 of Meinhardt (2013))"

ParaPreKernelQ::usage = 
"ParaPreKernelQ[game,payoff] checks whether the (pre-)imputation 'payoff' is an element of the pre-kernel. 
 ParaPreKernelQ checks also the efficiency condition in contrast to the function MaxExcessBalanced.";


ParaPreKernelElement::usage =
"ParaPreKernelElement[game,payoff,options] computes a pre-kernel element by iteratively 
 determining a direction of improvement in parallel mode. The iteration process stops whenever the 
 direction of improvement is equal to the null vector. (cf. Algorithm 8.3.1 of Meinhardt (2013))."

ParaBestCoalitions::usage = 
"ParaBestCoalitions[game,payoff] computes the set of most effective coalitions that supports the claim of 
 player i against j, for all possible pair of players in parallel mode."


ParaSetsToVec::usage =
"ParaSetsToVec[bestcoal,T,options] converts the set of most effective coalitions to a set of vectors 
 of length T in parallel mode. A vector reflects how the best arguments are distributed between a
 bargaining pair (i,j) at a proposal. A plus sign indicates that the arguments are skewed in favor
 of the player i, zero means that the arguments are balanced, and a minus sign indicates that the
 arguments are skewed in favor of the player j. See also Meinhardt (2013)."

ParaOptStepSize::usage =  
"ParaOptStepSize[game, payoff, options] computes the optimal step size in order to decrease  the excess 
 value of the function ValueExcess[] in parallel mode. A direction of improvement 'doi' can be
 determined by the function DirectionOfImprovement[]. Then a new payoff vector can be constructed by 
 newpay = payoff + Optstep * doi. Use this vector to value the excesses by ValueExcess[game, newpay]. 
 This value should be smaller than ValueExcess[game,payoff]. "      

ParaDirectionOfImprovement::usage = 
"ParaDirectionOfImprovement[game, payoff, options] determines a vector of improvement in order reduce 
 the maximum surpluses in parallel mode."

ParaMaxSurplus::usage = 
"ParaMaxSurplus[game,pi,pj,payoff] calculates the maximum surplus of player i over j with respect to the 
 imputation 'payoff' in parallel mode. Note that the efficiency condition will not be checked."

ParaGameBasis::usage = 
"ParaGameBasis[T] computes the basis of a |T|-person game in parallel. "

ParaCharacteristicValues::usage
"ParaCharacteristicValues[unancrd_List,T,opts] computes the coalitional values from the vector of 
 unanimity coordinates in parallel."


Options[ParaAntiPreKernel] = Sort[Options[PreKernel]];
(* Options[ParaAvConvexQ] = Options[AverageConvexQ]; *)
Options[ParaBestCoalitions] = Sort[Options[BestCoalitions]]; 
Options[ParaSetsToVec] = Sort[Options[SetsToVec]]; 
Options[ParaOptStepSize] = Sort[Options[OptStepSize]];
Options[ParaPreKernelElement] = Sort[Options[PreKernelElement]];
Options[ParaDirectionOfImprovement] = Sort[Options[DirectionOfImprovement]];
Options[ParaPreKernel] = Sort[Options[PreKernel]];
Options[ParaExcessPayoff] = Sort[Options[ExcessPayoff]];

DistributeDefinitions[Options[ParaPreKernel] = Sort[Options[PreKernel]]];
(* DistributeDefinitions[Options[ParaAvConvexQ] = Options[AverageConvexQ]]; *)
DistributeDefinitions[Options[ParaBestCoalitions] = Sort[Options[BestCoalitions]]];
DistributeDefinitions[Options[ParaOptStepSize] = Sort[Options[OptStepSize]]];
DistributeDefinitions[Options[ParaPreKernelElement] = Sort[Options[PreKernelElement]]];
DistributeDefinitions[Options[ParaDirectionOfImprovement] = Sort[Options[DirectionOfImprovement]]];
DistributeDefinitions[Options[ParaPreKernel] = Sort[Options[PreKernel]]];
DistributeDefinitions[Options[ParaExcessPayoff] = Sort[Options[ExcessPayoff]]];


(* SetSharedFunction[ParaSelCoal] *)
SetSharedFunction[ParaMaxSurplus]
SetSharedFunction[ParaAntiSurplus]    
SetSharedFunction[ParaTIJsets]
SetSharedFunction[ParaW]
(*
SetSharedFunction[ParaOberMenge,ParaSumMargContribution]
*)


(* Based on Algorithm 8.2.1 of Meinhardt (2013) *)
(* User interface to compute a pre-kernel element. *)

ParaPreKernel[game_,opts:OptionsPattern[ParaPreKernel]] := 
  Block[{pay},
  pay = Table[v[T],{Length[T]}]/Length[T];
  ParaPreKernel[game,pay,opts]
 ]


ParaPreKernel[game_, payoff_List, opts:OptionsPattern[ParaPreKernel]] := Block[{dimpay,rclim}, 
      dimpay = Dimensions[payoff]; 
      rclim=If[Length[T] > 11,256,156];
      Which[Length[dimpay]===2, 
                       Which[(Last[dimpay]===Length[T] && Depth[payoff] ===3), Block[{$RecursionLimit = rclim}, ParaPreKernelAlg2[game,#, opts]&/@ payoff //Union],
                                     True, ParaPrintRemark[payoff]],
                    Length[dimpay]===1, 
                        Which[(First[dimpay]===Length[T] && Depth[payoff] === 2 ), Block[{$RecursionLimit = rclim},ParaPreKernelAlg2[game, payoff,  opts]], 
                                     True, ParaPrintRemark[payoff]],
                    True, ParaPrintRemark[payoff]
                                   ]
      ]

(* Main Functions *)
ParaPreKernelAlg2[game_, payoff_List, opts:OptionsPattern[ParaPreKernel]] := 
Block[{sil, smc, meff, matE, vlis, alpv},
  sil = OptionValue[Silent];
  smc = OptionValue[SmallestCardinality];
  meff = ParaBestCoalitions[game, payoff, MaximumSurpluses -> False, SmallestCardinality -> smc];
  matE = -ParaSetsToVec[meff, T, EffVector -> True];
  vlis = ParallelMap[MapThread[v[#1] &, {#}] &, meff, Method -> "CoarsestGrained",DistributedContexts -> None];
  alpv = ParallelMap[ReplaceAll[#, List -> Subtract] &, vlis, Method -> "CoarsestGrained",DistributedContexts -> None];
  PrependTo[alpv,v[T]];
  err=Norm[matE.payoff+alpv]^2;
  If[LessEqual[err,1.5*10^(-12)],Return[payoff],     
               xvec=-PseudoInverse[matE].alpv;
               ParaPreKernelAlg2[game,xvec,opts]]   
  ]


(* Based on Algorithm 8.3.1 of Meinhardt (2013) *)
(* User interface to compute a pre-kernel element. *)

ParaPreKernelElement[game_,opts:OptionsPattern[ParaPreKernelElement]] := 
  Block[{pay},
  pay = Table[v[T],{Length[T]}]/Length[T];
  ParaPreKernelElement[game,pay,opts]
 ]

ParaPreKernelElement[game_, payoff_List, opts:OptionsPattern[ParaPreKernelElement]] := Block[{dimpay,rclim}, 
      dimpay = Dimensions[payoff]; 
      rclim=If[Length[T] > 11,256,156];
      Which[Length[dimpay]===2, 
                       Which[(Last[dimpay]===Length[T] && Depth[payoff] ===3), Block[{$RecursionLimit = rclim}, ParaPreKernelAlg3[game,#, opts]&/@ payoff //Union],
                                     True, ParaPrintRemark[payoff]],
                    Length[dimpay]===1, 
                        Which[(First[dimpay]===Length[T] && Depth[payoff] === 2 ), Block[{$RecursionLimit = rclim},ParaPreKernelAlg3[game, payoff,  opts]], 
                                     True, ParaPrintRemark[payoff]],
                    True, ParaPrintRemark[payoff]
                                   ]
      ]

(* Main Functions *)

ParaPreKernelAlg3[game_, payoff_List, opts:OptionsPattern[ParaPreKernelElement]] := 
Block[{sil, smc, optst, doi, optstep, itpay,tol,brc,pinv},
     sil = OptionValue[Silent];
     smc = OptionValue[SmallestCardinality];     
     optst = OptionValue[CalcStepSize];
     pinv = OptionValue[PseudoInv];
    {optstep, doi} = ParaDirectionOfImprovement[game, payoff, MaximumSurpluses -> True, CalcStepSize -> optst, PseudoInv->pinv,Silent -> sil, SmallestCardinality -> smc]; 
    If[sil ===False, Print["doi=", doi], True];
    If[sil ===False, Print["optstep=", optstep], True];
    itpay =  payoff + optstep*doi;
    If[sil===False, Print["itpay=", itpay], True];
    If[Depth[itpay]!=2,Return[payoff],True];
    tol=Table[1.5*10^(-12),{Length[T]}];
    brc=Apply[And,MapThread[LessEqual[#1,#2] &,{Abs[doi],tol}]];
    If[SameQ[brc,True], itpay, ParaPreKernelAlg3[game, itpay, CalcStepSize -> optst, Silent -> sil, SmallestCardinality -> smc]] 
]


ParaDirectionOfImprovement[game_, payoff_List, opts:OptionsPattern[ParaDirectionOfImprovement]] := 
Block[{sil, smc, optst, meff, matE, matQ, matP, varpay, mex, submex, setpay, grmex, doi, optstep,pinv},
  sil = OptionValue[Silent];
  smc = OptionValue[SmallestCardinality];
  optst = OptionValue[CalcStepSize];
  pinv = OptionValue[PseudoInv];
  {meff, mex} = ParaBestCoalitions[game, payoff, MaximumSurpluses -> True, SmallestCardinality -> smc]; 
  matE = -ParaSetsToVec[meff, T, EffVector -> True];
  submex = ParallelMap[{1, -1}.# &, mex];    
  varpay = x[#] & /@ T;
  setpay = MapThread[Rule, {varpay, payoff}];
  grmex = v[T] - Apply[Plus, x[#] & /@ T] /. setpay;
  PrependTo[submex, grmex];
  If[SameQ[sil,False], Print["submex=", submex],True];
  If[SameQ[pinv,False],
     doi = LeastSquares[matE,-submex,Tolerance -> 10^(-10)];,
     doi = -PseudoInverse[matE].submex];
  optstep = If[SameQ[optst,True], ParaDelStar[doi, matE, submex], 1];
  {optstep,doi}
  ]

ParaDelStar[doi_List, matE_List, smex_List]:= 
  Block[{edvec,nrsq,tol},
  edvec = matE.doi; 
  nrsq =Norm[edvec]^2;
  tol=1.5*10^(-12);
  If[LessEqual[Abs[nrsq],tol], 0, - smex.edvec/nrsq]
]

(* Computing the anti pre-kernel *)

ParaAntiPreKernel[game_,opts:OptionsPattern[ParaPreKernel]] := 
  Block[{pay},
  pay = ParallelTable[v[T],{Length[T]}]/Length[T];
  ParaAntiPreKernel[game,pay,opts]
 ]


ParaAntiPreKernel[game_, payoff_List, opts:OptionsPattern[ParaPreKernel]] := Block[{dimpay,rclim}, 
      dimpay = Dimensions[payoff]; 
      rclim=If[Length[T] > 11,256,156];
      Which[Length[dimpay]===2, 
                       Which[(Last[dimpay]===Length[T] && Depth[payoff] ===3), Block[{$RecursionLimit = rclim}, ParaAntiPreKernelAlg2[game,#, opts]&/@ payoff //Union],
                                     True, ParaPrintRemark[payoff]],
                    Length[dimpay]===1, 
                        Which[(First[dimpay]===Length[T] && Depth[payoff] === 2 ), Block[{$RecursionLimit = rclim},ParaAntiPreKernelAlg2[game, payoff,  opts]], 
                                     True, ParaPrintRemark[payoff]],
                    True, ParaPrintRemark[payoff]
                                   ]
      ]


ParaAntiPreKernelAlg2[game_, payoff_List, opts:OptionsPattern[ParaPreKernel]] := 
Block[{sil, smc, meff, matE, vlis, alpv},
  sil = OptionValue[Silent];
  smc = OptionValue[SmallestCardinality];
  meff = ParaBestCoalitions[game, payoff, AntiPreKernel -> True, MaximumSurpluses -> False, SmallestCardinality -> smc];
  matE = -ParaSetsToVec[meff, T, EffVector -> True];
  Parallelize[vlis = MapThread[v[#1] &, {#}] &/@ meff;
              alpv = ReplaceAll[#, List -> Subtract] & /@ vlis, Method -> "CoarsestGrained",DistributedContexts -> None];
  PrependTo[alpv,v[T]];
  err=Norm[matE.payoff+alpv]^2;
  If[LessEqual[err,1.5*10^(-12)],Return[payoff],     
               xvec=-PseudoInverse[matE].alpv;
               ParaAntiPreKernelAlg2[game,xvec,opts]]   
  ]

(* Selecting the set of lexicographically smallest coalitions. *) 

ParaBestCoalitions[game_,payoff_List,opts:OptionsPattern[ParaBestCoalitions]]:= 
  Block[{dimpay}, 
       dimpay = Dimensions[payoff]; 
      Which[Length[dimpay]===2, 
                        Which[(Last[dimpay]===Length[T] && Depth[payoff] ===3), Map[ParaBestcoalij01[game,#,opts]&, payoff],
                                     True, ParaWrongDimension],
                    Length[dimpay]===1, 
                        Which[(First[dimpay]===Length[T] && Depth[payoff] === 2 ),ParaBestcoalij01[game,payoff,opts], 
                                     True, ParaWrongDimension],
                    True, ParaWrongDimension
                                   ]
]

paralistIJ[T_List]:=Flatten[ParallelTable[Table[{i, j}, {j, i + 1, Length[T]}], {i, 1, Length[T]}]]

ParaBestcoalij01[game_, payoff_List,opts:OptionsPattern[ParaBestCoalitions]] :=  
  Block[{anti, maxsurp, allc, plvec,sijcol,sjicol,amax,ramax,exc,exvec,intcoal,selcij,selcji,sigcoal},
    anti = OptionValue[AntiPreKernel];
    allc = OptionValue[AllCoalitions];
    maxsurp = OptionValue[MaximumSurpluses];
    plvec = Partition[paralistIJ[T],2];
    sijcol = Partition[#,1] &/@ plvec;
    amax = If[anti===False,ParaMaxSurpluses[game, payoff,plvec],ParaAntiSurpluses[game, payoff,plvec]];	
    exc = ParaExcessPayoff[game, payoff][[1]];
    exvec = Drop[Drop[exc, 1], -1];
    intcoal = Drop[Drop[Subsets[T], 1], -1];
    sjicol = Map[Reverse[#] &, sijcol];
    ramax =  Map[Reverse[#] &, amax];
    selcij = ParallelTable[ParaSelCoal[sijcol[[i]], intcoal, exvec, amax[[i]]],{i,Length[amax]},Method -> "CoarsestGrained"];
    selcji = ParallelTable[ParaSelCoal[sjicol[[i]], intcoal, exvec, ramax[[i]]],{i,Length[ramax]},Method -> "CoarsestGrained"];
    sigcoal = MapThread[{Flatten[#1], Flatten[#2]} &,{selcij, selcji}];
    If[maxsurp === False, sigcoal,{sigcoal,amax}]
    ]



ParaSelCoal[sij_List, coal_List, redexc_List, maxexc_List, opts:OptionsPattern[ParaBestCoalitions]] := 
  Block[{allc, smc, setsij, detpos, extval, poscoal, extcoal},
    allc = OptionValue[AllCoalitions];
    smc = OptionValue[SmallestCardinality];
    setsij = MapThread[ParaTIJsets[#1, #2] &, sij][[1]];
    detpos = Outer[List, Position[coal, #] & /@ setsij // Flatten];
    extval = Extract[redexc, detpos];
    poscoal = Position[extval, First[maxexc]];
    extcoal = Extract[setsij, poscoal];
(*  Taking the coalition with smallest/largest (First/Last) cardinality if extcoal > 1 *)
    If[Length[extcoal] === 1, extcoal, 
     Which[allc === True, extcoal, True,
       Which[smc === True, First[extcoal], 
             smc === False, Last[extcoal], 
             True,  First[extcoal]]]]
    ]



ParaSetsToVec[mg_List, T_List, opts:OptionsPattern[ParaSetsToVec]] := 
    Block[{effvec, zrv, pscoal, replzr,coasts, onesoft},
    effvec = OptionValue[EffVector];
    zrv = Table[0, {i, Length[T]}];
    pscoal = ParallelMap[Outer[List, #] &, mg];
    replzr = Parallelize[Map[ReplacePart[zrv, 1, #] &, #] &/@ pscoal];
    coasts = Parallelize[MapThread[Subtract[#1, #2] &, #] &/@ replzr];
    onesoft = Table[1,{i,Length[T]}];
    If[effvec==True, Prepend[coasts,onesoft], coasts]
]


ParaMaxSurpluses[game_, payoff_List,dir_List] := 
    Block[{pli,plj,maxpi,maxpj,res},
      Parallelize[pli = First[#] &/@ dir;
                  plj = #[[2]] &/@ dir;
                  maxpi = MapThread[ParaMaxSurplus[game,#1,#2,payoff]&,{pli,plj}];
                  maxpj = MapThread[ParaMaxSurplus[game,#1,#2,payoff]&,{plj,pli}];
                  MapThread[List,{maxpi,maxpj}],Method -> "CoarsestGrained",DistributedContexts -> None]
    ]

ParaAntiSurpluses[game_, payoff_List,dir_List] := 
    Block[{pli,plj,minpi,minpj,res}, 
      Parallelize[pli = First[#] &/@ dir;
                  plj = #[[2]] &/@ dir;
                  minpi = MapThread[ParaAntiSurplus[game,#1,#2,payoff]&,{pli,plj}];
                  minpj = MapThread[ParaAntiSurplus[game,#1,#2,payoff]&,{plj,pli}];
                  MapThread[List,{minpi,minpj}],Method -> "CoarsestGrained",DistributedContexts -> None]
     ]


ParaMaxSurplus[game_, pi_, pj_, payoff_List] := 
    Block[{payass}, 
      payass = Which[Depth[payoff]==3, MapThread[Rule,{x /@ T,#}]& /@ payoff, 
                     Depth[payoff]==2, MapThread[Rule,{x /@ T,payoff}],
                     True, Print["The input 'payoff' is not a list."];Return[]];
      Which[Depth[payass] == 5,Max[ReplaceAll[(v[#] - x[#]) & /@ ParaTIJsets[pi,pj],#]] &/@ payass,
            Depth[payass] == 4,Max[ReplaceAll[(v[#] - x[#]) & /@ ParaTIJsets[pi,pj],payass]],
            True, Print["Wrong data format."];Return[]]
      ] 


ParaAntiSurplus[game_, pi_, pj_, payoff_List] := 
    Block[{payass}, 
      payass = Which[Depth[payoff]==3, MapThread[Rule,{x /@ T,#}]& /@ payoff, 
                     Depth[payoff]==2, MapThread[Rule,{x /@ T,payoff}],
                     True, Print["The input 'payoff' is not a list."];Return[]];
      Which[Depth[payass] == 5,Min[ReplaceAll[(v[#] - x[#]) & /@ ParaTIJsets[pi,pj],#]] &/@ payass,
            Depth[payass] == 4,Min[ReplaceAll[(v[#] - x[#]) & /@ ParaTIJsets[pi,pj],payass]],
            True, Print["Wrong data format."];Return[]]
      ]

ParaTIJsets[i_Integer, j_Integer]:=DeleteCases[Cases[ProperCoalitions,{___,i,___}],{___,j,___}];


ParaExcessPayoff[game_,payoff_List, opts:OptionsPattern[ParaExcessPayoff]]:= Block[{dispmat,assg,li,res},
  dispmat = OptionValue[DisplayMatrixForm];    
  If[Depth[payoff] == 2 || Depth[payoff] == 3,
    li = If[Length[Dimensions[payoff]]==1,{payoff},payoff];
    Parallelize[assg = MapThread[Rule,{Map[x,T],#}] & /@ li;
                res = (v[#]-x[#])& /@ Coalitions;
                res = ReplaceAll[res,#]&/@ assg,Method -> "CoarsestGrained",DistributedContexts -> Automatic];
    Which[dispmat == False, res, True, ParaDisplayErgb[res]],
            ParaPrintRemark[payoff]
		]
  ]

ParaDisplayErgb[payoff_List]:= Block[{exc,coal,mpc},
    exc = payoff;
    coal = Subsets[T];
    mpc = Map[Global`Co,coal];
    MatrixForm[PrependTo[exc,mpc]]
]


(* User interface to check for (anti) pre-kernel element. *)

ParaPreKernelQ[game_, payoff_List] :=Block[{tolv,graval,dimpay}, 
       graval = v[T];
       dimpay = Dimensions[payoff];
       tolv=1.5*10^(-8);
    Which[Length[dimpay] === 2,
                                 Which[ (Last[dimpay]===Length[T] && Depth[payoff] ===3),MapThread[And,{(Abs[Apply[Plus, #] - graval]<=tolv) & /@ payoff,ParaMaxExcessBalanced[game, payoff]}],
                                               True, ParaPrintRemark[payoff]],
                   Length[dimpay] === 1,
                              Which[(First[dimpay]===Length[T] && Depth[payoff] === 2 ), MapThread[And,{{Abs[Apply[Plus, payoff] - graval]<=tolv},{ParaMaxExcessBalanced[game, payoff]}}], 
                                            True, ParaPrintRemark[payoff]],
      True, ParaPrintRemark[payoff]
            ]
 ]


ParaAntiPreKernelQ[game_, payoff_List] :=Block[{tolv,graval,dimpay}, 
       graval = v[T];
       dimpay = Dimensions[payoff];
       tolv=1.5*10^(-8);
    Which[Length[dimpay] === 2,
                               Which[ (Last[dimpay]===Length[T] && Depth[payoff] ===3), MapThread[And,{(Abs[Apply[Plus, #] - graval]<= tolv) & /@ payoff,ParaMinExcessBalanced[game, payoff]}],
                                               True, ParaPrintRemark[payoff]],
                   Length[dimpay] === 1,
                              Which[(First[dimpay]===Length[T] && Depth[payoff] === 2 ), MapThread[And,{{Abs[Apply[Plus, payoff] - graval]<=tolv},{ParaMinExcessBalanced[game, payoff]}}], 
                                            True, ParaPrintRemark[payoff]],
      True, ParaPrintRemark[payoff]
            ]
 ]


ParaMaxExcessBalanced[game_, payoff_List]:= Block[{dimpay},
    dimpay = Dimensions[payoff];
    Which[Length[dimpay] === 2,
         Which[(Last[dimpay]===Length[T] && Depth[payoff] ===3), ParaMaxExcessBalCheck[game, #] & /@ payoff, 
                       True, ParaPrintRemark[payoff]], 
   Length[dimpay] === 1,
            Which[(First[dimpay]===Length[T] && Depth[payoff] === 2 ), ParaMaxExcessBalCheck[game, payoff], 
                         True,  ParaPrintRemark[payoff]], 
   True, ParaPrintRemark[payoff]]
]

ParaMaxExcessBalCheck[game_,payoff_List]:= 
 Block[{plpr,rvpr,asspay,sij,sji,msrplij,msrplji,msrij,msrji,lthij,tolvec,sysij,sysji,eqQ},
    plpr = Partition[paralistIJ[T],2];
    rvpr = ParallelMap[Reverse[#] &, plpr];
    asspay = ParaAssgPay[payoff];
    sij = ParallelMap[ParaTIJsets[#[[1]], #[[2]]] &,plpr,Method -> "CoarsestGrained"];
    sji = ParallelMap[ParaTIJsets[#[[1]], #[[2]]] &,rvpr,Method -> "CoarsestGrained"];
    {msrplij,msrplji}= {ParaMaxExcess[sij, asspay],ParaMaxExcess[sji, asspay]};
    {msrij,msrji} = {msrplij - msrplji,msrplji - msrplij};
    lthij = Binomial[Length[T],2];
    tolvec = ParallelTable[1.5*10^(-8), {i, lthij},Method -> "CoarsestGrained"];
    sysij = Union[MapThread[LessEqual, {Abs[msrij], tolvec}]];
    sysji = Union[MapThread[LessEqual, {Abs[msrji], tolvec}]];
    eqQ = Apply[Join, {sysij, sysji}];
    Apply[And, eqQ]
]


ParaMinExcessBalanced[game_, payoff_List]:= Block[{dimpay},
    dimpay = Dimensions[payoff];
    Which[Length[dimpay] === 2,
         Which[(Last[dimpay]===Length[T] && Depth[payoff] ===3), ParaMinExcessBalCheck[game, #] & /@ payoff, 
                       True, ParaPrintRemark[payoff]], 
   Length[dimpay] === 1,
            Which[(First[dimpay]===Length[T] && Depth[payoff] === 2 ), ParaMinExcessBalCheck[game, payoff], 
                         True,  ParaPrintRemark[payoff]], 
   True, ParaPrintRemark[payoff]]
]

ParaMinExcessBalCheck[game_,payoff_List]:= 
 Block[{plpr, rvpr, asspay,sij,sji,msrplij,msrplji,msrij, msrji,lthij,tolvec,sysij,sysji,eqQ},
    plpr = Partition[paralistIJ[T],2];
    rvpr = ParallelMap[Reverse[#] &,plpr];
    asspay = ParaAssgPay[payoff];
    sij = ParallelMap[ParaTIJsets[#[[1]], #[[2]]] &, plpr,Method -> "CoarsestGrained"];
    sji = ParallelMap[ParaTIJsets[#[[1]], #[[2]]] &, rvpr,Method -> "CoarsestGrained"];
     {msrplij,msrplji} = {ParaMinExcess[sij, asspay],ParaMinExcess[sji, asspay]};
     {msrij,msrji} = {msrplij - msrplji,msrplji - msrplij};
    lthij = Binomial[Length[T],2];
    tolvec = ParallelTable[1.5*10^(-8), {i, lthij}];
     sysij = Union[MapThread[LessEqual, {Abs[msrij], tolvec}]];
    sysji = Union[MapThread[LessEqual, {Abs[msrji], tolvec}]];
    eqQ = Apply[Join, {sysij, sysji}];
    Apply[And, eqQ]
]


ParaAssgPay[payoff_List] := Block[{vars},
    vars = x[#] & /@ T;
    MapThread[Rule, {vars, payoff}]
    ]

ParaMaxExcess[mgij_List, asspay_List] := ParallelMap[ParaMaxExc[#, asspay] &, mgij,Method -> "CoarsestGrained"]
ParaMinExcess[mgij_List, asspay_List] := ParallelMap[ParaMinExc[#, asspay] &, mgij,Method -> "CoarsestGrained"]

ParaMaxExc[mg_List, asspay_List] := Max[ReplaceAll[(v[#] - x[#]) & /@ mg, asspay]]
ParaMinExc[mg_List, asspay_List] := Min[ReplaceAll[(v[#] - x[#]) & /@ mg, asspay]]


(* Deriving a game from unanimity coordinates. *)

ParaCharacteristicValues[coord_List,T_,opts:OptionsPattern[]]:= Block[{},
      Which[ Length[coord] === 2^Length[T] , ParaDetWorth[coord,T] ,
                    True, ParaWrongCoordDimension[coord, T]]
]



ParaDetWorth[coord_List, T_, opts:OptionsPattern[]]:=Block[{tugb, cval},
                 tugb = ParaGameBasis[T];
                 cval = tugb.Drop[coord,1];
                 Prepend[cval,0]
]


ParaGameBasis[T_] := Block[{mgsys,gb},
    mgsys = Drop[Subsets[T], 1];
    gb = ParallelTable[If[SubsetQ[#,mgsys[[i]]], 1, 0] & /@ mgsys, {i, Length[mgsys]}]; 
    Transpose[gb]
]

(* Checking convexity and average-convexity *)

ParaConvexQ[game_]:= 
Block[{liste}, 
    liste = Flatten[ParaIncreasingMargContributions[game,#] & /@ T,1];
    Apply[And,Apply[And,liste,1]]
	]

ParaIncreasingMargContributions[game_,i_Integer]:=
	ParallelTable[(v[#]-v[DeleteCases[#,i]] <= 
          v[Union[Flatten[{#,j}]]] - v[DeleteCases[ 
            Union[Flatten[{#,j}]],i]])& /@ Take[ParaW[i],Length[ParaW[i]]-1],
              {j,1,Length[T]},Method -> "CoarsestGrained",DistributedContexts -> Automatic]

ParaW[i_Integer]:= Cases[Coalitions,{___,i,___}]

ParaAvConvexQ[game_] := Block[{dispre, pwset, chsum,delmp},
    pwset = Drop[Subsets[T],1];
    DistributeDefinitions[pwset];
    chsum = ParallelMap[ParaCheckSumQ[#, T] &, pwset,Method -> "CoarsestGrained"];
    delmp = DeleteCases[chsum, {{}, {}}];
    Apply[And, Union[chsum]]			      
 ]

ParaCheckSumQ[teilmg_List, T_] := 
  Block[{supset, smarg, dispres},
    supset = ParaOberMenge[teilmg, T];
    smarg = ParaSumMargContribution[#, teilmg] & /@ supset;
    Apply[And, Union[smarg]]
]


ParaOberMenge[teilmg_List, T_List] := Block[{compl,subc,prop},
    compl = Complement[T, teilmg];
    subc=Subsets[compl];
    prop=Join[teilmg, #] & /@ subc;
    Sort[#] & /@ prop

]

ParaSumMargContribution[superset_List, teilmg_List] := 
  Block[{dispre, delisp, delitlm, sumtmg, add},
    delisp = DeleteCases[superset, #] & /@ teilmg;
    delitlm = DeleteCases[teilmg, #] & /@ teilmg;
    sumtmg = MapThread[(v[superset] - v[#1] - v[teilmg] + v[#2]) &, {delisp, delitlm}];
    add = Apply[Plus, sumtmg] // Simplify;
    NonNegative[add]
]


(*
Def. Every subset S of T induce a subgame w via w(S) = v(S) on the new player set S.
Prop. A game v is superadditive, if for every subgame w it holds w =< dual w.
*)

ParaSuperAdditiveQ[game_] := Block[{coal, clsup},
    coal = Coalitions;
    DistributeDefinitions[v];
    clsup = Map[ParaSupAddQ[#] &, coal];
    Apply[And, clsup]
]


(*
Checking if w =< dual w holds for every subgame w.
*)

ParaSupAddQ[teilmg_List] := Block[{tpws, valsubg, duval, leq},
    tpws = Subsets[teilmg];
    valsubg = ParallelMap[v[#] &, tpws];
    duval = Parallelize[(v[T]-v[#] & /@ Reverse[tpws])];
    leq = MapThread[LessEqual, {valsubg, duval}];
    Apply[And, leq]
 ]


ParaWrongDimension:=(Print["Payoff vector has not the correct dimension!"]); 

ParaWrongCoordDimension[T_]:= Block[{},
      Print["List of unanimity coordinates of size 2 has not the correct length!"];
      Print["The correct dimension is: ", Binomial[Length[T],2]];
]
ParaWrongCoordDimension[coord_List,T_]:= Block[{},
      Print["List of unanimity coordinates of length ", Length[coord]];
      Print["is not correct!"];
      Print["The correct dimension is: ", 2^Length[T]];
]

ParaPrintRemark[payoff_List]:= (
      Print["Dimensions is equal to ",Dimensions[payoff]];
      Print["Depth is equal to ",Depth[payoff]];
      Print["Usage: MaxExcessBalanced[game,payoff] and ExcessPayoff[game,payoff]"];
      Print["The variable 'payoff' has not the correct input format."];
      Print["The variable 'payoff' must be a list of payoff vectors or a single payoff vector."]
);


SetSharedVariable[T] 
