Abstract
Allocating students to schools or universities, people to teams or groups, people to urban housing, and matching users on social platforms are prominent examples of allocating limited goods, spaces, or positions to optimize social welfare. We study a welfare maximization problem that arises when such resource allocation scenarios involve peer effects, where people have preferences over the others who are nearby (e.g. their classmates, teammates, neighbors, or partners). We first develop a unified mathematical framework for this "position allocation problem," which assigns people to positions in a given network, with people caring about both their positions and their neighbors' attributes. We show that welfare maximization for the corresponding position allocation problem is computationally intractable, even when people have preferences that depend only on who is allocated to nearby positions, and those preferences satisfy simple constraints that arise naturally in urban and other real-world systems. In contrast to this computational lower bound, we show that if people can be classified into a fixed number of (demographic) groups and the network satisfies certain realistic spatial conditions, then efficiently computable allocations can be obtained for many natural scenarios. Importantly, the achieved social welfare is either optimal or arbitrarily close to optimal for natural forms of preferences. Our methods provide a foundation for position allocation with peer effects, and guide the design of optimal allocation strategies when people can be classified into a fixed number of groups in which members share similar preferences.