Haris Aziz, Associate Professor CSE, UNSW

The Vigilant Eating Rule: A General Approach For Probabilistic Economic Design With Constraints

Abstract

We consider the problem of probabilistic allocation of objects under ordinal preferences. Our main contribution is an allocation mechanism, called the vigilant eating rule (VER), that applies to arbitrary distributional constraints. It is constrained ordinally efficient, can be computed efficiently for a large class of constraints, and treats agents equally if they have the same preferences and are subject to the same constraints. When the set of feasible allocations is convex, we also present a characterization of our rule based on ordinal egalitarianism. Our general results concerning VER do not just apply to allocation problems but to any collective choice problem in which agents have ordinal preferences over discrete outcomes. As a case study, we assume objects have priorities for agents and apply VER to sets of probabilistic allocations that are constrained by stability. VER coincides with the (extended) probabilistic serial rule when priorities are flat and the agent proposing deterministic deferred acceptance algorithm when preferences and priorities are strict. While VER always returns a stable and constrained efficient allocation, it fails to be strategyproof, unconstrained efficient, and envy-free. We show however, that each of these three properties is incompatible with stability and constrained efficiency.

Bio

Haris Aziz is a Scientia Associate Professor at UNSW Sydney. His research interests lie at the intersection of artificial intelligence, theoretical computer science and mathematical social sciences, especially computational social choice and algorithmic game theory. Haris is a recipient of the CORE Chris Wallace Research Excellence Award (2017), the Julius Career Award (2016 - 2018) and the IEEE AI 10 to Watch Award (2015). He is on the board of directors of IFAAMAS and is an associate editor of major AI journals including JAIR and JAAMAS.