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].
On Fair Division under Heterogeneous Matroid Constraints
Authors: Amitay Dror, Michal Feldman, Erel Segal-Halevi
JAIR 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our goal is to devise algorithms that find fair allocations of indivisible items among agents with heterogeneous preferences and feasibility constraints. Let us first explain what we mean by fair and what we mean by constraints . A classic notion of fairness is envy-freeness (EF), which means that every agent (weakly) prefers his or her bundle to that of any other agent. ... Among other results, we devise polynomial-time algorithms for finding EF1 allocations in the following settings: (i) n agents with heterogeneous (non-identical) binary valuations and partition matroids with heterogeneous capacities; (ii) two agents with heterogeneous additive valuations and partition matroids with heterogeneous capacities; and (iii) three agents with heterogeneous binary valuations and identical base-orderable matroid constraints. ... Open problem: Given agents with heterogeneous additive valuations and heterogeneous matroid constraints, which settings admit a complete and feasible EF1 allocation? |
| Researcher Affiliation | Academia | Amitay Dror EMAIL Michal Feldman EMAIL Tel-Aviv University, Tel-Aviv, Israel Erel Segal-Halevi EMAIL Ariel University, Ariel 40700, Israel |
| Pseudocode | Yes | ALGORITHM 1: Per-Category Round Robin (Biswas & Barman, 2018) 1: Initialize: σ an arbitrary order over the agents. For all i N, set Xi . ... ALGORITHM 7: Iterated Swaps Input: Constraints based on a base-orderable matroid M; n agents with additive valuations; A set M of items with |M| = n rank(M). 1: Initialize: X a complete feasible SWM allocation (by Theorem 9). |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on datasets. It defines abstract concepts like 'set M of m items' and refers to examples like 'allocation of shifts to medical doctors' conceptually rather than as specific datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets, thus no dataset splits are mentioned. |
| Hardware Specification | No | The paper is theoretical and discusses algorithms and proofs without conducting computational experiments that would require specific hardware. |
| Software Dependencies | No | The paper describes algorithms at a theoretical level, focusing on their computational complexity ('polynomial number of arithmetic operations' and 'independence oracle'). It does not specify any software libraries or version numbers. |
| Experiment Setup | No | The paper is theoretical and does not present experimental results, therefore it does not include details on experimental setup or hyperparameters. |