Truthful aggregation of budget proposals with proportionality guarantees

9^th December 2020, 13:00
Nikos Protopapas
University of Liverpool

Abstract

We study a participatory budgeting problem, where a set of strategic agents need to decide on how to divide a budget (or any divisible good) among different projects (or any set of alternatives), by aggregating their proposals on a single division. Unfortunately, the straightforward rule which takes as input the proposals of each agent and assigns to each project the mean of the agents' proposals, is well known to be susceptible to manipulation. Recently, Freeman et al. proposed a class of mechanism for aggregating a budget that was proven to be truthful under \ell_1 preferences: Each voter has a single most preferred division and she gets dissatisfied according to the \ell_1 distance between the aggregated division and her most preferred one. The Independent Markets mechanism, a member of the aforementioned family, is proven to be proportional, in the sense that in the extreme case where all agents prefer a single project to receive the whole budget, each project is assigned a fraction of the budget equal to the proportion of voters supporting it.

In this work, we propose an extension of proportionality as follows: Given a truthful mechanism and a set of proposals, we measure how far the outcome of the mechanism is, compared to the proportional division. We call this notion \ell_1 loss and we provide upper and lower bounds on the worst-case \ell_1 loss. Work in progress.