The Hylland-Zeckhauser Rule Under Bi-Valued Utilities
share
The Hylland-Zeckhauser (HZ) rule is a well-known rule for probabilistic assignment of items. The complexity of the rule has received renewed interest recently with Vazirani and Yannakakis (2020) proposing a strongly polynomial-time algorithm for the rule under bi-valued utilities, and making several general insights. We study the rule under the case of agents having bi-valued utilities. We point out several characterizations of the HZ rule, drawing clearer relations with several well-known rules in the literature. As a consequence, we point out alternative strongly polynomial-time algorithms for the HZ solution. We also give reductions from computing the HZ solution to computing well-known solutions based on leximin or Nash social welfare. An interesting contrast is that the HZ rule is group-strategyproof whereas the unconstrained competitive equilibrium with equal incomes rule is not even strategyproof. We also clarify which results change when moving from 1-0 binary utilities to the more general bi-valued utilities.
READ FULL TEXT