# Satisfactory Budget Division [Extended Abstract]

Laurent Gourvès, Michael Lampis, Nikolaos Melissinos, Aris Pagourtzis

## ► To cite this version:

Laurent Gourvès, Michael Lampis, Nikolaos Melissinos, Aris Pagourtzis. Satisfactory Budget Division [Extended Abstract]. International Conference on Autonomous Agents and Multiagent Systems, May 2025, Detroit, United States. hal-05232785

HAL Id: hal-05232785

https://hal.science/hal-05232785v1

Submitted on 1 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Satisfactory Budget Division [Extended Abstract]

Laurent Gourvès<fnref n="1" />

Michael Lampis<fnref n="1" />

Nikolaos Melissinos<fnref n="2" />

Aris Pagourtzis³

1. Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, 75016, Paris, France

2. Czech Technical University in Prague, Prague Czech Republic

3. National Technical University of Athens & Archimedes/Athena RC, Athens, Greece

laurent.gourves@lamsade.dauphine.fr, michail.lampis@lamsade.dauphine.fr, nikolaos.melissinos@fit.cvut.cz, pagour@cs.ntua.gr

**Abstract**

A divisible budget must be allocated to several projects, and agents are asked for their opinion on how much they would give to each project. We consider that an agent is satisfied by a division of the budget if, for at least a certain predefined number $\tau$ of projects, the part of the budget actually allocated to each project is at least as large as the amount the agent requested. The objective is to find a budget division that “best satisfies” the agents. In this context, different problems can be stated and we address the following ones. We study (i) the largest proportion of agents that can be satisfied for any instance, (ii) classes of instances admitting a budget division that satisfies all agents, (iii) the complexity of deciding if, for a given instance, every agent can be satisfied, and finally (iv) the question of finding, for a given instance, the smallest total budget to satisfy all agents. We provide answers to these complementary questions for several natural values of the parameter $\tau$, capturing scenarios where we seek to satisfy for each agent all; almost all; half; or at least one of her requests.

**Keywords:** Budget Division; Computational Social Choice

## 1 Introduction

For many years, social choice has concerned the AI community, particularly for the computational questions that it generates [6, 14, 20]. The central question in computational social choice is to take into account the individual preferences of several agents when developing a compromise solution. The main topics of this field are voting methods to elect representatives (e.g., committees), fair allocation of (possibly indivisible) goods and chores, or the partitioning of agents into stable subgroups (e.g., matchings, hedonic games). In addition to these fundamental topics which are now widely discussed in the literature, significant interest has recently arisen around collective budget issues [4, 2, 3, 19, 1, 7, 15, 10, 11, 21, 5, 13, 18, 9, 16]. Numerous models have been proposed and studied, including the now famous and well-studied *participatory budgeting* [8, 12]. Budgeting problems address the recurring question of how to properly use a common budget for funding a given set of projects. This article is part of this vibrant trend. Its aim is to contribute, using a new concept of agent satisfaction, to our knowledge on the existence and computation of an acceptable collective budget.<fnref n="1" />

## 2 The Model

We are given a perfectly divisible budget of (normalized) value 1, $m$ projects, and a set of agents $N = [n]$.<fnref n="2" /> Each agent $i \in N$ has reported a demand $d_i^i \in [0, 1]$ for every project $j \in [m]$. These quantities are opinions on how to spend the budget, i.e., agent $i$ would devote $d_i^i$ to the project $j$ if she was the only decision maker.

Let us clarify the semantics of the demands: a small (resp., large) demand does not mean that the agent considers the associated project to be of no (resp., great) interest. On the contrary, a demand of $d_i^i$ means that after an investment

<footnote n="1">¹See [17] for a full version of the present work.</footnote>

<footnote n="2">²For every positive integer $k$, $[k]$ denotes the set $\{1, \dots, k\}$.</footnote>
of (at least) $d_j^i$ on project j, agent i judges the status of the project j to be satisfactory. Therefore, a small (resp., large) demand from an agent means that she is quite satisfied (resp., not very satisfied) with the current state of the project and that a small (resp., large) part of the budget would make it acceptable.

