Seminar Details

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' 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.

Bio:
Edith Elkind is a Ginny Rometty Professor of Computer Science at Northwestern University. She obtained her PhD from Princeton in 2005, and worked in Israel, Singapore, and the UK before joining Northwestern in 2024. She works in algorithmic game theory, with a focus on algorithms for collective decision making. She is a recipient of the SIGAI Autonomous Agents Research Award and a Fellow of EurAI. She served as a chair of multiple leading conferences in AI and algorithmic game theory (including IJCAI, ACM EC, AAMAS, WINE and COMSOC), and will serve as an editor in chief of Journal of AI Research from May 2025.