Tuesday, November 1, 2016. 12:00PM. NSH 3305.

Back to Lunch Schedule

Hadi Hosseini - Analyzing and Designing Truthful Matching Mechanisms

The problem of allocating indivisible goods to a set of self-interested agents in the absence of transferable utilities (such as money) is omnipresent in various resource allocation settings such as assigning shifts to nurses, dormitory rooms to students, and members to subcommittees. These settings leverage techniques from computer science and economics to ensure fairness and efficiency while preventing agents from manipulating the outcomes.

In the first part of this talk, I will focus on two widely-studied randomized matching mechanisms for fair allocation of indivisible goods under ordinal preferences, namely Random Serial Dictatorship and Probabilistic Serial rule. I will give an overview of their properties and discuss how empirical results can provide deeper insights into theoretical guarantees, addressing the question of which mechanism to adopt in practice.

In the second part, I will focus on sequential matching with dynamic ordinal preferences. I will briefly describe a novel model based on a generic stochastic decision process and show that, in contrast to static settings, traditional approaches are highly susceptible to manipulation in dynamic settings. I will describe how we can restore some of the desired properties by careful consideration of the history of outcomes and how this history-dependent approach impacts efficiency and fairness.

This talk is based on joint work with Kate Larson and Robin Cohen.