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

《设施定位游戏中的公平性- 李闽溟.pdf》由会员分享，可在线阅读，更多相关《设施定位游戏中的公平性- 李闽溟.pdf（32页珍藏版）》请在三个皮匠报告上搜索。

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