Teams formation: Efficiency and approximate fairness
研究将不可分割物品分配给团队时，如何兼顾效率与近似公平，提出基于两物交换的新公平概念，并评估轮询规则和福利最大化规则的性能。
A set of kn indivisible items is to be allocated to n agents; each agent has to get exactly k items, and agents have additive utilities over bundles. Can one find an efficient and approximately fair allocation? In this setting, we introduce new notions of approximate fairness, based on exchange of two single objects, and compare them to the “traditional” ones based on disregarding one object. Our model and new fairness properties are insensitive to positive affine transformations of utilities, hence, there is no need for a separate treatment of “goods”, “bads”, and “mixed objects”. A famous Round Robin rule fares very well on all fairness accounts, but fails efficiency, while rules based on collective welfare maximization (like Nash or Leximin) cannot guarantee fairness, except on several special sub-domains (two agents, identical valuations, or binary utilities). EFx and PROPx still appear too strong. Traditional notions of approximate fairness do not allow for more positive results either.