Prof. Elkind is interested in strategic foundations of multiagent systems, with a focus on algorithms for preference aggregation and fair division. In her recent work she focused on multiwinner voting, participatory budgeting, and temporal voting.

Her homepage: https://www.mccormick.northwestern.edu/research-faculty/directory/profiles/elkind-edith.html

AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

Participatory budgeting (PB) is a form of citizen participation that allows citizens to decide how public funds are spent. Through an election, citizens express their preferences over various projects (spending proposals). A voting mechanism then determines which projects will be selected. The Method of Equal Shares (MES) is a state-of-the-art proportional voting rule for participatory budgeting, which has been implemented in several European cities. Unfortunately, MES has a major drawback: it is not exhaustive, i.e., given a budget b, it may terminate after allocating b' < b units of currency, with the leftover budget b-b' being large enough to fund additional projects. Therefore, in practice the algorithm is combined with a completion heuristic - usually the ADD-ONE heuristic, which sequentially executes MES with virtual budgets b, b+n, b+2n, ... (where n is the number of voters) until the budget b is exhausted or a further budget increase would result in an infeasible allocation. This heuristic is computationally inefficient, and may become impractical for large instances of PB; moreover, it may fail to find an optimal virtual budget. To overcome this issue, we consider Exact Equal Shares (EES) - a simpler version of MES that is known to retain its key desirable properties. We show that EES admits an efficient algorithm for iterating through virtual budgets that is guaranteed to find an optimal virtual budget; each iteration can be computed in linear time in the number of voters, and changes the outcome in a non-trivial way. Our algorithm, which we call ADD-OPT, inspires a new heuristic ADD-OPT-SKIP that shortcuts the search for an optimal virtual budget, and offers significant reduction in computation time while maintaining essentially the same level of budget utilization, as established by comprehensive experiments on real-world PB instances from Pabulib.

Nidhi Rathi

+49 681 9325 1134

--email hidden

Zoom

897 027 2575

passcode not visible

logged in users only