Almost Envy-freeness, Envy-rank, and Nash Social Welfare Matchings
Authors: Alireza Farhadi, MohammadTaghi Hajiaghayi, Mohamad Latifian, Masoud Seddighin, Hadi Yami5355-5362
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Theorem 1. There exists an algorithm that finds a 0.73-EFR allocation. In addition, such an allocation can be found in polynomial time. In order to prove Theorem 1, we propose a three-step algorithm that finds a 0.73-EFR allocation in polynomial time. The following Lemma shows the approximation guarantee of our algorithm. |
| Researcher Affiliation | Collaboration | Alireza Farhadi,1 Mohammad Taghi Hajiaghayi, 1 Mohamad Latifian, 2 Masoud Seddighin, 3 Hadi Yami 4 1 University of Maryland 2 University of Toronto 3 Institute for Research in Fundamental Sciences (IPM) 4 Microsoft |
| Pseudocode | Yes | ALGORITHM 1: The outline of the 0.73-EFR algorithm. Parameters : ϕ = 3 + 1. // Step 1 Allocate NSW matching; Let ri be envy-rank of an agent i. Divide the agents into groups G1, G2, G3 as follows. Agent i belongs to G1 if ri > ϕ, belongs to G2 if 2 < ri ϕ, and belongs to G3 if ri 2; |
| Open Source Code | No | The paper does not contain any statements about providing open-source code for the methodology, nor does it provide links to any code repositories. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and proofs for fair allocation problems. It defines abstract instances with agents, goods, and valuation profiles (e.g., "an instance of the fair allocation problem with 5 items and 2 agents with the valuations represented in Figure 2"), but it does not use or refer to specific publicly available datasets for training, evaluation, or empirical analysis. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments involving data. Therefore, it does not specify any training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical, describing algorithms and proofs. It does not mention any specific hardware (e.g., GPU models, CPU types, memory) used for running experiments. |
| Software Dependencies | No | The paper describes a theoretical algorithm and does not mention any specific software dependencies or version numbers (e.g., programming languages, libraries, solvers) required for implementation or reproduction. |
| Experiment Setup | No | The paper is theoretical and focuses on the design and analysis of an algorithm. It does not describe an empirical experimental setup, including hyperparameters, model initialization, training schedules, or system-level training settings. |