合作博弈中提前到达的激励-赵登吉.pdf

1、Incentives for Early Arrival in Cooperative Games(AAMAS24 Best Paper)Yaoxin Ge1,YaoZhang1,Dengji Zhao1,Zhihao GavinTang2,HuFu2,Pinyan Lu21ShanghaiTechUniversity2ShanghaiUniversityofFinanceandEconomicsCooperativeGame Playerscooperatetocreatedifferentvalues Determinehowtosharethevalue:Shapleyvalue,cor

2、e,ABBCCAABCABCA3125346CooperativeGameandShapleyValue Players:!=$,&,ValuationFunction:):2!-MarginalContribution:MC 0,),1=)1 )(1 0),0 1 ShapleyValue:SV)1!=#!1!1 1 MC(0,),1 0)Theaveragedmarginalcontributiononallpossiblejoiningorders.Shapley Value SV:AveragedMConallorders E.g.CAAC2BCCBABBABBAACCCoalitio

3、nABCABACBCABCValue312543622312213123321141SV(=2+3+3+3+3+46=3VentureCapital/DataAcquisition:JoinOrderMattersABC$100000ABC$100000ProfitShare95%AccuracyProfitShareOnlineCooperativeGamesUnknownABCJoiningOrderValueafterjoiningMarginalContribution(MC)321356TheValueShare?OnlineCooperativeGameModel Players:

4、!=$,&,ValuationFunction:):2!-JoiningOrder:M (!)(apermutationofplayers)MarginalContribution:MC 0,),1=)1 )(1 0),0 1 ShapleyValue:SV)1!=#!1!1 1 MC(0,),1 0)Howtosharethevalue:MarginalContributionUnknownABCJoiningOrderMC321UnknownBACJoiningOrderMC141AisincentivizedtoWAITIncentivizingforEarlyArrival(I4EA)

5、I4EA:Whentheorderofothersarefixed,theplayersareincentivizedtojoinassoonaspossible.UnknownCABOneSolution:TheFirstGetsAllUnknownABCJoiningOrderMC321ValueShare600NotFair!OneFairness:ShapleyFair(SF)SF:TheexpectedsharetoaplayerequalsherShapleyvalue.ABCBACCABACBBCACBAShapleyvalueaverageShapleyvalue?Unknow

6、nAOrderUnknownACOrderShapleyvalue3Shapleyvalue2.5 1.5CAAC324AsshareDecreases!OnlineIndividualRational(OIR)UnknownAX)UnknownAX*AX+OIR:X+X*X)(non-decreasing,non-negative)AlltheDesireProperties IncentivizingForEarlyArrival(I4EA)Shapley-fair(SF)OnlineIndividualRational(OIR)BAAB!UnknownAB!UnknownCaverage