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

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