Keep Your Friends Close
Land Allocation with Friends
TL;DR: We look at algorithms for assigning land plots to families where they care about both the plot and staying near their friends. The latter externality makes the problem very hard. Undeterred, we devise an algorithm that is simple to implement, use and understand, while offering optimality guarantees.
A village in a quaint part of Israel is expanding. Lucky families are invited to pick plots of land for their new homes. However, even though the plots are about the same size and value, each family has their own particular preferences — some prefer living close to the village center, others favor living in an area with a view, and yet others prefer level plots for their home garden. If the families can give us their value for each plot, finding the assignment that maximizes total value is the classic matching problem with one-sided preferences, which is relatively easy to solve.
But real life is complicated — it turns out some families are close friends or blood relatives, and really want to live next to each other. We can formalize this by asking the families to specify a value for each plot, and a value for any friendships they have. But it turns out incorporating this small change greatly complicates the problem. In fact, even if assume all plots are identical (have the same value for all families), and friendships are binary (valued at either 0 or 1), the problem reduces to subgraph isomorphism, which is known to be really hard.
What can we do? Well, a standard approach in matching literature is serial dictatorship, which is a fancy way of saying we line everyone up in a random order, and let them pick in sequence. It’s a method that’s simple to understand and implement, and it offers some nice guarantees in many settings. What can possibly go wrong?
Let’s consider the scenario illustrated above with 4 families and 4 plots. Families 1 and 4 are friends, as are 2 and 3, all valued at 4. The plots are arranged in a line, with values to the respective families indicated by the blue arrows (if there is no arrow, they really don’t like that plot and it is valued at 0).
Let’s suppose the families pick in numerical order. They may naively proceed as follows:
Family 1 picks their favorite plot A, followed by 2 picking B. Family 3 arrives to find their favorite plot taken, and goes with their second choice at D, leaving Family 4 with C (sadly, valued at 0 to them). This assignment is illustrated on the left. Unfortunately, neither pair of friends end up next to each other, and so the friendship values are lost, for a total of 19.
Looking at this, Family 1 realizes they can do better. Let’s see what happens if they pick B instead. If they get B, 2 is forced to take C. Family 3 still gets D, but now Family 4 gets placed in A — sadly, still valued at 0 to them, but at least they get to live beside their friends! Family 1 likes this arrangement better, because they value it at 5+4=9, which is more than the 7 they received earlier. More than that, the amount of value overall is improved too, since Families 2 and 3 end up adjacent to each other, for a total of 23.
How would Family 1 know to pick plot B even though they actually prefer plot A? They would have to reason through the entire process to know which plot would be left for Family 4. If families need to perform this kind of complex calculation to ensure a good outcome, then the process will disadvantage certain participants. If we can do away with this kind of computation, the outcomes will be more fair for all involved.
Where does this complexity come from? If we think about it, it is only really complicated when one friend has to wait for many other families to pick their plots before the other friend get to go; if we can ensure friends are positioned next to each other in the line, then it will greatly simplify their decisions. This motivates the following procedure:
- Line families up randomly, as 1, 2, 3…
- Invite the next family i to pick an unclaimed plot.
- i may declare a friend j
- j skips the line and picks an unclaimed plot. However, this plot must be next to i’s. j does not get to declare another friend.
This procedure has many advantages. It greatly simplifies the thought process for each participant. When it is their turn, they simply choose their favorite plot, and declare a friend to join them next door. The protocol guarantees that the result is “optimal” in the sense that plots cannot be swapped around without upsetting any families. Running this algorithm on the above scenario indeed gives a good assignment (left).
However, it is not without its own brand of awkwardness. What if your friend is a jerk and picks a daisy field to which you are deathly allergic? One might consider an “improved” algorithm where you are not restricted to an adjacent plot when you are declared as a friend. Unfortunately, such an algorithm can be exploited by “dishonest” friendships. We leave as an exercise for the reader to work out an example where this can happen. (Hint: What happens in the scenario below, when Family 1 declares Family 3 as their friend? Solution in full paper below.)
Curious to learn more? Read our full paper, where we examine several more variations of our serial dictatorship mechanisms, and show where they breakdown. We include formal hardness reductions that show our problem is NP-complete even under several simplifying assumptions. Finally, we show that the value of friendship plays a key role in determining what algorithms can be used, and what guarantees we can make about them.
Paper: Edith Elkind, Neel Patel, Alan Tsang, Yair Zick. Keeping Your Friends Close: Land Allocation with Friends