A solution (a.k.a. budget division) $\mathbf{x}$ is an element of $[0, 1]^m$, and $\mathbf{x}$ is said to be budget-feasible if $\sum_{j=1}^{m} x_j \le 1$. Here, $x_j$ is the j-th coordinate of $\mathbf{x}$ and it indicates how much of the common budget is actually spent on project j. We assume that $\sum_{j=1}^{m} d_j^i \le 1$ holds for all $i \in N$ in order to express that the demands of every fixed agent are compatible with a feasible division of the budget.

This model has many applications. It captures situations where an organization (e.g., a library, a city council, a company, a university, etc.) invests in different projects (or activities, topics, facilities, etc.) and the goal is to divide the budget in a way that satisfies as much as possible the members of the organization.

Our approach is to consider that an agent $i$ is locally satisfied by $\mathbf{x}$ for a given project $j$ if $x_j \ge d_j^i$, i.e., enough resources are put on the project from the agent's perspective (and investing more than the agent's demand is not harmful). More globally, an agent is said to be satisfied by $\mathbf{x}$ if she is locally satisfied for at least $\tau$ projects, where the threshold $\tau \in [1, m]$ is a parameter belonging to the problem's input. Thus, a solution can satisfy several agents by satisfying them locally, possibly for different projects. Let us illustrate the setting with an instance in which the demands are gathered in an $n \times m$ matrix $D$ where the entry at line $i$ and column $j$ is equal to $d_j^i$.

**Instance 1.** A multimedia library has 3 kinds of documents (book, DVD, and record), and 4 employees (Alice, Bob, Carl, and Diana) who have the following demands concerning the purchase of new items.

$$ \begin{pmatrix} 0.5 & 0.5 & 0 \\ 0 & 0.5 & 0.5 \\ 0.6 & 0.1 & 0.3 \\ 0.3 & 0.1 & 0.6 \end{pmatrix} $$

Alice and Bob agree that at least half of the budget should be devoted to new DVDs. Alice thinks that the other 50% should be spent on new books, and nothing for records because there are enough albums on the shelves. However, Bob believes that the rest should be invested on new records, and nothing for books because there are quite enough books. Carl's opinion is to spend 60% of the budget on new books, 10% on new DVDs, and 30% on new records. Finally, Diana prefers to devote 30% of the budget on new books, 10% on new DVDs, and 60% on new records.

Suppose $\tau = 2$ and $\mathbf{x} = (0.3, 0.6, 0.1)$. Alice is satisfied by $\mathbf{x}$ because after the purchase of new items, the outcome meets her expectations concerning the DVD and record sections. Bob and Diana are also satisfied because enough money is invested on new books and DVDs. However Carl is not satisfied by $\mathbf{x}$ because even after the purchase of new items, the sections of books and records are below his expectations.

A typical instance of the proposed budget division problem contains multiple agents who have heterogeneous demands for the projects. Then, what solution should we decide to implement, seeking to best satisfy agents? The aim of this article is to provide several complementary approaches to address this question.

It is often impossible to satisfy all agents, as in Instance 1 when $\tau = 2$. Of course, the parameter $\tau$ plays a central role in this matter: the larger $\tau$ is, the more constraints we impose on $\mathbf{x}$ so that it satisfies an agent. We mainly consider four values of $\tau$ corresponding to four scenarios: $1, m/2, m-1$, and $m$. These values of $\tau$ range from 1 (very undemanding) to $m$ (very demanding). The value $\tau = m/2$ corresponds to an intermediate case where an agent is globally satisfied if she is locally satisfied for a majority of projects. A positive result for the demanding case $\tau = m$ is valuable, but if it is out of reach, then maybe the problem is amenable to a small relaxation; that is why we also consider $\tau = m-c$ where $c$ is constant.

# 3 Contributions

We address the following complementary questions and provide the indicated answers.

* What proportion $\rho$ of agents can be satisfied for any instance? Our findings, summarized in the following table, are bounds on the largest fraction of agents that can be satisfied for any instance, in every scenario (specified by a certain value of $\tau$).
<table><tr><td>τ</td><td>1</td><td>m/2</td><td>m-1</td><td>m</td></tr><tr><td>ρ</td><td>1</td><td>[1/2 + 1/2n, 2/3 + 1/n]</td><td>Θ(1/n)</td><td>1/n</td></tr></table>

