Multi-Type Resource Allocation with Partial Preferences
Authors: Haibin Wang, Sujoy Sikdar, Xiaoxi Guo, Lirong Xia, Yongzhi Cao, Hanpin Wang2260-2267
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We propose multi-type probabilistic serial (MPS) and multitype random priority (MRP) as extensions of the well-known PS and RP mechanisms to the multi-type resource allocation problems (MTRAs) with partial preferences. In our setting, there are multiple types of divisible items, and a group of agents who have partial order preferences over bundles consisting of one item of each type. We show that for the unrestricted domain of partial order preferences, no mechanism satisfies both sd-efficiency and sd-envy-freeness. Notwithstanding this impossibility result, our main message is positive: When agents preferences are represented by acyclic CPnets, MPS satisfies sd-efficiency, sd-envy-freeness, ordinal fairness, and upper invariance, while MRP satisfies ex-postefficiency, sd-strategyproofness, and upper invariance, recovering the properties of PS and RP. Besides, we propose a hybrid mechanism, multi-type general dictatorship (MGD), combining the ideas of MPS and MRP, which satisfies sd-efficiency, equal treatment of equals and decomposability under the unrestricted domain of partial order preferences. |
| Researcher Affiliation | Academia | 1Key Laboratory of High Confidence Software Technologies (MOE), Department of Computer Science and Technology, Peking University, China 2Computer Science & Engineering, Washington University in St. Louis 3Department of Computer Science, Rensselaer Polytechnic Institute 4School of Computer Science and Cyber Engineering, Guangzhou University, China |
| Pseudocode | Yes | Algorithm 1 MRP; Algorithm 2 MPS; Algorithm 3 MGD |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the methodology is openly available. |
| Open Datasets | No | The paper describes theoretical mechanisms and their properties, but does not conduct empirical studies with training data. Therefore, no information about publicly available training datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical studies requiring validation dataset splits. Therefore, no information on validation splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not involve computational experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and describes algorithms and proofs. It does not mention any specific software dependencies or versions required for implementation or experiments. |
| Experiment Setup | No | The paper is theoretical and describes mechanisms and their properties, rather than conducting empirical experiments. Therefore, it does not include details about an experimental setup, such as hyperparameters or system-level training settings. |