Abstract
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.
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings of the 29th International Joint Conference on Artificial Intelligence, IJCAI 2020 |
| Editors | Christian Bessiere |
| Publisher | International Joint Conferences on Artificial Intelligence |
| Pages | 318-324 |
| Number of pages | 7 |
| ISBN (Electronic) | 9780999241165 |
| State | Published - 2020 |
| Event | 29th International Joint Conference on Artificial Intelligence, IJCAI 2020 - Yokohama, Japan Duration: Jan 1 2021 → … |
Publication series
| Name | IJCAI International Joint Conference on Artificial Intelligence |
|---|---|
| Volume | 2021-January |
| ISSN (Print) | 1045-0823 |
Conference
| Conference | 29th International Joint Conference on Artificial Intelligence, IJCAI 2020 |
|---|---|
| Country/Territory | Japan |
| City | Yokohama |
| Period | 1/1/21 → … |
Funding
This research was supported by an NRF Fellowship #R-252-000-750-733, an AI Singapore award #AISG-RP-2018-009, and th ERC Starting Grant ACCORD (GA 639945). Part of this work was done when the first author was visiting NUS. The authors thank the IJCAI 2020 and GAIW 2020 reviewers for their informative comments. Zick would like to thank his sister, Anat, for useful discussions and her insights.
ASJC Scopus subject areas
- Artificial Intelligence