• Which classes of instances admit a solution that satisfies all agents? For every scenario we characterize the values of $(n, m)$ for which every instance with $n$ agents and $m$ projects admits a budget-feasible solution satisfying all agents. The results are summarized in the following two tables for $\tau \in \{m/2, m-1\}$.

<table><tr><td>(case $\tau = m/2$)</td><td>$m=2$</td><td>$m=3$</td><td>$m \ge 4$</td></tr><tr><td>$n \in \{2, 3\}$</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>$n \ge 4$</td><td>✓</td><td>✗</td><td></td></tr></table><table><tr><td>(case $\tau = m-1$)</td><td>$m=2$</td><td>$m=3$</td><td>$m=4$</td><td>$m=5$</td></tr><tr><td>$n=2$</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td></tr><tr><td>$n=3$</td><td>✓</td><td>✓</td><td>✗</td><td></td></tr><tr><td>$n=4$</td><td>✓</td><td>✗</td><td></td><td></td></tr></table>

• For a given instance, what is the difficulty of deciding whether all agents can be satisfied? We show that the problem's complexity has a somewhat counterintuitive behavior. If we allow $\sum_{j \in [m]} d_j^i < 1$, then the problem is strongly NP-complete for $\tau = m-1$, but if we have $\sum_{j \in [m]} d_j^i = 1$, then the problem can be resolved in pseudopolynomial time. Surprisingly, the subtle distinction only plays a role when $\tau = m-1$ because the problem is shown strongly NP-complete for $\tau = m-c$ and all constant $c \ge 2$.

• What is the smallest total budget (possibly smaller or larger than 1) needed to satisfy all agents? Our results, summarized in the table below, follow two approaches: answering the question for a single instance or for an entire class of instances (specified by $\tau$).

<table><tr><td>τ</td><td>1</td><td>m/2</td><td>m-1</td><td>m</td></tr><tr><td>Single instance complexity (first approach)</td><td>NP-hard</td><td>NP-hard</td><td>NP-hard</td><td>P</td></tr><tr><td>Total budget upper bound (second approach)</td><td>1</td><td>2</td><td>m/2</td><td>m</td></tr></table>

In the future, it would be interesting to answer the aforementioned questions for all possible values of $\tau$. In particular, what is the exact largest fraction $\rho$ of agents that can be satisfied for any instance when $\tau = m/2$? What is the largest value of $\tau$ such that a constant fraction of agents $\rho$ is satisfied?

**Acknowledgements:** Laurent Gourvès is supported by ANR project THEMIS ANR-20-CE23-0018. Michael Lampis is supported by ANR project S-EX-AP-PE-AL ANR-21-CE48-0022. Nikolaos Melissinos is supported by the European Union under the project Robotics and advanced industrial production (reg. no. CZ.02.01.01/00/22_008/0004590). Aris Pagourtzis has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program.

## References

[1] Stéphane Airiau, Haris Aziz, Ioannis Caragiannis, Justin Kruger, Jérôme Lang, and Dominik Peters. Portioning using ordinal preferences: Fairness and efficiency. *Artif. Intell.*, 314:103809, 2023.

[2] Haris Aziz, Anna Bogomolnaia, and Hervé Moulin. Fair mixing: The case of dichotomous preferences. *ACM Trans. Economics and Comput.*, 8(4):18:1–18:27, 2020.
[3] Haris Aziz and Nisarg Shah. Participatory budgeting: Models and approaches. In Tamás Rudas and Gábor Péli, editors, *Pathways between Social Science and Computational Social Science: Theories, Methods and Interpretations*, pages 215–236. Springer, Switzerland, 2021.

[4] Anna Bogomolnaia, Hervé Moulin, and Richard Stong. Collective choice under dichotomous preferences. *Journal of Economic Theory*, 122(2):165–184, 2005.

