  Participatory budgeting (PB) has been widely adopted and has attracted
significant research efforts; however, there is a lack of mechanisms for PB
which elicit project interactions, such as substitution and complementarity,
from voters. Also, the outcomes of PB in practice are subject to various
minimum/maximum funding constraints on 'types' of projects. We propose a novel
preference elicitation scheme for PB which allows voters to express how their
utilities from projects within 'groups' interact. We consider preference
aggregation done under minimum and maximum funding constraints on 'types' of
projects, where a project can have multiple type labels as long as this
classification can be defined by a 1-laminar structure (henceforth called
1-laminar funding constraints). Overall, we extend the Knapsack voting model of
Goel et al. [26] in two ways - enriching the preference elicitation scheme to
include project interactions and generalizing the preference aggregation scheme
to include 1-laminar funding constraints. We show that the strategyproofness
results of Goel et al. [26] for Knapsack voting continue to hold under
1-laminar funding constraints. Moreover, when the funding constraints cannot be
described by a 1-laminar structure, strategyproofness does not hold. Although
project interactions often break the strategyproofness, we study a special case
of vote profiles where truthful voting is a Nash equilibrium under substitution
project interactions. We then study the computational complexity of preference
aggregation. Social welfare maximization under project interactions is NP-hard.
As a workaround for practical instances, we give a fixed parameter tractable
(FPT) algorithm for social welfare maximization with respect to the maximum
number of projects in a group when the overall budget is specified in a fixed
number of bits.
