When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness.
Formally: Some early algorithms could find an approximately fair allocation that satisfies a weak form of efficiency, but not PE.
Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang[1] were the first to prove the existence of a PE+EF1 allocation.
Barman, Krishanmurthy and Vaish[9] presented a pseudo-polynomial time algorithm for finding PE+EF1 allocations for positive additive valuations.
Increase the prices of all objects in the MBB hierarchy by the same multiplicative factor, until one of the following three things happen: First, assume that the above algorithm is executed on an instance in which all values are powers of (1+e), for some fixed e>0.
Aziz, Caragiannis, Igarashi and Walsh[23]: sec.4 extended the condition of EF1 to mixed valuations (objects can have both positive and negative utilities).
They presented a generalization of the adjusted winner procedure, for finding a PO+EF1 allocation for two agents in time O(m2).
Formally, for all i (where M is the set of all goods): The PROP1 condition was introduced by Conitzer, Freeman and Shah[24] in the context of fair public decision making.
Barman and Krishnamurthy[25] presented a strongy-polynomial-time algorithm finding a PE+PROP1 allocation for goods (objects with positive utility).
Aziz, Caragiannis, Igarashi and Walsh[23] extended the condition of PROP1 to mixed valuations (objects can have both positive and negative utilities).
Aziz, Moulin and Sandomirskiy[27] presented a strongly polynomial-time algorithm for finding an allocation that is fractionally PE (stronger than PE) and PROP1, with general mixed valuations, even if the number of agents or objects is not fixed, and even if the agents have different entitlements.
An allocation of objects is called equitable (EQ) if the subjective value of all agents is the same.
The motivation for studying this notion comes from experiments showing that human subjects prefer equitable allocations to envy-free ones.
Formally, for all i, j: A stronger notion is equitable up to any item (EQx): for every two agents i and j, if any single item is removed from the bundle of j, then the subjective value of i is at least that of j: EQx allocations were first studied by Gourves, Monnot and Tlilane, who used a different term: "near jealosy-free".
Freeman, Sidkar, Vaish and Xia[31] proved the following stronger results: Bredereck, Kaczmarcyk, Knop and Niedermeier[32] study a setting where there are few agents (small n) and few item-types (small m), the utility per item-type is upper-bounded (by V), but there can be many items of each type.
is fixed, then it is possible to decide in polynomial time whether exists an allocation that is both E-efficient and F-fair, as long as E and F satisfy the following properties: Then, they prove that several common fairness and efficiency criteria satisfy these properties, including: The runtime of their algorithm is polynomial in the input size (in bits) times