  Participatory budgeting is a method used by city governments to select public
projects to fund based on residents' votes. Many cities use participatory
budgeting at a district level. Typically, a budget is divided among districts
proportionally to their population, and each district holds an election over
local projects and then uses its budget to fund the projects most preferred by
its voters. However, district-level participatory budgeting can yield poor
social welfare because it does not necessarily fund projects supported across
multiple districts. On the other hand, decision making that only takes global
social welfare into account can be unfair to districts: A
social-welfare-maximizing solution might not fund any of the projects preferred
by a district, despite the fact that its constituents pay taxes to the city.
Thus, we study how to fairly maximize social welfare in a participatory
budgeting setting with a single city-wide election. We propose a notion of
fairness that guarantees each district at least as much welfare as it would
have received in a district-level election. We show that, although optimizing
social welfare subject to this notion of fairness is NP-hard, we can
efficiently construct a lottery over welfare-optimal outcomes that is fair in
expectation. Moreover, we show that, when we are allowed to slightly relax
fairness, we can efficiently compute a fair solution that is
welfare-maximizing, but which may overspend the budget.
