具有次加性估值的不可分割合唱的MMS分配和公平監督分配問題-李博.pdf

《具有次加性估值的不可分割合唱的MMS分配和公平監督分配問題-李博.pdf》由會員分享，可在線閱讀，更多相關《具有次加性估值的不可分割合唱的MMS分配和公平監督分配問題-李博.pdf（28頁珍藏版）》請在三個皮匠報告上搜索。

1、MMS Allocation of Indivisible Chores andFair Surveillance Assignment ProblemThe Hong Kong Polytechnic UniversityBo Li,Fangxiao Wang,Yu ZhouRLChina 2024，香港科技大學（廣州），2024年10月13日A set of agents =1,A set of indivisible chores =1,Each agent has a cost function()over any set of choresAn allocation is a-par

2、tition of the chores =1,2ProblemHow to fairly allocate the chores to the agents?AdditiveSubmodularSubadditive3Cost FunctionsFor any :=()For any and :()For any,:+()Agents evaluate the fairness of an allocation by comparing their received cost with a benchmark shareProportionality(PROP)An allocation i

3、s proportional if PROPfor every For divisible chores,proportionality can always be satisfiedFor indivisible chores,proportionality may not be satisfied:2 agents and 1 chore4Share-based Fairness NotionsPROP=()MinMaxShare(MMS)Budish,2011A partition is an MMS partition for agent if MMSfor every An allo

4、cation is-MMS fair(1)if MMSfor every 5Share-based Fairness NotionsMMS=min()max()(1)(2)()()is the set of-partitions of 6Approximation for GoodsValuationsApproximation for GoodsAdditiveSubmodularXOSSubadditive23-MMS Kurokawa et al.,2018,23-MMS Amanatidis,et al.,2018,23-MMS Barman and Krishnamurthy,202

5、2,34-MMS Ghodsi et al.,2021,(34+112)-MMS Garg and Taki,2021,(+)-MMS Akrami and Garg,20240.21-MMS Barman and Krishnamurthy,2022,13-MMS Ghodsi et al.,2022,-MMS Uziahu and Feige,202315-MMS Ghodsi et al.,2022,0.219-MMS Seddighin and Seddighin,2024,0.230-MMS Akrami et al.20231log-MMS Ghodsi et al.,2022 -

6、MMS Seddighin and Seddighin,20247Goods v.s.ChoresGoodsChoresAdditive(34+33836)-MMS Akrami,Garg,2024Submodular1027-MMS Uziahu and Feige,2023XoS0.230-MMS,Akrami et al.2023Subadditive1log log log-MMSSeddighin and Seddighin,20242-MMS Aziz et al.,2017 4/3-MMSBarman et al.,2020 11/9-MMS Huang et al.,2021

7、13/11 Huang et al.,2023 Unknown8Our ResultsGoodsChoresAdditive(34+33836)-MMS Akrami,Garg,2024Submodular1027-MMS Uziahu and Feige,2023XoS0.230-MMS,Akrami et al.2023Subadditive1log log log-MMSSeddighin and Seddighin,20242-MMS Aziz et al.,2017 4/3-MMSBarman et al.,2020 11/9-MMS Huang et al.,2021 13/11

8、Huang et al.,2023 For specific subadditive cost functions,a constant approximate MMS allocation always exists:job Scheduling,bin packing,and vertex cover Wang and Li.2024(min,log)-MMS Li et al.20239Submodular and Subadditive Cost Functions10Lower Bound for Submodular Cost FunctionsInstance:-dimensio

9、nal integer lattice with agents and =choresExample:=3,=27Covering planesCost function():minimum number of covering planes that can cover Theorem:for any 2,there is an instance with submodular cost functions for which no allocation is better than-MMS or log log log-MMS1=12=23=311Lower Bound for Submo

10、dular Cost FunctionsInstance:-dimensional integer lattice with agents and =choresExample:=3,=27Covering planesCost function():minimum number of covering planes that can cover Theorem:for any 2,there is an instance with submodular cost functions for which no allocation is better than-MMS or log log l

