Designing Efficient and Fair Mechanisms for Multi-Type Resource Allocation

In the multi-type resource allocation problem (MTRA), there are 𝑑 ≥ 2 types of items, and 𝑛 agents who each demand one unit of items of each type and have strict linear preferences over bundles consisting of one item of each type. For MTRAs with indivisible items, we first present an impossibility result that no mechanism can satisfy both sd-efficiency and sd-envy-freeness. We show that this impossibility result is circumvented under the natural assumption of lexicographic preferences by providing lexicographic probabilistic serial (LexiPS) as an extension of the probabilistic serial (PS) mechanism. We also prove that LexiPS satisfies sd-efficiency and sd-envy-freeness. Moreover, LexiPS satisfies sd-weak-strategy proofness when agents are not allowed to misreport their importance orders. The multi-type probabilistic serial cannot deal with indivisible items, but provides a stronger efficiency guarantee under the unrestricted domain of strict linear preferences for divisible items, while also retaining desirable fairness guarantees.