設施定位游戲中的公平性- 李閩溟.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

7、nism has an approximation ratio of at least 2.Procaccia and Tennenholtz,2009 For the maximum cost,locating the facility at the leftmost agent location with probability14 the rightmost agent location with probability14 the middle point of those agents with probability12,is strategyproof and has an ap

8、proximation ratio of 1.5.Any randomized strategyproof mechanism has an approximation ratio of at least 1.5.Facility Location Games:Groups&Fairness People in real-life scenarios are always in groups divided by certain criteria(e.g.,age,occupation),where people in the same group have similar character

9、istics and behaviors.Governments or policymakers are increasingly concerned about fairness among individuals and groups.Corresponding Publications Group-fair Facility Location Games Zhou,Li,Chan,IJCAI 2022 Altruism in Facility Location Games Zhou,Chan,Li,AAAI 2024Group-fair Facility Location Games T

10、here are groups,1,.How to reflect and ensure group fairness and equality among groups of agents?Group-fair Facility Location Games?Activity Event Group Fairness+Facility Location Problems:Marsh and Schilling(1994)gives many measures of group-fair objectives in the optimization literature of facility

11、 location problems.Individual Fairness+Facility Location Games:Maximum cost(Procaccia and Tennenholtz,2009)Envy(Cai et al.,2016;Chen et al.,2020)Envy ratio(Liu et al.,2020;Ding et al.,2020)Related Work We consider all group-fair cost objectives introduced by Marsh and Schilling(1994).Unfortunately,o

12、nly one objective(maximum total group cost)can have mechanisms with bounded approximation ratios.Given agents profiles =1,where=,.Maximum total group cost(mtgc):mtgc,=max1dist(,)Maximum average group cost(magc):mtgc,=max1dist,|Social Objectives We complete our results by giving lower bound of 2 for

13、both objectives.Deterministic MechanismmtgcmagcMedian Mechanism()3Leftmost Mechanism()()Majority Group Median Mechanism33 We complete our results by giving lower bound of 1.5 for both objectives.Randomized MechanismmtgcmagcRandomized Mechanism()()Narrow Randomized Mechanism()2 Narrow Randomized Mech

14、anism:locating the facility at the leftmost group median agent location with probability 14;the rightmost group median agent location with probability 14;the middle point between those points with probability 12.We also investigate Intergroup and Intragroup Fairness(IIF),which not only captures fair

15、ness between groups but also fairness within groups.We give two types of IIF objectives:IIF1,=maxjavgdist Gj+maxjmaxdist Gj mindist GjIIF2,=maxjavgdist Gj+maxdist(Gj)mindist(Gj)For IIF1,the intergroup fairness and the intragroup fairness are two separate indicators and they can be achieved by differ

16、ent groups,while for IIF2 we combine these two as one indicator of each group.Intergroup and Intragroup FairnessIntergroup and Intragroup FairnessUpper BoundLower BoundIIF144IIF244 We also investigate Intergroup and Intragroup Fairness(IIF),which not only captures fairness between groups but also fa

17、irness within groups.kth Leftmost Mechanism:locating the facility at the kth leftmost agent location.Altruism in Facility Location Games How to make my group better?Altruism Facility Location Games?Activity EventAltruistic Agents Myopic agent:minimizing the distance from the facility,=dist(,)Altruis

18、tic agent:minimizing the group cost,for all agents in group at,=dist,amc,=maxdist,where the former is called the altruistic total cost,the latter is called altruistic maximum cost.Remark:one in multiple groups has multiple altruistic costs.Strategyproofness v.s.Pareto SP Myopic agent setting:a mecha

19、nism is strategyproof if and only if it is in the best interest of every agent to report their true positions,irrespectively of the reports of the other agents.Altruistic agent setting:a mechanism is Pareto strategyproof(PSP)if and only if every agent cannot benefit at least one of their groups with

20、out hurting any other group they belongs to by reporting a false location,irrespectively of the reports of the other agents(ex-ante)/given the true profile of the other agents(ex-post).There does not exist any ex-ante PSP mechanism with a bounded approximation ratio for any altruistic cost and objec

21、tive even if there is only one group.Altruistic Total Cost Median/Leftmost/Majority Group Median are not ex-post strategyproof.Profile Preprocessing:Every agent has an ideal interval for locating the facility:If he/she is outside this interval,we map him/her to the boundaries closest to his/her loca

22、tions;If he/she is within this interval,we do not move him/her.Desired property:any facility moving farther away from the agent mapped location will result in either 1.increasing the cost of at least one of his/her groups or 2.nothing happening.Altruistic Total CostAfter Profile Preprocessing Classi

23、cal Objectives:Let the weight of a group be the number of agents in that group.Locating the facility at the weighted median of all group median locations/largest group median location gives 2 1 approximation ratio for the social cost.Locating the facility at the weighted median of group median locat

24、ions of all larger groups(size 2234|max|)gives(45)3434+19 approximation ratio for the social cost.All three mechanisms achieve 2-approximation ratio for the maximum cost.Group-fair Objectives:Majority Group Median Mechanism gives 3-approximation ratio for both group-fair objectives.Altruistic Maximu

25、m Cost Classical Objectives:Let the weight of a group be the number of agents in that group.Let the group middle point be the middle point between the leftmost agent and the rightmost agent in that group.Locating the facility at the weighted median of all group middle points gives 2-approximation ra

26、tio for the social cost,2-approximation ratio for the maximum cost.Group-fair Objectives:Locating the facility at the largest group middle point gives(|max|2+1)-approximation ratio for both group-fair objectives.SummaryClassical CostAltruistic Total Cost Altruistic Maximum CostSocial CostUB:1(2009)U

27、B:(45)34LB:UB:2LB:2Maximum CostUB:2(2009)LB:2(2009)UB:2LB:2mtgcUB:3LB:2UB:3LB:3UB:|max|2+1LB:|max|2+1magcIIF1/IIF2UB:4LB:4Future Work Tighten the gaps between the lower and upper bounds of the results.Consider alternative group-fair objectives that are appropriate for specific application domains.St

28、udy altruistic agents in other facility location games.Other Directions Beyond Real Line:circle,tree,general graphs,Euclidean space Beyond Single Facility:two facilities,multiple facilities.Beyond Classical Agent Cost Functions:obnoxious,dual preference,optional preference,fractional preference,ordinal preference,entrance fee and scaling effect,(group)-externality Beyond Classical Social Objectives:happiness,envy ratio,SoS Other variants Dynamic facility location games Cheating facilities Dual-role Thanks!Q&A