Proportional Item Allocation
   HOME

TheInfoList



OR:

Proportional item allocation is a
fair item allocation Fair item allocation is a kind of a fair division problem in which the items to divide are ''discrete'' rather than continuous. The items have to be divided among several partners who value them differently, and each item has to be given as a whole ...
problem, in which the fairness criterion is proportionality - each agent should receive a bundle that they value at least as much as 1/''n'' of the entire allocation, where ''n'' is the number of agents. Since the items are indivisible, a proportional assignment may not exist. The simplest case is when there is a single item and at least two agents: if the item is assigned to one agent, the other will have a value of 0, which is less than 1/2. Therefore, the literature considers various relaxations of the proportionality requirement.


Proportional allocation

An allocation of objects is called proportional (PROP) if every agent ''i'' values his bundle at least 1/''n'' of the total. Formally, for all ''i'' (where ''M'' is the set of all goods): * V_i(X_i) \geq V_i(M)/n. A proportional division may not exist. For example, if the number of people is larger than the number of items, then some people will get no item at all and their value will be zero. Nevertheless, such a division exists with high probability for indivisible items under certain assumptions on the valuations of the agents.


Deciding whether a PROP allocation exists: cardinal utilities

Suppose the agents have
cardinal utility In economics, a cardinal utility function or scale is a utility index that preserves preference orderings uniquely up to positive affine transformations. Two utility indices are related by an affine transformation if for the value u(x_i) of one i ...
functions on items. Then, the problem of deciding whether a proportional allocation exists is
NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
: it can be reduced from the
partition problem In number theory and computer science, the partition problem, or number partitioning, is the task of deciding whether a given multiset ''S'' of positive integers can be partitioned into two subsets ''S''1 and ''S''2 such that the sum of the numbers ...
.


Deciding whether a PROP allocation exists: ordinal rankings

Suppose the agents have ordinal rankings on items. An allocation is called necessary-proportional (or sd-proportional) if it is proportional according to ''all'' valuations consistent with the rankings. It is called possibly-proportional if it is proportional according to ''at least one'' set of consistent valuations. * Pruhs and Woeginger present a polytime algorithm for deciding whether a necessary-proportional allocation exists, when agents have strict rankings. The algorithm is simpler when there are two agents. * Aziz, Gaspers, Mackenzie and Walsh extend this algorithm to agents with weak preferences, and with possibly different
entitlements An entitlement is a provision (accounting), provision made in accordance with a law, legal framework of a society. Typically, entitlements are based on concepts of principle ("rights") which are themselves based in concepts of social equality or en ...
: they show that the problem of deciding whether a necessarily-proportional allocation exists can be reduced to the problem of checking whether a
bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
admits a feasible ''b-matching'' (a matching when the edges have capacities). * They also present algorithms for deciding whether a possibly-proportional allocation exists. Its runtime is polynomial if the preferences are ''strict'', or the number of agents is a ''constant''. It is open whether the problem is in P when the number of agents is variable, and the preferences have indifferences.


Relation to other fairness criteria

With additive valuations: * Every
envy-free item allocation Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent. Since the items are i ...
is also proportional. The opposite implication is true when ''n''=2, but not when ''n''>2. * Every proportional allocation satisfies the
maximin share Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the ''1-out-of-n maximin-share'' is the maximum value that can be gained by partitioning the items into ''n'' parts and taking the part with th ...
. The opposite implication is not true.


PROP1 allocations

An allocation is called proportional up to the best ''c'' items (PROPc) if for every agent ''i'', there exists a subset of at most ''c'' items that, if given to ''i'', brings the total value of ''i'' to at least 1/''n'' of the total. Formally, for all ''i'' (where ''M'' is the set of all goods): * \exists Y\subseteq M \setminus X_i: ~~~, Y, \leq c, ~~~V_i(X_i \cup Y) \geq V_i(M)/n. An equivalent definition is: the value of each agent ''i'' is at least (1/''n'' of the total) minus (the most valuable ''c'' items not assigned to ''i''): * V_i(X_i)~ \geq~ V_i(M)/n~ - ~\max_V_i(Y) PROP0 is equivalent to proportionality, which might not exist. In contrast, a PROP1 allocation always exists and can be found e.g. by
round-robin item allocation Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that the bundle he received is at least as good as ...
. The interesting question is how to combine it with efficiency conditions such as
Pareto efficiency Pareto efficiency or Pareto optimality is a situation where no action or allocation is available that makes one individual better off without making another worse off. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engine ...
(PE).


Finding efficient PROP1 allocations

