Max-min item allocation

Erel Segal:

---

'''Max-min item allocation''' is a [[fair item allocation]] problem, in which the goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. Another term for a max-min allocation is '''egalitarian-optimal'''.

Max-min item allocation is a generalization of [[multiway number partitioning]] (the latter corresponds to the special case in which all agents have the same valuations), which is itself a generalization of the [[partition problem]] (the latter corresponds to the special case of two agents). Therefore, it is [[NP-hard]] in general.

Note the difference between max-min item allocation and ''[[Maximin share|maximin share item allocation]]''. The former is an optimization problem, while the latter is a satisfaction problem: the goal is to guarantee that each agent receives a value above a certain threshold.

The special case in which the value of each item ''j'' to each agent is either 0 or some constant ''v_j'' is called the '''santa claus problem''': santa claus has a fixed set of gifts, and wants to allocate them among children such that the least-happy child is as happy as possible.

== Algorithms ==
Below, ''n'' is the number of agents and ''m'' is the number of items.

For the special case of the santa claus problem:

* '''Bansal and Sviridenko<ref name="bs06"></ref>''' gave a <math>O(\log{\log{n}}/\log{\log{\log{n}}})</math>-approximation algorithm, based on rounding a [[Linear programming|linear program]].
*'''Feige'''<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> proved that a polynomial-time constant-factor approximation algorithm exists, but the proof used [[Lovász local lemma]] and was non-constructive.
*'''Asadpour, Feige and Saberi'''<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> gave an actual constant-factor approximation algorithm, using [[Matching in hypergraphs|hypergraph matching]]. They could not prove that it converges in a finite number of steps.
*'''Annamalai, Kalaitzis and Svensson'''<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> gave a polynomial-time 13-approximation algorithm.

For the general case, for agents with [[Additive utility|additive valuations]]:

* '''Bezakova and Dani'''<ref name="bd05"></ref> gave a <math>(m - n + 1)</math> -approximation algorithm.
*'''Asadpour and Saberi'''<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> gave a <math>O(\sqrt{n} \cdot \log^3 n)</math>-approximation algorithm. Their algorithm uses an iterative method for rounding a [[fractional matching]] on a [[Tree (graph theory)|tree]]. They also provide better bounds when it is allowed to exclude a small fraction of people from the problem.

* '''Chakrabarty, Chuzoy and Khanna'''<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> gave an <math>O(m^{\varepsilon})</math> -approximation algorithm with a run-time of <math>O(m^{1/\varepsilon})</math> , for any <math>\varepsilon\in \Omega\left(\frac{\log\log m}{\log m}\right)</math> . For the special case in which every item has nonzero utility for at most two agents, they gave a 2-factor approximation algorithm, and proved that it is hard to approximate to any better factor.
*'''Golovin'''<ref name="g05"></ref> gave an algorithm by which, for every integer <math>k</math>, a <math>(1 - 1/k)</math> fraction of the agents receive utility at least <math>OPT/k</math>. This result is obtained from rounding a suitable linear programming relaxation of the problem, and is the best possible result for this linear program. He also gave an <math>O(\sqrt{n})</math> -approximation algorithm for the special case with two classes of goods.
*'''Dall'Aglio and Mosca'''<ref name="dm07"></ref> gave an exact, branch-and-bound algorithm for two agents, based on an adaptation of the [[Adjusted winner procedure]].
For agents with [[Submodular set function|submodular utility functions]]:

*'''Golovin'''<ref name="g05" /> gave an <math>(m - n + 1)</math> -approximation algorithm, and some inapproximability results for general utility functions.
*'''Goemans, Harvey, Iwata and Mirrkoni'''<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> give a <math>O(\sqrt{m} \cdot n^{1/4} \cdot \log n\cdot \log^{3/2} m)</math>-approximation algorithm
* '''Nguyen, Roos and Rothe'''<ref name="nrr13"></ref><ref name="nnrr14"></ref> present some stronger hardness results.

For general ordinal ranking on subsets of items:

* The [[Decreasing Demand procedure|'''Decreasing Demand procedure''']] returns an egalitarian-optimal division in an ordinal sense: it maximizes the rank, in the linear-ranking of bundles, of the agent with the lowest rank. It works for any number of agents with any ordering of bundles.

== References ==

[[Category:Fair division]]
[[Category:Combinatorial optimization]]

from Wikipedia - New pages [en] https://ift.tt/2UPC9pG
via IFTTT