Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Fair in the Eyes of Others
Authors: Parham Shams, Aurélie Beynier, Sylvain Bouveret, Nicolas Maudet
JAIR 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We exhibit several properties of these notions. Computing the minimal threshold guaranteeing approval envy and approval non-proportionality clearly inherits well-known intractable results from envyfreeness and proportionality, but (i) we identify some tractable cases such as house allocation; and (ii) we provide a general method based on a mixed integer programming encoding of the problem, which proves to be efficient in practice. This allows us in particular to show experimentally that existence of such allocations, with a rather small threshold, is very often observed. (...) We conducted an experimental evaluation of our approval notions and solving methods. These experiments serve two purposes: (i) evaluate the behaviour of the MIPs we presented in Section 8 and of the polynomial algorithms described in Section 9 for the HAP setting, and (ii) observe the relevance of our two approval notions when varying the number of agents, of items, and the type of preferences. |
| Researcher Affiliation | Academia | Parham Shams EMAIL LIP6, Sorbonne Université, CNRS, F-75005 Paris, France Aurélie Beynier EMAIL LIP6, Sorbonne Université, CNRS, F-75005 Paris, France Sylvain Bouveret EMAIL LIG, Université Grenoble Alpes, CNRS, Grenoble INP, Grenoble, France Nicolas Maudet EMAIL LIP6, Sorbonne Université, CNRS, F-75005 Paris, France |
| Pseudocode | Yes | Algorithm 9.1: Minimizing (K-app envy)-freeness in the HAP |
| Open Source Code | No | The paper does not contain an explicit statement about the release of source code or a link to a repository. |
| Open Datasets | Yes | We have tested our methods on three types of instances: Spliddit instances (Goldman & Procaccia, 2015), instances under uniformly distributed preferences and instances under an adaptation of Mallows distributions to cardinal utilities (Durand et al., 2016). |
| Dataset Splits | No | For each couple (n, m), Table 1 reports the percentage of envy-free instances obtained over 1000 randomly generated instances. (...) For each couple (n, m), we randomly picked 60 instances over the instances not EF that were randomly generated. (...) For each couple (n, m), we generated 10 000 instances. (...) We have generated 20 instances for each number of agents from 5 to 100 agents (and objects) by steps of 5. |
| Hardware Specification | Yes | All the tests presented in this section have been run on an Intel(R) Core(TM) i7-2600K CPU with 16GB of RAM and using the Gurobi solver to solve the Mixed Integer Program. |
| Software Dependencies | Yes | All the tests presented in this section have been run on an Intel(R) Core(TM) i7-2600K CPU with 16GB of RAM and using the Gurobi solver to solve the Mixed Integer Program. |
| Experiment Setup | Yes | by setting a timeout of 1 minute, the program was able to solve all but 6 instances optimally. By extending the timeout to 10 minutes, we were able to solve 4 additional instances. (...) For each couple (n, m), we generated 10 000 instances. (...) We have generated 20 instances for each number of agents from 5 to 100 agents (and objects) by steps of 5. |