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

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 chores⚫An allocation is a ?-partition of the chores ?={?1,…,??}2ProblemHow to fairly allocate the chores to the agents?⚫Additive⚫Submodular⚫Subadditive3Cost FunctionsFor any ?⊆?: ???=σ?∈???({?})For any ?⊆?⊆? and ?∈?∖?: ???∪?−???≥???∪?−??(?)For any ?,?⊆?: ???∪?≤???+??(?)Agents evaluate the fairness of an allocation by comparing their received cost with a benchmark share⚫Proportionality (PROP)◆An allocation ?is proportional if ????≤PROP?for every ?∈?◆For divisible chores, proportionality can always be satisfied◆For indivisible chores, proportionality may not be satisfied: 2 agents and 1 chore4Share-based Fairness NotionsPROP?=