Fair and Efficient Allocations under Lexicographic Preferences
Authors: Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, Lirong Xia5472-5480
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments We now revisit the non-existence result in Example 2 by examining how frequently {EF, EFX, EF1, MMS} + RM allocations exist in synthetically generated data. To that end, we consider a fixed number of agents (n = 5) whose preferences over a set of m goods (where m {5, . . . , 15}) are generated using the Mallows model (Mallows 1957). Given a reference ranking L and a dispersion parameter φ [0, 1], the probability of generating a ranking i L under the Mallows model is given by 1 Z φd( , i), where Z is a normalization constant and d( ) is the Kendall s Tau distance. Thus, φ = 0 induces identical preferences (i.e., i = ) while φ = 1 is the uniform distribution. For each combination of m, n, and φ {0, 0.25, 0.5, 0.75, 1}, we sample 1000 preference profiles, and use an integer linear program to check the existence of {EF, EFX, EF1, MMS}+ RM allocations. Code and data for all our experiments is available at https://github.com/sujoyksikdar/Envy-Freeness With-Lexicographic-Preferences. Figure 2 presents our experimental results. |
| Researcher Affiliation | Academia | Hadi Hosseini,1 Sujoy Sikdar,2 Rohit Vaish,3 Lirong Xia4 1 Pennsylvania State University, University Park, Pennsylvania, USA 16802 2 Binghamton University, Binghamton, New York 13902-6000 3 Tata Institute of Fundamental Research, Mumbai, India 400005 4 Rensselaer Polytechnic Institute, Troy, New York 12180 |
| Pseudocode | Yes | ALGORITHM 1: EFX+PO and ALGORITHM 2: Input: An instance N, M, with lexicographic preferences Parameters: A permutation σ : N N of the agents Output: An allocation A A ( , . . . , ) Execute one round of serial dictatorship according to σ. Assign all remaining goods to the last agent in σ. return A |
| Open Source Code | Yes | Code and data for all our experiments is available at https://github.com/sujoyksikdar/Envy-Freeness With-Lexicographic-Preferences. |
| Open Datasets | No | The paper uses |
| Dataset Splits | No | The paper mentions sampling |
| Hardware Specification | No | The paper does not provide any specific hardware details such as GPU/CPU models or cloud instance types used for running experiments. |
| Software Dependencies | No | The paper mentions using an 'integer linear program' but does not provide specific software dependencies or version numbers (e.g., solver names, programming language versions, or library versions). |
| Experiment Setup | Yes | For each combination of m, n, and φ {0, 0.25, 0.5, 0.75, 1}, we sample 1000 preference profiles, and use an integer linear program to check the existence of {EF, EFX, EF1, MMS}+ RM allocations. |