Conitzer, Freeman and Shah proved that, in the context of fair public decision making, a PROP1 allocation that is also PE. Barman and Krishnamurthy presented a strongy-polynomial-time algorithm finding a PE+PROP1 allocation for ''goods'' (objects with positive utility). Branzei and Sandomirskiy extended the condition of PROP1 to ''chores'' (objects with negative utility). Formally, for all ''i'': * \exists Y\subseteq X_i: ~~~, Y, \leq 1, ~~~V_i(X_i \setminus Y) \geq V_i(M)/n. They presented an algorithm finding a PE+PROP1 allocation of chores. The algorithm is strongly-polynomial-time if either the number of objects or the number of agents (or both) are fixed. Aziz, Caragiannis, Igarashi and Walsh extended the condition of PROP1 to ''mixed valuations'' (objects can have both positive and negative utilities). In this setting, an allocation is called PROP1 if, for each agent ''i'', if we remove one negative item from i's bundle, or add one positive item to i's bundle, then i's utility is at least 1/''n'' of the total. Their Generalized Adjusted Winner algorithm finds a PE+EF1 allocation for two agents; such an allocation is also PROP1. Aziz, Moulin and Sandomirskiy 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.


Relation to other fairness criteria

With additive valuations: * Every EF1 allocation is also PROP1, but the opposite is not necessarily true even with two agents. * The same is true for any ''c ≥'' 1: Every EF''c'' allocation is also PROP''c'', but the opposite is not necessarily true even with two agents.


PROP*(''n''-1) allocations

An allocation is called proportional from all except ''c'' items (PROP*''c'') for an agent ''i'' if there exists a set of at most ''c'' items that, if removed from the set of ''all'' items, then ''i'' values his bundle at least 1/''n'' of the remainder. Formally, for all ''i'': * \exists Y\subseteq M: ~~~, Y, \leq c, ~~~V_i(X_i) \geq V_i(M\setminus Y)/n. PROP*(''n''-1) is slightly stronger than PROP1: when ''n''=2, PROP*(''n''-1) is equivalent to EF1, but PROP1 is weaker. A PROP*(''n''-1) allocation always exists and can be found e.g. by
round-robin item allocation Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that the bundle he received is at least as good as ...
.


Relation to other fairness criteria

With additive valuations: * EF1 implies PROP*(''n''-1). The opposite implication is true when ''n''=2, but not when ''n''>2. Thus, the relation between EF1 and PROP*(''n''-1) is analogous to the relation between envy-freeness and proportionality, which shows that PROP*(''n''-1) is a more natural relaxation of proportionality than PROP1. * Moreover, for any integer ''c'' ≥ 0, EF''c'' implies PROP*((''n''-1)''c''). The opposite implication is true when ''n''=2, but not when ''n''>2. The following
maximin-share Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the ''1-out-of-n maximin-share'' is the maximum value that can be gained by partitioning the items into ''n'' parts and taking the part with th ...
approximations are implied by PROP*(''n''-1): * Multiplicative approximation: 1/''n''-fraction MMS (the 1/''n'' is tight); * Ordinal approximation: 1-of-(2''n''-1) MMS (the 2''n''-1 is tight). Similarly, for every integer ''c'', PROP*''c'' implies 1-of-(''c''+''n'') MMS. * MMS when the value function is binary. The opposite implication holds too.


PROPx allocations

An allocation is called proportional up to the worst item (PROPx) if for every agent ''i'', for any subset with one item not allocated to ''i'', if the subset is given to ''i'', then it brings his value to at least 1/''n'' of the total. Formally, for all ''i'': * \forall Y\subseteq M \setminus X_i: ~~~, Y, = 1, ~~~V_i(X_i \cup Y) \geq V_i(M)/n An equivalent definition is: the value of each agent ''i'' is at least (1/''n'' of the total) minus (the ''least'' valuable item not assigned to ''i''): * V_i(X_i)~ \geq~ V_i(M)/n~ - ~\min_V_i(Y) Obviously, PROPx is stronger than PROP1. Moreover, while PROP1 allocations always exist, PROPx allocations may not exist.


PROPm allocations

An allocation is called proportional up to the maximin item (PROPm) if the value of each agent ''i'' is at least (1/''n'' of the total) minus (the ''maximin'' item not assigned to ''i''), where the maximin item the maximum over all the other ''n''-1 agents ''j'', of the least-valuable item allocated to ''j''. Formally: * V_i(X_i)~ \geq~ V_i(M)/n~ - ~\max_ \min_V_i(Y) Obviously, PROPx is stronger than PROPm, which is stronger than PROP1. A PROPm allocation exists when the number of agents is at most 5.


References

{{reflist Fair item allocation