Various normalizations can be applied to the original problem without changing the solution. Below,
O is the set of all objects.
Scaling If, for each agent i, all valuations are scaled by a factor k_i (which can be different for different agents), then the MMS for each agent is scaled by the same factor; therefore, every MMS allocation in the original instance is an MMS allocation in the scaled instance. It is common to scale the valuations such that the MMS of every agent is exactly 1. After this scaling, the MMS approximation problems can be stated as: • r
-fraction MMS: the total value of O is at least n; we need to give each of n agents a bundle worth at least r. •
1-of-d MMS: the total value of O is at least d; we need to give each of
n agents a bundle worth at least 1. The above scaling requires to compute the MMS of each agent, which is an NP-hard problem (
multiway number partitioning). An alternative scaling, that can be done faster, is: • r
-fraction MMS: the total value of O is exactly n; the MMS is at most 1; we need to give each of n agents a bundle worth at least r. •
1-of-d MMS: the total value of O is exactly d; the MMS is at most 1; we need to give each of n agents a bundle worth at least 1.
Allocating one object If we remove one object o from O. Then for each agent, the 1-out-of-(n - 1) MMS w.r.t. the remaining set O \setminus o is at least his 1-out-of-n MMS w.r.t. the original set O. This is because, in the original MMS partition, n - 1 parts remain intact. Now, suppose we aim to give each agent a value of r. If some object o_1 is worth at least r to at least one agent, then we can give o_1 to one such agent arbitrarily, and proceed to allocate the remaining objects to the remaining agents. Therefore, we can assume w.l.o.g. that: • r
-fraction MMS : the value of each object for all agents is less than r. • 1
-of-d
MMS : the value of each object for all agents is less than 1. This normalization works even with the fast scaling, and with arbitrary monotone valuations (even non-additive).
Bag filling Denote an object, that is valued by at most s by all agents, as an "s-small object". Suppose that all objects are s-small. Take an empty bag and fill it with object after object, until the bag is worth at least r to at least one agent. Then, give the bag to one such agent arbitrarily. Since all objects are s-small, the remaining agents value the bag at most r + s; if this value is sufficiently small, then the remaining value is sufficiently large so that we can proceed recursively. In particular, bag-filling gives as the following solutions: •
1/2-fraction MMS : take s = r = 1/2; note that by the previous normalization we can assume that all objects are 1/2-small. Initially, there are
n agents and the total value is at least n for them. After a bag is allocated, the remaining n - 1 agents value the remaining objects at least n - (r + s) = n - 1, so we can proceed recursively. •
1-of-(2n) MMS : take s = r = 1; note that by the previous normalization we can assume that all objects are 1-small. Initially, there are n agents and the total value is at least 2n for them. After a bag is allocated, the remaining n - 1 agents value the remaining objects at least 2n - (r + s) = 2n - 2 = 2(n - 1), so we can proceed recursively. These bag-filling algorithms work even with the fast scaling, so they run in polynomial time - they do not need to know the exact MMS value. In fact, both algorithms can be stated without mentioning the MMS at all: • Every agent for whom each object is worth at most 1/(2n) of the total value, receives at least 1/(2n) of the total value.
Modified bag filling: The condition that all objects are s-small can be relaxed as follows. Take some s . Denote an object that is not s-small (i.e., valued at least s by at least one agent) as an "s-large object". Suppose at most n objects are s-large. Take one s-large object o_1, put it in a bag, and fill it with s-small objects until one agent indicates that it is worth for him at least r. There must be at least one such agent, since some agent i values o_1 at some x>s. For this agent, there are at most n - 1 remaining s-large objects. By the previous normalization, these objects are still r-small, so their total value for i is at most r(n-1)
, so the value of remaining s-small objects is at least n - r(n - 1) - x = r(n - 1) + r - x \ge r-x
. Ordering An instance is
ordered if all agents have the same ordinal ranking on the objects, i.e, the objects can be numbered o_1, \dots, o_m such that, for each agent i, v_i(o_1) \ge \dots \ge v_i(o_m). Intuitively, ordered instances are hardest, since the conflict between agents is largest. Indeed, the negative instance of is ordered - the order of the objects is determined by the matrix T, which is the same for all agents. This can also be proved formally. Suppose we have an algorithm that finds, for every ordered instance, an r-fraction MMS allocation. Now, we are given a general item-allocation instance P. We solve it in the following way. • Construct an ordered instance \mathrm{ord}(P) in the following way: for every agent
i, define v_i(o_j) in \mathrm{ord}(P) as the j-th highest value in the set of values of agent i in P
. This requires O(nm\lg m) time. • Find an r-fraction MMS allocation \mathrm{ord}(A) in \mathrm{ord}(P). • Construct a
picking sequence in which the agent who received o_1 in \mathrm{ord}(A) picks first, the agent who received o_2 in \mathrm{ord}(A) picks second, etc. • Let agents pick their best items according to the picking-sequence. Let
A be the resulting allocation. In
A, each agent receives exactly the same number of items as in \mathrm{ord}(A). Moreover, each agent who received o_j in \mathrm{ord}(A), receives one of his top j items in
A. Therefore, his value for each item he got in A is at least as large as his value for the corresponding item in \mathrm{ord}(A). Therefore, the value of every agent in A is at least as high as in \mathrm{ord}(A). Since the ordering does not change the MMS values, the new allocation A is still r-fraction MMS. So when looking for r-fraction MMS allocations, we can assume w.l.o.g. that: • The ordinal ranking of the objects is the same for all agents.
Allocating two objects Suppose we find two objects
o1 and
o2, that one agent
i values at least
r, while the other agents value at most 1. Then these two objects can be allocated to
i. For the other agents, the 1-out-of-(
n-1) MMS w.r.t. the remaining set is at least his 1-out-of-
n MMS w.r.t. the original set
O. This is because, in the original MMS partition, at least
n-2 parts remain intact, while the two parts that are not intact can be combined to form a single part with a value of at least 1. This normalization works only with additive valuations. Moreover, suppose that the instance is ordered, and suppose we remove from
O the two objects
on,
on+1 (i.e., the
n-th and (
n+1)-th highest-valued items). Then for each agent, the 1-out-of-(
n-1) MMS w.r.t. the remaining set is at least his 1-out-of-
n MMS w.r.t. the original set
O. This is because, by the
pigeonhole principle, at least one MMS part of each agent must contain two or more objects from the set {
o1, ...,
on+1}. These items can be used to replace the objects given away, which results in
n-1 parts with a value of at least 1. This means that, if the objects
on,
on+1 have a value of at least the MMS for some agent
i, we can give them to
i and proceed to allocate the remaining objects to the remaining agents. Therefore, we can assume w.l.o.g. that: •
r-fraction MMS: the total value of
on,
on+1 for all agents is less than
r . In particular, the value of
on+1 and all objects after it in the ordering is less than
r/2. •
1-of-d MMS : the total value of
od,
od+1 for all agents is less than 1. In particular, the value of
od+1 and all objects after it in the ordering is less than 1/2. This normalization works even with the fast scaling. Combining it with modified bag-filling leads to the following simple algorithm for 2/3-fraction MMS. • As long as a single object is worth at least 2/3 to some agent, allocate it. • Order the instance. • As long as
on,
on+1 are worth at least 2/3 to some agent, allocate them. • Finally, there are at most
n objects with value at least 1/3; allocate them using modified bag-filling. The guarantee of this algorithm can be stated even without mentioning MMS: • Every agent, for whom
o1 is worth at most 2/(3
n) of the total value and
on + on+1 are worth together at most 2/(3
n) of the total value, receives at least 2/(3
n) of the total value. == Algorithmic problems ==