  In multi-type resource allocation (MTRA) problems, there are p $\ge$ 2 types
of items, and n 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, our first result is an impossibility
theorem that is in direct contrast to the single type (p = 1) setting: No
mechanism, the output of which is always decomposable into a probability
distribution over discrete assignments (where no item is split between agents),
can satisfy both sd-efficiency and sd-envy-freeness. To circumvent this
impossibility result, we consider the natural assumption of lexicographic
preference, and provide an extension of the probabilistic serial (PS), called
lexicographic probabilistic serial (LexiPS).We prove that LexiPS satisfies
sd-efficiency and sd-envy-freeness, retaining the desirable properties of PS.
Moreover, LexiPS satisfies sd-weak-strategyproofness when agents are not
allowed to misreport their importance orders. For MTRAs with divisible items,
we show that the existing multi-type probabilistic serial (MPS) mechanism
satisfies the stronger efficiency notion of lexi-efficiency, and is
sd-envy-free under strict linear preferences, and sd-weak-strategyproof under
lexicographic preferences. We also prove that MPS can be characterized both by
leximin-ptimality and by item-wise ordinal fairness, and the family of eating
algorithms which MPS belongs to can be characterized by no-generalized-cycle
condition.