[5] Florian Brandl, Felix Brandt, Matthias Greger, Dominik Peters, Christian Stricker, and Warut Suksompong. Funding public projects: A case for the nash product rule. *Journal of Mathematical Economics*, 99:102585, 2022.

[6] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors. *Handbook of Computational Social Choice*. Cambridge University Press, Cambridge, 2016.

[7] Markus Brill, Paul Gölz, Dominik Peters, Ulrike Schmidt-Kraepelin, and Kai Wilker. Approval-based apportionment. *Math. Program.*, 203(1):77–105, 2024.

[8] Yves Cabannes. Participatory budgeting: a significant contribution to participatory democracy. *Environment and Urbanization*, 16(1):27–46, 2004.

[9] Ioannis Caragiannis, George Christodoulou, and Nicos Protopapas. Truthful aggregation of budget proposals with proportionality guarantees. *Artificial Intelligence*, 335:104178, 2024.

[10] Pierre Cardi, Laurent Gourvès, and Julien Lesca. Worst-case bounds for spending a common budget. In Frank Dignum, Alessio Lomuscio, Ulle Endriss, and Ann Nowé, editors, *AAMAS '21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021*, pages 288–296, New York, NY, 2021. ACM.

[11] Pierre Cardi, Laurent Gourvès, and Julien Lesca. On fair and efficient solutions for budget apportionment. In Piotr Faliszewski, Viviana Mascardi, Catherine Pelachaud, and Matthew E. Taylor, editors, *21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022, Auckland, New Zealand, May 9-13, 2022*, pages 1560–1562, Richland, South Carolina, 2022. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

[12] Michiel S De Vries, Juraj Nemec, and David Špaček. International trends in participatory budgeting. Palgrave Macmillan, Springer, 2022.

[13] Edith Elkind, Warut Suksompong, and Nicholas Teh. Settling the score: Portioning with cardinal preferences. In Kobi Gal, Ann Nowé, Grzegorz J. Nalepa, Roy Fairstein, and Roxana Radulescu, editors, *ECAI 2023 - 26th European Conference on Artificial Intelligence, September 30 - October 4, 2023, Kraków, Poland - Including 12th Conference on Prestigious Applications of Intelligent Systems (PAIS 2023)*, volume 372 of *Frontiers in Artificial Intelligence and Applications*, pages 621–628, Amsterdam, The Netherlands, 2023. IOS Press.

[14] Ulle Endriss, editor. *Trends in Computational Social Choice*. Lulu.com, Raleigh, 2017.

[15] Rupert Freeman, David M. Pennock, Dominik Peters, and Jennifer Wortman Vaughan. Truthful aggregation of budget proposals. *Journal of Economic Theory*, 193:105234, 2021.

[16] Rupert Freeman and Ulrike Schmidt-Kraepelin. Project-fair and truthful mechanisms for budget aggregation. In Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan, editors, *Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2014, February 20-27, 2024, Vancouver, Canada*, pages 9704–9712, Washington DC, USA, 2024. AAAI Press.

[17] Laurent Gourvès, Michael Lampis, Nikolaos Melissinos, and Aris Pagourtzis. Satisfactory budget division. *CoRR*, abs/2502.00484, 2025.
[18] Mohak Goyal, Sukolsak Sakshuwong, Sahasrajit Sarmasarkar, and Ashish Goel. Low sample complexity participatory budgeting. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 70:1–70:20, Germany, 2023. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.

[19] Marcin Michorzewski, Dominik Peters, and Piotr Skowron. Price of fairness in budget division and probabilistic social choice. In *The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020*, pages 2184–2191, Washington, DC, 2020. AAAI Press.

[20] Jörg Rothe, editor. *Economics and Computation, An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division*. Springer texts in business and economics. Springer Cham, Cham, 2024. Second Edition.

[21] Jonathan Wagner and Reshef Meir. Strategy-proof budgeting via a vcg-like mechanism. In Argyrios Deligkas and Aris Filos-Ratsikas, editors, Algorithmic Game Theory - 16th International Symposium, SAGT 2023, Egham, UK, September 4-7, 2023, Proceedings, volume 14238 of Lecture Notes in Computer Science, pages 401–418, Cham, 2023. Springer.