A Bi-level model for district-fairness participatory budgeting: Decomposition methods and application

Participatory budgeting is one of the most well-known and widespread participatory programs implemented in many municipalities worldwide. Targeting poorer regions to receive a greater per capita amount of spending than wealthier regions is the most important transformational aspect of participatory budgeting. However, current approaches do not provide a precise method for achieving social justice through participatory budgeting. This paper proposes a bi-level mixed-integer non-linear optimization framework under the partial cooperation assumption to promote social justice in participatory budgeting programs. In addition, single-level reformulation and linearization techniques are presented, along with valid inequalities that speed up their resolution procedure. The single-level linear problem is solved using the Benders decomposition algorithm to find global optimality. To improve the computational performance of the proposed model on large-scale instances, a hierarchical iterative, evolutionary algorithm is proposed based on the hybrid binary particle swarm optimization and gravitational search algorithm. To illustrate the capability of the proposed model, computational experiments were conducted on both adapted examples from the literature and real-world, large-scale cases implemented in recent years in Warsaw, the capital of Poland. The results show that the proposed model is significantly more efficient, affordable, and faster than other methods presented in the literature, such as the Greedy rule and ε-district-fair lottery. In addition, the proposed model is fully operational for real-world societal problems.