Random Assignment of Indivisible Goods under Constraints
Authors: Yasushi Kawase, Hanna Sumita, Yu Yokoi
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| 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. |