  Participatory Budgeting (PB) is a form of participatory democracy in which
citizens select a set of projects to be implemented, subject to a budget
constraint. The Method of Equal Shares (MES), introduced in [18], is a simple
iterative method for this task, which runs in polynomial time and satisfies a
demanding proportionality axiom (Extended Justified Representation) in the
setting of approval utilities. However, a downside of MES is that it is
non-exhaustive: given an MES outcome, it may be possible to expand it by adding
new projects without violating the budget constraint. To complete the outcome,
the approach currently used in practice is as follows: given an instance with
budget $b$, one searches for a budget $b'\ge b$ such that when MES is executed
with budget $b'$, it produces a maximal feasible solution for $b$. The search
is greedy, i.e., one has to execute MES from scratch for each value of $b'$. To
avoid redundant computation, we introduce a variant of MES, which we call
Adaptive Method of Equal Shares (AMES). Our method is budget-adaptive, in the
sense that, given an outcome $W$ for a budget $b$ and a new budget $b'>b$, it
can compute the outcome $W'$ for budget $b'$ by leveraging similarities between
$W$ and $W'$. This eliminates the need to recompute solutions from scratch when
increasing virtual budgets. Furthermore, AMES satisfies EJR in a certifiable
way: given the output of our method, one can check in time $O(n\log n+mn)$ that
it provides EJR (here, $n$ is the number of voters and $m$ is the number of
projects). We evaluate the potential of AMES on real-world PB data, showing
that small increases in budget typically require only minor modifications of
the outcome.
