[UTMD-038] Efficient, fair, and strategy-proof allocation of discrete resources under weak preferences and constraints (by Koji Yokote)


Koji Yokote


We study no-transfer allocation of indivisible objects under weak preferences and constraints. A case in point is the allocation of time slots for vaccination among residents. Under the assumption that the constraints constitute a discrete structure called an integral polymatroid, we show that our new mechanism is efficient, respects priorities, and is strategy-proof and polynomial-time computable. The mechanism determines a final allocation through an algorithm that adjusts the so-called rank profile in response to excess demands, which is similar in spirit to auction mechanisms.