Abstract | ||
---|---|---|
We provide efficient, fair, and non-manipulable mechanisms for the multi-type resource allocation problems (MTRAs) and multiple assignment problems where agents have partial preferences over bundles consisting of multiple divisible items. We uncover a natural reduction from multiple assignment problems to MTRAs, which preserves the properties of MTRA mechanisms. We extend the well-known random priority (RP) and probabilistic serial (PS) mechanisms to MTRAs with partial preferences as multi-type PS (MPS) and multi-type RP (MRP) and propose a new mechanism, multi-type general dictatorship (MGD), which combines the ideas of MPS and MRP. We show that for the unrestricted domain of partial order preferences, unfortunately, no mechanism satisfies both sd-efficiency and sd-envy-freeness, even as they each satisfy different weaker notions of the desirable properties of efficiency, fairness, and non-manipulability we consider. Notwithstanding this impossibility result, our main message is positive: When agents' preferences are represented by acyclic CP-nets, MRP satisfies ex-post-efficiency, sd-strategyproofness, and upper invariance, while MPS satisfies sd-efficiency, sd-envy-freeness, ordinal fairness, and upper invariance, recovering the properties of RP and PS; the MGD satisfies sd-efficiency, equal treatment of equals, and decomposability under the unrestricted domain of partial preferences. We introduce a natural domain of bundle net preferences, which generalizes previously studied domain restrictions of partial preferences for multiple assignment problems and is incomparable to the domain of acyclic CP-nets. We show that MRP and MPS satisfy all properties of the RP and PS under bundle net preferences as well. |
Year | DOI | Venue |
---|---|---|
2023 | 10.1016/j.artint.2022.103824 | Artificial Intelligence |
Keywords | DocType | Volume |
Computational social choice,Multi resource allocation,Partial preference,Probabilistic serial,Random priority | Journal | 314 |
Issue | ISSN | Citations |
1 | 0004-3702 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
H. Wang | 1 | 84 | 15.66 |
Sujoy Sikdar | 2 | 11 | 3.93 |
Xiaoxi Guo | 3 | 0 | 1.69 |
Lirong Xia | 4 | 1034 | 86.84 |
yongzhi cao | 5 | 63 | 10.56 |
hanpin wang | 6 | 72 | 22.42 |