We examine the problem of assigning plots of land to
prospective buyers who prefer living next to their friends. They care not only
about the plot they receive, but also about their neighbors. This externality
results in a highly non-trivial problem structure, as both friendship and land
value play a role in determining agent behavior. We examine mechanisms that
guarantee truthful reporting of both land values and friendships. We propose
variants of random serial dictatorship (RSD) that can offer both truthfulness
and welfare guarantees. Interestingly, our social welfare guarantees are
parameterized by the value of friendship: if these values are low, enforcing
truthful behavior results in poor welfare guarantees and imposes significant
constraints on agents' choices; if they are high, we achieve good approximation
to the optimal social welfare. Based on joint work with Neel Patel, Alan Tsang and Yair
Zick.
29/10/2020