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.