Ordinal Maximin Guarantees for Group Fair Division
Authors: Pasin Manurangsi, Warut Suksompong
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate fairness in the allocation of indivisible items among groups of agents using the notion of maximin share (MMS). While previous work has shown that no nontrivial multiplicative MMS approximation can be guaranteed in this setting for general group sizes, we demonstrate that ordinal relaxations are much more useful. For example, we show that if n agents are distributed equally across g groups, there exists a 1-out-of-k MMS allocation for k = O(g log(n/g)), while if all but a constant number of agents are in the same group, we obtain k = O(log n/ log log n). We also establish the tightness of these bounds and provide non-asymptotic results for the case of two groups. |
| Researcher Affiliation | Collaboration | Pasin Manurangsi1 and Warut Suksompong2 1Google Research, Thailand 2School of Computing, National University of Singapore, Singapore pasin@google.com, warut@comp.nus.edu.sg |
| Pseudocode | Yes | Our algorithm for finding the desired allocation (A1, . . . , Ag) works as follows. Let q1 = 40 log(n1+1) p , . . . , qg = 40 log(ng+1) p , and q = 1 q1 qg = 1 Construct A1, . . . , Ag, A by assigning each item from M to one of these sets independently with probabilities q1, . . . , qg, q, respectively. Let N = S j [g]{a Nj | ua( Aj) < 1}. Check whether the following two conditions hold: |N | 2g (3) ua( A) 8g a N . (4) If at least one condition does not hold, the algorithm terminates with failure. Run the algorithm from Lemma 3.3 on the agents N (with ta = 1 for all a N ) and items A. Let the output be ( Aa)a N . Finally, output (A1, . . . , Ag) defined by |
| Open Source Code | No | No statement about making the source code publicly available or a link to a repository was found. The paper mentions: "The proof of Theorem 3.5, along with all other omitted proofs, can be found in the full version of our paper [Manurangsi and Suksompong, 2024]." which points to a preprint, not source code. |
| Open Datasets | No | This paper is theoretical and does not involve the use of datasets for training or experimentation. |
| Dataset Splits | No | This paper is theoretical and does not involve datasets or their splits for validation. |
| Hardware Specification | No | This is a theoretical paper focused on mathematical proofs and algorithms, and therefore does not specify hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper focused on mathematical proofs and algorithms, and therefore does not specify software dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical and does not involve an experimental setup with hyperparameters or system-level training settings. |