Keeping Your Friends Close: Land Allocation with Friends

Keeping Your Friends Close: Land Allocation with Friends

Edith Elkind, Neel Patel, Alan Tsang, Yair Zick

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 318-324. https://doi.org/10.24963/ijcai.2020/45

We examine the problem of assigning plots of land to prospective buyers who prefer living next to their friends. In this setting, each agent's utility depends on the plot she receives and the identities of the agents who receive the adjacent plots. We are interested in mechanisms without money that guarantee truthful reporting of both land values and friendships, as well as Pareto optimality and computational efficiency. We explore several modifications of the Random Serial Dictatorship (RSD) mechanism, and identify one that performs well according to these criteria, We also study the expected social welfare of the assignments produced by our mechanisms when agents' values for the land plots are binary; it turns out that we can achieve good approximations to the optimal social welfare, but only if the agents value the friendships highly.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Algorithmic Game Theory