Fairly Allocating Many Goods with Few Queries
Authors: Hoon Oh, Ariel D. Procaccia, Warut Suksompong2141-2148
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic valuations, we design an algorithm that computes an allocation satisfying envy-freeness up to one good (EF1), a relaxation of envy-freeness, using a logarithmic number of queries. We show that the logarithmic query complexity bound also holds for three agents with additive valuations. These results suggest that it is possible to fairly allocate goods in practice even when the number of goods is extremely large. By contrast, we prove that computing an allocation satisfying envyfreeness and another of its relaxations, envy-freeness up to any good (EFX), requires a linear number of queries even when there are only two agents with identical additive valuations. |
| Researcher Affiliation | Academia | Hoon Oh Computer Science Department Carnegie Mellon University Ariel D. Procaccia Computer Science Department Carnegie Mellon University Warut Suksompong Department of Computer Science University of Oxford |
| Pseudocode | Yes | Algorithm 1 (for two agents with monotonic valuations) Step 1: Arrange the goods on a line in arbitrary order. Find the rightmost good g such that u1(Lg) u1(Rg {g}). Step 2: If u1(Lg) u1(Rg), consider the partition (Lg {g}, Rg); else, consider the partition (Lg, Rg {g}). Give a2 the bundle from the partition that she prefers, and a1 the remaining bundle. Algorithm 2 (for three agents with identical additive valuations) Step 1: Assume that the goods lie on a line, and denote by u the common valuation of the three agents. Let g1 be the leftmost good such that u(Lg1 {g1}) > u(G)/3, and let g2 be the rightmost good such that u(Rg2 {g2}) > u(G)/3. (Possibly g1 = g2.) Assume without loss of generality that u(Lg1) u(Rg2). Step 2: If Lg1 = , let g3 be the leftmost good such that u(Lg3 {g3}) u(Rg2). Set A = Lg3 {g3}. Else, set A = . In both cases, set C = Rg2 and B = G\(A C). Step 3: If u(C) u(B\{g2}), return the allocation (A, B, C). Else, set C = Rg2 {g2}. Partition the remaining goods into two contiguous blocks according to Lemma 4.1; denote by A the left block and B the right block. Return the allocation (A , B , C ). Algorithm 3 (for three agents with additive valuations) Step 1: Compute an EF1 allocation (A, B, C) for three identical agents with valuation u1. If a2 and a3 have different favorite bundles among A, B, C, give them their favorite bundles, and give the remaining bundle to a1. Else, assume without loss of generality that u2(A) > u2(B) u2(C) and u3(A) > max{u3(B), u3(C)}. Step 2: Let a2 divide A into A and T such that u2(A ) u2(B) and there exists g T with u2(A {g}) > u2(B). If u3(A ) max{u3(B), u3(C)}, give A to a3, B to a2, and C to a1. Compute an EF1 allocation (T1, T2, T3) of the goods in T for three identical agents with valuation u2. Let a3 choose her favorite bundle followed by a1, and let a2 take the remaining bundle. Else, we have u3(A ) < max{u3(B), u3(C)}. Step 3: Define d = u2(B) u2(A ) 0. Call a good g large if g T and u2(g) d, where we update A , T, and d during the course of the step. Let a2 find up to three large goods. The first large good is the good g T such that u2(A {g}) > u2(B). To find further large goods, let E T be such that u2(E) d, u2(E\{g}) < d for some g E, and E does not contain any identified large good. If such a set E (and good g) exists, remove the goods in E\{g} from T and add them to A , and decrease d by u2(E\{g}). (For the first large good, take E = {g}.) Then g is a new large good. If u3(A ) max{u3(B), u3(C)} with the updated set A , allocate the goods according to Step 2. So we may still assume that u3(A ) < max{u3(B), u3(C)}. On the other hand, if no such set E exists, remove all goods except the (up to two) identified large goods from T and add them to A , and decrease d by a2 s value for these goods. Step 4: Compute an EF1 allocation (T1, T2, T3) of the goods in T for three identical agents with valuation u3 in such a way that all identified large goods belong to different bundles. Step 5: Let S3 be a3 s preferred bundle between B and C, and let S1 be the other bundle. Give S2 := A to a2, S3 to a3, and S1 to a1. Step 6: If there is an identified large good in each of T1, T2, and T3, give a2 her favorite bundle Ti if we were to remove the identified large good from each of these bundles. Let a1 choose her preferred bundle from the remaining two bundles (without removing the large goods), and give a3 the remaining bundle. Else, give the first identified large good to a2 and the second identified large good (if exists) to a1. |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical, focusing on algorithm design and query complexity, rather than empirical evaluation using datasets. Therefore, it does not mention training data or provide access information for a public dataset. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe specific hardware used for running experiments. |
| Software Dependencies | No | The paper describes algorithms and proofs but does not provide specific software dependencies with version numbers for implementation. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and query complexity, not on empirical experiment setups with hyperparameters or training configurations. |