Ioannis Caragiannis

Estimating the Expected Social Welfare and Cost of Random Serial Dictatorship

We consider the assignment problem, where n agents have to be matched to n items. Each agent has a preference order over the items. In the serial dictatorship (SD) mechanism the agents act in a particular order and pick their most preferred available item when it is their turn to...