Notice: This website is continuously updated as new conference proceedings and journal volumes are published. Consequently, the figures presented here may differ from those reported in our publications.
A brief overview of our methodology is provided on the Methods page, along with references to publications documenting our approach and links to the code and data used in each study.
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.
Random Assignment of Indivisible Goods under Constraints
Authors: Yasushi Kawase, Hanna Sumita, Yu Yokoi
IJCAI 2023 | Venue PDF | LLM Run Details | Input Tokens: 18,328 Total number of tokens sent to the LLM as input for this paper's analysis. | Output Tokens: 2,610 Total number of tokens produced by the LLM (including reasoning/thinking tokens) for this paper's analysis.
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate the problem of random assignment of indivisible goods, in which each agent has an ordinal preference and a constraint. Our goal is to characterize the conditions under which there always exists a random assignment that simultaneously satisfies efficiency and envy-freeness. The probabilistic serial mechanism ensures the existence of such an assignment for the unconstrained setting. In this paper, we consider a more general setting in which each agent can consume a set of items only if the set satisfies her feasibility constraint. Such constraints must be taken into account in student course placements, employee shift assignments, and so on. We demonstrate that an efficient and envy-free assignment may not exist even for the simple case of partition matroid constraints, where the items are categorized, and each agent demands one item from each category. We then identify special cases in which an efficient and envy-free assignment always exists. For these cases, the probabilistic serial cannot be naturally extended; therefore, we provide mechanisms to find the desired assignment using various approaches. |
| Researcher Affiliation | Academia | 1University of Tokyo 2Tokyo Institute of Technology |
| Pseudocode | Yes | Algorithm 1: Heterogeneous matroid constraints and identical preferences |
| Open Source Code | No | The paper does not provide a statement about open-source code availability or a link to a code repository for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not use or reference any publicly available datasets for training, validation, or testing. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental validation on data splits. Therefore, it does not specify training, validation, or test splits. |
| Hardware Specification | No | The paper does not describe any experimental setup or specific hardware used for computations. |
| Software Dependencies | No | The paper does not describe any experimental setup or specific software dependencies with version numbers. |
| Experiment Setup | No | The paper describes theoretical algorithms and proofs but does not include details about an experimental setup, such as hyperparameters or system-level training settings. |