具有次加性估值的不可分割合唱的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𝑖=