11、og-MMS12Upper Bound for Subadditive Cost FunctionsTheorem:for any instance with subadditive cost functions,there always exists a min,log-MMS allocationCase 1(log ):allocate all chores to one agent MMS13Upper Bound for Subadditive Cost FunctionsCase 2(log ):agents take turns picking log bundles with

12、the most chores from their MMS partitions 1234log bundles1 1(1)log MMS11 1 log =1 log MMS partition for agent 1:14Upper Bound for Subadditive Cost FunctionsCase 2(log ):agents take turns picking log bundles with the most chores from their MMS partitions 1234log bundles2 2(2)log MMS2|2|1 log 1 1 log

13、2 MMS partition for agent 2:15Upper Bound for Subadditive Cost FunctionsCase 2(log ):agents take turns picking log bundles with the most chores from her MMS partition()log MMS for every agent 1 log =1 log log log 1log 1Open Problem:how to compute such an allocation efficiently?16Fair Surveillance As

14、signment Problem17Fair Surveillance Assignment ProblemSetting A city represented by =(,)Residents live on the edges(streets)is the items to be allocated agents(patrollers),denoted by Agent has weight for each vertex Given ,=weight of a min vertex cover on.abcd=1=10,=1,=218Fair Surveillance Assignmen

15、t ProblemSetting Every edge is allocated to one agent If(,)and(,)are given to different agents,both agents can use vertex to set up cameraabcd=1=10,=1,=219Fair Surveillance Assignment ProblemMain Results For general instances,there exists a 4.562-MMS allocation For general instances,a 9.124-MMS allo

16、cation can be computed in poly time When 4,there exists a 2-MMS allocation No better than 2-MMS allocation is guaranteed for any The tight bound of the approximation ratio for general instances is still unknown20Fair Surveillance Assignment ProblemPreliminaries For any vertex set,let =Let(1,)be an M

17、MS partition of,then=max()Suppose is the vertex cover of G,then=max()Valid vertices to,=1 (imaginary items)Observation.For any ,suppose =(,)is a vertex cover of ()Difficulty:Different agents have different valid verticesEpstein et al.2016 gave a 2 approximation21Fair Surveillance Assignment ProblemP

18、reliminariesLemma.Given =(,),let(1,)be vertex covers Define=Define =2(“pivotal vertices”)is a vertex cover of Intuition:valid vertices(1,)form vertex covers22Fair Surveillance Assignment ProblemAlgorithmGiven =,and valid vertices(1,).Let“=3.562”.Repeat:Compute pivotal vertices=and =2 (When is update

19、d,and are also updated)1=.For every vertex ,assign to the agent:valid+smallest weight;Until(1)()or(2)all vertices in are allocatedIf(1),agent gets all edges covered by,all the other vertices are returned Remove from and move to next round.If(2)arbitrarily allocate every edge to the agent whose cover

20、s it.(is a vertex cover,so all edges are allocated)Can we allocate all edges?Why do we need to update P?Each vertex in is valid to 2 remaining agents23Fair Surveillance Assignment ProblemMain Results For general instances,there exists a 4.562-MMS allocation For general instances,a 9.124-MMS allocati

21、on can be computed in poly time When 4,there exists a 2-MMS allocation.No better than 2-MMS allocation is guaranteed for any 24Fair Surveillance Assignment ProblemWhen =Let=Let=Let=Let 0=()Observations,0 are independent sets 0 are only adjacent to vertices in 25Fair Surveillance Assignment ProblemWh

22、en =Case 1.There exists two agents 13 and 13 Assign all edges covered by to agent Assign all the other edges to agent 26Fair Surveillance Assignment ProblemWhen =Case 1.There exists two agents 13 and 13Case 2.There exists two agents 13 and 13 Find such that 23 and 13 Assign all edges covered by to a

23、gent Assign all the other edges to agent 27Fair Surveillance Assignment ProblemWhen =Case 3.For any two agents 13 and 13 Assign all edges covered by 23 to agent 2 Assign all the other edges to agent 1For agent 1,The edges allocated to agent 1 are,such that 2 3 and 3 2 They are covered by 1 2 3 11 2 3 1(1 2)+1(1 3)23 28ThanksQ&A