Reforming an Envy-Free Matching
Authors: Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki5084-5091
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. ... We prove that a shortest sequence is computationally hard to obtain even when each agent accepts at most four items and each item is accepted by at most three agents. On the other hand, we give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed. |
| Researcher Affiliation | Academia | 1Graduate School of Information Sciences, Tohoku University, Japan 2Graduate School of Informatics, Kyoto University, Japan 3Faculty of Science and Technology, Keio University, Japan 4Institute of Mathematics for Industry, Kyushu University, Japan 5Research Institute for Mathematical Sciences, Kyoto University, Japan 6Graduate School of Advanced Science and Engineering, Hiroshima University, Japan 7Graduate School of Informatics and Engineering, The University of Electro-Communications, Japan 8Faculty of Environment and Information Sciences, Yokohama National University, Japan |
| Pseudocode | No | The paper describes algorithms and proofs in narrative text, but does not include formal pseudocode blocks or clearly labeled algorithm sections. |
| Open Source Code | No | The paper is theoretical and discusses algorithmic complexity; it does not mention the release of any source code. |
| Open Datasets | No | This paper is theoretical and does not involve empirical experiments with datasets. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical experiments with data splits. |
| Hardware Specification | No | This paper is theoretical and does not describe any experiments that would require specific hardware specifications. |
| Software Dependencies | No | This paper is theoretical and does not describe any software implementation or dependencies. |
| Experiment Setup | No | This paper is theoretical and does not involve empirical experiments with specific setup details like hyperparameters. |