设施定位游戏中的公平性- 李闽溟.pdf

1、Fairness in Facility Location GamesMinming LiCity University of Hong Kongjoint work with Hau Chan,HouyuZhouIntroductionFacility Location ProblemsLibrary?Determining the optimal locations for facilities to minimize transportation costs when serving customers.Facility Location ProblemsClusteringLeftRi

2、ghtTemperature SettingElectionFacility Location GamesLibrary?Agents report their locations and aim to exert influence over the facility location in a manner that favors their own interests,i.e.,making the facility as close to their locations as possible.I can report my location to the right to make

3、the library closer to me.Mechanism Design StrategyproofnessA mechanism is strategyproof if it is in the best interest of every agent to report their true position,irrespectively of the reports of the other agents.Approximation RatioThe approximation ratio is defined as the worst-case ratio(over all

4、possible instances)between the value of the social objective achieved by the mechanism and the optimal social objective value.Procaccia and Tennenholtz,2009 A set of agents =1,A set of agents locations =1,Deterministic mechanism =;Randomized mechanism =Agent cost ,=dist(,),(,)=dist(,)Social cost sc,

5、=dist(,),sc,=sc(,)Maximum cost mc,=maxdist(,),mc,=mc(,)Procaccia and Tennenholtz,2009 For the social cost,locating the facility at the median agent location(Median Mechanism)is strategyproof and optimal.Procaccia and Tennenholtz,2009 For the maximum cost,locating the facility at the middle point bet

6、ween the leftmost and the rightmost agents locations is optimal but not strategyproof.Procaccia and Tennenholtz,2009 For the maximum cost,locating the facility at the leftmost agent location(Leftmost Mechanism)is strategyproof and has an approximation ratio of 2.Any deterministic strategyproof mecha