participatory-budgeting/final_revision/diff.tex

\documentclass[11pt,a4paper]{article}
%DIF LATEXDIFF DIFFERENCE FILE
%DIF DEL old.tex                  Sat Jul  4 17:48:08 2020
%DIF ADD ../paper/termpaper.tex   Sat Jul  4 17:42:12 2020
\usepackage{termpaper}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{microtype}
\usepackage{setspace}

\usepackage{amssymb}
\usepackage{amsmath}

\usepackage[english]{babel}
\usepackage{csquotes}
\usepackage[style=ieee,backend=biber,maxbibnames=9,mincitenames=1,maxcitenames=2]{biblatex}

\usepackage{hyperref}

\setstretch{1.07}

\addbibresource{references.bib}

% opening
\title{Participatory Budgeting: Algorithms and Complexity}
\author{
 \authorname{Tobias Eidelpes} \\
 \studentnumber{01527193} \\
 \curriculum{033 534} \\
 \email{e1527193@student.tuwien.ac.at}
}

% Numbered example environment
\newcounter{example}[section]
\newenvironment{example}[1][]{\refstepcounter{example}\par\medskip
   \noindent \textbf{Example~\theexample. #1} \rmfamily}{\medskip}
%DIF PREAMBLE EXTENSION ADDED BY LATEXDIFF
%DIF UNDERLINE PREAMBLE %DIF PREAMBLE
\RequirePackage[normalem]{ulem} %DIF PREAMBLE
\RequirePackage{color}\definecolor{RED}{rgb}{1,0,0}\definecolor{BLUE}{rgb}{0,0,1} %DIF PREAMBLE
\providecommand{\DIFaddtex}[1]{{\protect\color{blue}\uwave{#1}}} %DIF PREAMBLE
\providecommand{\DIFdeltex}[1]{{\protect\color{red}\sout{#1}}}                      %DIF PREAMBLE
%DIF SAFE PREAMBLE %DIF PREAMBLE
\providecommand{\DIFaddbegin}{} %DIF PREAMBLE
\providecommand{\DIFaddend}{} %DIF PREAMBLE
\providecommand{\DIFdelbegin}{} %DIF PREAMBLE
\providecommand{\DIFdelend}{} %DIF PREAMBLE
\providecommand{\DIFmodbegin}{} %DIF PREAMBLE
\providecommand{\DIFmodend}{} %DIF PREAMBLE
%DIF FLOATSAFE PREAMBLE %DIF PREAMBLE
\providecommand{\DIFaddFL}[1]{\DIFadd{#1}} %DIF PREAMBLE
\providecommand{\DIFdelFL}[1]{\DIFdel{#1}} %DIF PREAMBLE
\providecommand{\DIFaddbeginFL}{} %DIF PREAMBLE
\providecommand{\DIFaddendFL}{} %DIF PREAMBLE
\providecommand{\DIFdelbeginFL}{} %DIF PREAMBLE
\providecommand{\DIFdelendFL}{} %DIF PREAMBLE
%DIF HYPERREF PREAMBLE %DIF PREAMBLE
\providecommand{\DIFadd}[1]{\texorpdfstring{\DIFaddtex{#1}}{#1}} %DIF PREAMBLE
\providecommand{\DIFdel}[1]{\texorpdfstring{\DIFdeltex{#1}}{}} %DIF PREAMBLE
%DIF LISTINGS PREAMBLE %DIF PREAMBLE
\RequirePackage{listings} %DIF PREAMBLE
\RequirePackage{color} %DIF PREAMBLE
\lstdefinelanguage{DIFcode}{ %DIF PREAMBLE
%DIF DIFCODE_UNDERLINE %DIF PREAMBLE
  moredelim=[il][\color{red}\sout]{\%DIF\ <\ }, %DIF PREAMBLE
  moredelim=[il][\color{blue}\uwave]{\%DIF\ >\ } %DIF PREAMBLE
} %DIF PREAMBLE
\lstdefinestyle{DIFverbatimstyle}{ %DIF PREAMBLE
	language=DIFcode, %DIF PREAMBLE
	basicstyle=\ttfamily, %DIF PREAMBLE
	columns=fullflexible, %DIF PREAMBLE
	keepspaces=true %DIF PREAMBLE
} %DIF PREAMBLE
\lstnewenvironment{DIFverbatim}{\lstset{style=DIFverbatimstyle}}{} %DIF PREAMBLE
\lstnewenvironment{DIFverbatim*}{\lstset{style=DIFverbatimstyle,showspaces=true}}{} %DIF PREAMBLE
%DIF END PREAMBLE EXTENSION ADDED BY LATEXDIFF

\begin{document}

\maketitle

\begin{abstract}
    Participatory budgeting is a deliberative democratic process that allows
    residents to decide how public funds should be spent. By combining a form of
    preference elicitation with an aggregation method, a set of winning projects
    is determined and funded. This paper first gives an introduction into
    participatory budgeting methods and then focuses on approval-based models to
    discuss algorithmic complexity. Furthermore, \DIFaddbegin \DIFadd{this work presents }\DIFaddend a short
    overview of useful axioms that can help select one method in practice\DIFdelbegin \DIFdel{is presented. Finally, }\DIFdelend \DIFaddbegin \DIFadd{. The
    paper concludes with }\DIFaddend an outlook on future challenges surrounding
    participatory budgeting\DIFdelbegin \DIFdel{is given}\DIFdelend .
\end{abstract}

\section{Introduction}

\emph{Participatory Budgeting} (PB) is a process of democratic deliberation that
allows residents of a municipality to decide how a part of the public budget is
to be spent. It is a way to improve transparency and citizen involvement which
are two important cornerstones of a democracy. PB was first realized in the
1990s in Porto Alegre in Brazil by the Workers' Party to combat the growing
divide between the rich city center and the poor living in the greater region.
Owing to its success in the south of Brazil, PB quickly spread to North America,
Europe, Asia and Africa.

Although the process is heavily adapted by each municipality to suit the
environment in which the residents live in, it generally follows the following
stages \autocite{participatorybudgetingprojectHowPBWorks}:

\begin{description}
    \item [Design the process] A rule book is crafted to ensure that the process
        is democratic.
    \item [Collect ideas] Residents propose and discuss ideas for projects.
    \item [Develop feasible projects] The ideas are developed into projects that
        can be undertaken by the municipality.
    \item [Voting] The projects are voted on by the residents.
    \item [Aggregating votes \& funding] The votes are combined to determine a
        set of winning projects which are then funded.
\end{description}

\noindent The \DIFdelbegin \DIFdel{two last }\DIFdelend \DIFaddbegin \DIFadd{last two }\DIFaddend stages \emph{voting} and \emph{aggregating votes} are of
main interest for computer scientists \DIFdelbegin \DIFdel{, economists and social choice theorists
}\DIFdelend \DIFaddbegin \DIFadd{and economists }\DIFaddend because depending on how
voters elicit their preferences (\emph{balloting} or \emph{input method}) and
how the votes are aggregated through the use of algorithms, the outcome is
different. To study different ways of capturing votes and aggregating them, the
participatory process is modeled mathematically. This model will be called a
participatory budgeting \emph{scenario}. The aim of studying participatory
budgeting scenarios is to find ways to achieve a desirable outcome. A desirable
outcome can be one based on fairness by making sure that each voter has at least
one chosen project in the final set of winning projects for example. Other
approaches are concerned with maximizing social welfare or discouraging
\emph{gaming the voting process} (where an outcome \DIFdelbegin \DIFdel{can
}\DIFdelend \DIFaddbegin \DIFadd{cannot }\DIFaddend be manipulated by not
voting truthfully; also called \emph{strategyproofness}).

First, this paper will give a brief overview of common methods and show how a
participatory budgeting scenario can be modeled mathematically. To illustrate
these methods, one approach will be chosen and discussed in detail with respect
to algorithmic complexity and properties. Finally, the \DIFaddbegin \DIFadd{conclusion will summarize
the }\DIFaddend gained insight into participatory budgeting algorithms \DIFdelbegin \DIFdel{will be summarized and }\DIFdelend \DIFaddbegin \DIFadd{and will give }\DIFaddend an
outlook on further developments \DIFdelbegin \DIFdel{will be given}\DIFdelend \DIFaddbegin \DIFadd{and research directions}\DIFaddend .

\section{A Participatory Budgeting Framework}
\label{sec:a participatory budgeting framework}

\textcite{talmonFrameworkApprovalBasedBudgeting2019} define a participatory
budgeting scenario as a tuple $E = (P,V,c,B)$, consisting of a set of projects
$P = \{ p_1,\dots,p_m \}$ where each project $p\in P$ has an associated cost
$c(p):P\rightarrow\mathbb{R}$, a set of voters $V = \{v_1,\dots,v_n\}$ and a
budget limit $B$. The \DIFaddbegin \DIFadd{authors assume a model where the }\DIFaddend voters express
preferences over individual projects\DIFdelbegin \DIFdel{or
}\DIFdelend \DIFaddbegin \DIFadd{, although models where voters express
preferences }\DIFaddend over subsets of all projects \DIFaddbegin \DIFadd{exist}\DIFaddend . How the preferences of voters
are expressed has to be decided during the design phase of the process and is a
choice that has to be made in accordance with the method that is used for
aggregating the votes. After the voters have elicited their preferences, a set
of projects $A\subseteq P$ is selected as \emph{winning projects} according to
some rule and subject to the total budget limit $B$. For the case where projects
are indivisible, which is also called discrete, the sum of the winning projects'
costs is not allowed to exceed the limit $B$:
\begin{equation}\label{eq:1}
    \sum_{p\in A}{c(p)\leq B}.
\end{equation}
When projects can be divisible, i.e., completed to a fractional degree, \DIFdelbegin \DIFdel{the
authors define }\DIFdelend a
function $\mu(p) : P\rightarrow [0,1]$ \DIFdelbegin \DIFdel{which }\DIFdelend maps every project to an interval between
zero and one, representing the fractional degree to which this project is
completed. Since the cost of each project is a function of its degree of
completion, the goal is to select a set of projects where the cost of the degree
of completion does not exceed the budget limit:
\begin{equation}\label{eq:2}
    \sum_{p\in A}{\mu(p)\cdot c(p)\leq B}.
\end{equation}

\DIFdelbegin \DIFdel{Common ways }\DIFdelend \DIFaddbegin \DIFadd{One way }\DIFaddend to design the input method is to ask the voters to approve a subset of
projects \DIFdelbegin \DIFdel{$A_v\subseteq P$ }\DIFdelend \DIFaddbegin \DIFadd{$P_v\subseteq P$ }\DIFaddend where each individual project can be either chosen to
be in \DIFdelbegin \DIFdel{$A_v$ }\DIFdelend \DIFaddbegin \DIFadd{$P_v$ }\DIFaddend or not. This form is called \emph{dichotomous preferences} because
every project is put in one of two categories: \emph{good} or \emph{bad}.
Projects that have not been approved (are not in \DIFdelbegin \DIFdel{$A_v$}\DIFdelend \DIFaddbegin \DIFadd{$P_v$}\DIFaddend ) are assumed to be in the
bad category. This type of preference elicitation is known as approval-based
preference elicitation \DIFdelbegin \DIFdel{or balloting}\DIFdelend \DIFaddbegin \DIFadd{with dichotomous
preferences~\mbox{%DIFAUXCMD
\cite{bramsApprovalVoting1978}}\hspace{0pt}%DIFAUXCMD
}\DIFaddend . It is possible to design variations
of the described scenario by for example asking the voters to only specify at
most $k$ projects which they want to see approved ($k$-Approval)
\cite{goelKnapsackVotingParticipatory2019a}. These variations typically do not
take into account the cost that is associated with each project at the voting
stage. To alleviate this, approaches where the voters are asked to approve
projects while factoring in the cost have been proposed. After asking the voters
for their preferences, various aggregation methods\DIFdelbegin \DIFdel{can be used. }\DIFdelend \DIFaddbegin \DIFadd{, which take the votes
elicited by the voters as input, aggregate them to provide a set of winning
projects. Each voter's total utility is added to the total sum of utility that a
set of winning project provides for all voters. This type of measuring total
utility is referred to as }\emph{\DIFadd{additive utilities}}\DIFadd{.
}\DIFaddend Section~\ref{sec:approval-based budgeting} will go into detail about the
complexity and axiomatic guarantees of \DIFdelbegin \DIFdel{these methods }\DIFdelend \DIFaddbegin \DIFadd{a subset of aggregation methods called
}\emph{\DIFadd{approval-based aggregation methods}}\DIFaddend .

One such approach \DIFaddbegin \DIFadd{and a second way for preference elicitation}\DIFaddend , where the cost
and benefit of each project is factored in, is described by
\textcite{goelKnapsackVotingParticipatory2019a}, which they term \emph{knapsack
voting}. It allows voters to express preferences by factoring in the cost as
well as the benefit per unit of cost.
\DIFaddbegin \DIFadd{\mbox{%DIFAUXCMD
\textcite[p.~3]{goelKnapsackVotingParticipatory2019a} }\hspace{0pt}%DIFAUXCMD
describe a scenario
(example 1.2) where $1$-Approval voting falls short of selecting two more
valuable projects in favor of a single project even though the budget limit
would allow for the two more valuable projects to be funded. }\DIFaddend The name stems from
the well-known knapsack problem in which, given a set of items, their associated
\DIFdelbegin \DIFdel{weight and value }\DIFdelend \DIFaddbegin \DIFadd{weights and values }\DIFaddend and a weight limit, a selection of items that maximize the
value subject to the weight limit has to be chosen. In the budgeting scenario,
the items correspond to projects, the weight limit to the budget limit\DIFaddbegin \DIFadd{, the
weight of each item to the cost of each project }\DIFaddend and the value of each item to
the value that a project provides to a voter. To have a suitable metric for the
value that each voter gets from a specific project, the authors introduce
different \emph{utility models}. These models make it possible to provide
axiomatic guarantees such as strategyproofness or welfare maximization.  While
their model assumes fractional voting---that is each voter can allocate the
budget in any way they see fit---utility functions are also used by
\textcite{talmonFrameworkApprovalBasedBudgeting2019} \DIFaddbegin \DIFadd{for the case where projects
are indivisible }\DIFaddend to measure the total satisfaction that a winning set of projects
provides under an aggregation rule.

A third possibility for preference elicitation is \emph{ranked orders}. In this
scenario, voters specify a ranking over the available choices (projects) with
the highest ranked choice receiving the biggest amount of the budget and the
lowest ranked one the lowest amount of the budget.
\textcite{airiauPortioningUsingOrdinal2019} study a scenario in which the input
method is ranked orders and the projects that can be chosen are divisible. The
problem of allocating the budget to a set of winning projects under these
circumstances is referred to as \emph{portioning}. Depending on the desired
outcome, multiple aggregation methods can be combined with ranked orders.

% Cite municipalities using approval-based budgeting (Paris?)

Since approval-based \DIFdelbegin \DIFdel{methods are comparatively easy to implement and are being
}\DIFdelend \DIFaddbegin \DIFadd{budgeting is }\DIFaddend used in practice by multiple municipalities,
the next section will discuss aggregation methods, their complexity as well as
useful axioms for comparing the different aggregation rules.

\section{Approval-based budgeting}
\label{sec:approval-based budgeting}

\DIFaddbegin \subsection{\DIFadd{Greedy rules}}
\label{subsec:greedy rules}

\DIFaddend Although approval-based budgeting is also suitable for the case where the
projects can be divisible, municipalities using this method generally assume
indivisible projects. Moreover---as is the case with participatory budgeting in
general---we not only want to select one project as a winner but multiple. This
is called a multi-winner election and is in contrast to single-winner elections.
Once the votes have been cast by the voters, again assuming dichotomous
preferences, a simple aggregation rule is greedy selection. In this case the
goal is to iteratively select one project $p\in P$ that gives the maximum
satisfaction for all voters. Satisfaction can be viewed as a form of social
welfare where it is not only desirable to stay below the budget limit $B$ but
also to \DIFdelbegin \DIFdel{achieve a high score at some metric that quantifies the value that each
voter gets from the result}\DIFdelend \DIFaddbegin \DIFadd{select a set of winning projects maximizing the value for the voters}\DIFaddend .
\textcite{talmonFrameworkApprovalBasedBudgeting2019} propose three satisfaction
functions which provide this metric. Formally, they define a satisfaction
function as a function $sat : 2^P\times 2^P\rightarrow \mathbb{R}$, where $P$ is
a set of projects. A voter $v$ selects projects to be in her approval set $P_v$
and a bundle $A\subseteq P$ contains the projects that have been selected as
winners. The satisfaction that voter $v$ gets from a selected bundle $A$ is
denoted as $sat(P_v,A)$. The set $A_v = P_v\cap A$ denotes the set of approved
items by $v$ that end up in the winning bundle $A$.  A simple approach is to
count the number of projects that have been approved by a voter and which ended
up being in the winning set:
\begin{equation}\label{eq:3}
    sat_\#(P_v,A) = |A_v|
\end{equation}
Combined with the greedy rule for selecting projects, projects are iteratively
added to the winning bundle $A$ where at every iteration the project that gives
the maximum satisfaction to all voters is selected. It is assumed that the
voters' individual satisfaction can be added together to provide the
satisfaction that one project gives to all the voters \DIFaddbegin \DIFadd{(additive utilities)}\DIFaddend . This
gives the rule $\mathcal{R}_{sat_\#}^g$ which seeks to maximize $\sum_{v\in
V}sat_\#(P_v,A\cup \{p\})$ at every iteration.

Another satisfaction function assumes a relationship between the cost of the
items and a voter's satisfaction. Namely, a project that has a high cost and is
approved by a voter $v$ and ends up in the winning bundle $A$ provides more
satisfaction than a lower cost project. Equation~\ref{eq:4} gives a definition
of this property.
\begin{equation}\label{eq:4}
    sat_\$ (P_v,A) = \sum_{p\in A_v} c(p) = c(A_v)
\end{equation}

The third satisfaction function assumes that voters are content as long as there
is at least one of the projects they have approved selected to be in the winning
set. Therefore, a voter achieves satisfaction 1 when at least one approved
project ends up in the winning bundle, i.e., if $|A_v| > 0$ and 0 satisfaction
otherwise (see equation~\ref{eq:5}).
\begin{equation}\label{eq:5}
    sat_{0/1}(P_v,A) =
    \begin{cases}
        1 & \mathsf{if}\; |A_v|>0 \\
        0 & \mathsf{otherwise}
    \end{cases}
\end{equation}
The satisfaction functions from equations~\ref{eq:4} and \ref{eq:5} can also be
combined with the greedy rule, potentially giving \DIFdelbegin \DIFdel{slightly }\DIFdelend different outcomes than
$\mathcal{R}_{sat_\#}^g$. An example demonstrating the greedy rule is given in
example~\ref{ex:greedy} \DIFaddbegin \DIFadd{taken from
\mbox{%DIFAUXCMD
\textcite[p.~2182]{talmonFrameworkApprovalBasedBudgeting2019}}\hspace{0pt}%DIFAUXCMD
}\DIFaddend .

\begin{example}\label{ex:greedy}
    A set of projects $P = \{ p_2,p_3,p_4,p_5,p_6 \}$ and their associated cost
    \DIFdelbegin \DIFdel{$p_i$ where project $p_i$ costs }\DIFdelend $i$ \DIFaddbegin \DIFadd{given as subscripts (project $p_2$ costs $2$) }\DIFaddend and a budget limit $B =
    10$ is given. Futhermore, five voters \DIFdelbegin \DIFdel{vote }\DIFdelend $v_1 = \{ p_2,p_5,p_6 \}$, $v_2 = \{
    p_2, p_3,p_4,p_5 \}$, $v_3 = \{ p_3,p_4,p_5 \}$, $v_4 = \{ p_4,p_5 \}$ and
    $v_5 = \{ p_6 \}$ \DIFaddbegin \DIFadd{vote on the five projects}\DIFaddend . Under $\mathcal{R}_{sat_\#}^g$
    the winning bundle is $\{ p_4,p_5 \}$, $\mathcal{R}_{sat_\$ }^g$ gives $\{
    p_4,p_5 \}$ and $\mathcal{R}_{sat_{0/1}}^g$ $\{ p_2,p_3,p_5 \}$.
\end{example}

Computing a solution to the problem of finding a winning set of projects by
using greedy rules can be done in polynomial time due to their iterative nature
\DIFdelbegin \DIFdel{.
The downside to using a greedy selection process is that the provided solution
might not be optimal with respect to the satisfaction.
}\DIFdelend \DIFaddbegin \DIFadd{where each iteration takes polynomial time.
}\DIFaddend

\DIFdelbegin \DIFdel{To be able to compute optimal solutions,
}\DIFdelend \DIFaddbegin \subsection{\DIFadd{Max rules}}
\label{subsec:max rules}

\DIFaddend \textcite{talmonFrameworkApprovalBasedBudgeting2019} suggest combining the
satisfaction functions with a maximization rule. The maximization rule always
selects a winning set of projects that maximizes the sum of the voters'
satisfaction:
\begin{equation}\label{eq:6}
    \max_{A\subseteq P}\sum_{v\in V}sat(P_v,A)
\end{equation}
The max rule can then be used with the three satisfaction functions in the same
way, giving: $\mathcal{R}_{sat_\#}^m$, $\mathcal{R}_{sat_\$ }^m$ and
$\mathcal{R}_{sat_{0/1}}^m$. Example~\ref{ex:max} shows that the selection of
winning projects is not as intuitive as when using the greedy rule. Whereas it
was still possible to compute a solution without any tools for the greedy
selection, the max rule requires knowing the possible sets of projects
beforehand in order to select the bundle with the maximum satisfaction. This
hints at the complexity of the max rule being harder to solve than the greedy
rule. The authors confirm this by identifying $\mathcal{R}_{sat_\$ }^m$ as weakly
\textsf{NP}-hard for the problem of finding a winning set that gives at least a
specified amount of satisfaction. The proof follows from \DIFdelbegin \DIFdel{a reduction to }\DIFdelend \DIFaddbegin \DIFadd{reducing }\DIFaddend the subset sum
problem \DIFdelbegin \DIFdel{which asks the }\DIFdelend \DIFaddbegin \DIFadd{to the problem of asking the }\DIFaddend question of given a set of numbers (in this
case the cost associated with each project) and a number $B$ (the budget limit)
does any subset of the numbers sum to exactly $B$? Because the subset sum
problem is solvable by a dynamic programming algorithm in $O(B\cdot |P|)$ where
$P$ is the set of projects, $\mathcal{R}_{sat_\$ }^m$ is solvable in
pseudo-polynomial time. Finding a solution using the rule
$\mathcal{R}_{sat_\#}^m$ however, is doable in polynomial time due to the
problem's relation to the knapsack problem. \DIFdelbegin \DIFdel{If the input (either projects or
voters) is represented in unary, a dynamic programming algorithm is bounded by a
polynomial in the length of the input. }\DIFdelend For $\mathcal{R}_{sat_{0/1}}^m$,
finding a set of projects that gives at least a certain amount of satisfaction
is \textsf{NP}-hard. Assuming that the cost of all of the projects is one unit,
the rule is equivalent to the max cover problem because we are searching for a
subset of all projects with the number of the projects (the total cost due to
the projects given in unit cost) smaller or equal to the budget limit $B$ and
want to maximize the number of voters that are represented by the subset. \DIFaddbegin \DIFadd{The
bigger the resulting set of projects, the more voters are satisfied.
}\DIFaddend

\begin{example}\label{ex:max}
    Taking the initial setup from example~\ref{ex:greedy}: $P = \{
    p_2,p_3,p_4,p_5,p_6 \}$ and their associated cost \DIFdelbegin \DIFdel{$p_i$ where project $p_i$
    costs }\DIFdelend $i$ \DIFaddbegin \DIFadd{given as subscripts
    (project $p_2$ has a cost of $2$)}\DIFaddend , a budget limit $B = 10$ and the five
    voters: $v_1 = \{ p_2,p_5,p_6 \}$, $v_2 = \{ p_2, p_3,p_4,p_5 \}$, $v_3 = \{
    p_3,p_4,p_5 \}$, $v_4 = \{ p_4,p_5 \}$ and $v_5 = \{ p_6 \}$. We get $\{
    p_2,p_3,p_5 \}$ for $\mathcal{R}_{sat_\#}^m$, $\{ p_4,p_5 \}$ for
    $\mathcal{R}_{sat_\$ }^m$ and $\{ p_4,p_6 \}$ for
    $\mathcal{R}_{sat_{0/1}}^m$.  Especially the last rule is interesting
    because it provides \DIFdelbegin \DIFdel{the highest }\DIFdelend \DIFaddbegin \DIFadd{a high }\DIFaddend amount of satisfaction \DIFdelbegin \DIFdel{possible
    }\DIFdelend by covering each voter
    with at least one project.  Project $p_6$ covers voters $v_1$ and $v_5$ and
    project $p_4$ voters $v_2$, $v_3$ and $v_4$.
\end{example}

\DIFaddbegin \subsection{\DIFadd{Proportional greedy rules}}
\label{subsec:proportional greedy rules}

\DIFaddend The third rule, which places a heavy emphasis on cost versus benefit, is similar
to the greedy rule but instead of disregarding the satisfaction per cost that a
project provides, it seeks to maximize the sum of satisfaction divided by cost
for a project $p\in P$:
\begin{equation}
    \frac{\sum_{v\in V}sat(P_v,A\cup\{p\}) - \sum_{v\in V}sat(P_v,A)}{c(p)}
\end{equation}
\textcite{talmonFrameworkApprovalBasedBudgeting2019} call this type of
aggregation rule \emph{proportional greedy rule}. \DIFdelbegin \DIFdel{Example}\DIFdelend \DIFaddbegin \DIFadd{Their example}\DIFaddend ~\ref{ex:prop
greedy} shows how the outcome of a budgeting scenario might look like compared
to using a simple greedy rule or a max rule. Since the proportional greedy rule
is a variation of the simple greedy rule, it is therefore also solvable in
polynomial time. The variation of computing the satisfaction per unit of cost
does not change the complexity since it only adds an additional step which can
be done in constant time.

\begin{example}\label{ex:prop greedy}
    We again have the same set of projects $P = \{ p_2,p_3,p_4,p_5,p_6 \}$, the
    same budget limit of $B = 10$ and the five voters: $v_1 = \{ p_2,p_5,p_6
    \}$, $v_2 = \{ p_2, p_3,p_4,p_5 \}$, $v_3 = \{ p_3,p_4,p_5 \}$, $v_4 = \{
    p_4,p_5 \}$ and $v_5 = \{ p_6 \}$. If we combine the satisfaction function
    $sat_\#$ from equation~\ref{eq:3} with the proportional greedy rule, we get
    the same result as with the simple greedy rule of $\{ p_4,p_5 \}$. While the
    simple greedy rule selects first $p_5$ and then $p_4$, the proportional
    greedy rule first selects $p_4$ and then $p_5$. The rule
    $\mathcal{R}_{sat_\$ }^p$ yields the same result as $\mathcal{R}_{sat_\$ }^g$
    and $\mathcal{R}_{sat_\$ }^m$ of $\{ p_4,p_5 \}$. $\mathcal{R}_{sat_{0/1}}^p$
    however, gives $\{ p_2,p_3,p_4 \}$.
\end{example}

A benefit of the three discussed satisfaction functions is that they can be
\DIFdelbegin \DIFdel{viewed as constraint satisfaction problems (CSPs) and can thus be }\DIFdelend formulated using integer linear programming (ILP). Although integer programming
is \textsf{NP}-complete, efficient solvers are readily available for these types
of problems\DIFdelbegin \DIFdel{. }\DIFdelend \DIFaddbegin \DIFadd{, which can be an important factor when choosing a budgeting
algorithm. For the problem of finding a set of projects that achieve at least a
given satisfaction, }\DIFaddend \textcite{talmonFrameworkApprovalBasedBudgeting2019} show
that the rule $\mathcal{R}_{sat_{0/1}}^m$ is similar to the max cover problem
which can be approximated with \DIFdelbegin \DIFdel{a $(1-\frac{1}{\epsilon})$-approximation algorithm, where
$\epsilon > 0$ is a fixed parameter that is chosen depending on the error of the
approximation. In fact, \mbox{%DIFAUXCMD
\textcite{khullerBudgetedMaximumCoverage1999} }\hspace{0pt}%DIFAUXCMD
show that
an approximation algorithm with the same ratio exists not only for the case
where the projects have unit cost but also for the general cost version}\DIFdelend \DIFaddbegin \DIFadd{an approximation ratio of $(1-\frac{1}{e})$,
giving a reasonably good solution while taking much less time to compute}\DIFaddend .

Instead of sacrificing exactness to get a better running time,
\textcite{talmonFrameworkApprovalBasedBudgeting2019} show that the
$\mathcal{R}_{sat_{0/1}}^m$ rule is fixed parameter tractable for the number of
voters $|V|$. A problem is fixed parameter tractable if there exists an
algorithm that decides each instance of the problem in $O(f(k)\cdot p(n))$ where
\DIFdelbegin \DIFdel{$p(n)$ is }\DIFdelend \DIFaddbegin \DIFadd{$n$ is the input size, $k$ some parameter (in this case the cost of each
project), $p(n)$ }\DIFaddend a polynomial function and $f(k)$ an arbitrary function in $k$.
It is crucial to note that $f(k)$ does not admit functions of the form $n^k$.
\DIFdelbegin \DIFdel{The
algorithm }\DIFdelend \DIFaddbegin \DIFadd{\mbox{%DIFAUXCMD
\textcite{talmonFrameworkApprovalBasedBudgeting2019} }\hspace{0pt}%DIFAUXCMD
provide a proof }\DIFaddend for the
maximum rule \DIFdelbegin \DIFdel{tries }\DIFdelend \DIFaddbegin \DIFadd{by trying }\DIFaddend to guess the number of voters that are represented by the
same project. The estimation is then used to pick a project which has the lowest
cost and satisfies exactly the estimated amount of voters.

\section{Normative Axioms}
\label{sec:normative axioms}

Axioms in the context of participatory budgeting define some kind of property of
a budgeting method that might be desirable to have. Generally it is beneficial
if a certain method satisfies as many axioms as possible as this gives the
method a strong theoretical backbone. One set of axioms, discussed by
\textcite{talmonFrameworkApprovalBasedBudgeting2019}, relates to the cost of
projects. Another possibility is to look at the \emph{fairness} associated with
a particular set of winning projects. Fairness captures the notion of for
example protecting minorities and their preferences.
\textcite{azizProportionallyRepresentativeParticipatory2018} propose axioms that
are representative of the broad spectrum of \DIFdelbegin \DIFdel{choices }\DIFdelend \DIFaddbegin \DIFadd{votes }\DIFaddend which voters can \DIFdelbegin \DIFdel{make}\DIFdelend \DIFaddbegin \DIFadd{cast}\DIFaddend . Other
fairness-based approaches are proposed by
\textcite{fainCoreParticipatoryBudgeting2016}, \DIFdelbegin \DIFdel{using }\DIFdelend \DIFaddbegin \DIFadd{by calculating }\DIFaddend the core of a
solution, although they focus on cases where voters elicit their preferences via
a cardinal utility function. The notion of core is also studied by
\textcite{fainFairAllocationIndivisible2018} for the case where voters have
additive utilities over the selection of projects\DIFdelbegin \DIFdel{, which is similar to the rules
discussed above}\DIFdelend . To illustrate working with
axioms, the following will introduce intuitive properties which are then applied
to the rules discussed in section~\ref{sec:approval-based budgeting}.

\DIFaddbegin \subsection{\DIFadd{Inclusion Maximality}}
\label{subsec:inclusion Maximality}

\DIFaddend A simple axiom is termed \emph{exhaustiveness} by
\textcite{azizParticipatoryBudgetingModels2020} and \emph{inclusion maximality}
by \textcite{talmonFrameworkApprovalBasedBudgeting2019}. Inclusion maximality
encodes the requirement that if it is possible to fund more projects because the
budget is not yet exhausted, then we should. Greedy and proportional greedy
rules satisfy this axiom because of their inherent iterative process that
terminates only when the budget does not allow more projects to be funded. For
the maximum rules inclusion maximality still holds because for two feasible sets
of projects where one set is a subset of the other and the smaller set is
winning then also the bigger set is winning.

\DIFaddbegin \subsection{\DIFadd{Discount Monotonicity}}
\label{subsec:discount monotonicity}

\DIFaddend An axiom which is not met by all the discussed aggregation rules is
\emph{discount monotonicity}. Discount monotonicity states that if an already
selected project which is going to be funded receives a revised cost function
\DIFaddbegin \DIFadd{resulting in less budget needed for that particular project}\DIFaddend , then that project
should not be implemented to a lesser degree
\cite[p.~11]{azizParticipatoryBudgetingModels2020}. This is an important
property because if a rule were to fail discount monotonicity, the outcome may
be manipulated by increasing the cost of a project instead of trying to minimize
it. For the rules given in section~\ref{sec:approval-based budgeting}, the
satisfaction functions $sat_\#$ (see equation~\ref{eq:3}) and $sat_{0/1}$
(equation~\ref{eq:5}) and their combination with the three aggregation methods
(greedy, proportional greedy and maximum rule) satisfy discount monotonicity.
This is the case because decreasing a project's cost makes it more attractive
for selection, which is not the case when the satisfaction function $sat_\$ $
(equation~\ref{eq:4}) is used \DIFdelbegin \DIFdel{.
}\DIFdelend \DIFaddbegin \DIFadd{because with $sat_\$ $ a projects value is its
cost. Discounting a project under $sat_\$ $ therefore lessens its value.
}\DIFaddend

\DIFaddbegin \subsection{\DIFadd{Limit Monotonicity}}
\label{subsec:Limit monotonicity}

\DIFaddend \emph{Limit monotonicity} is similar to discount monotonicity in that the
relation of a project's cost to the budget limit is modified. Whereas discount
monotonicity changes the project's cost, limit monotonicity changes the total
available budget. It states that if the budget limit is increased and there
exists no project which might become affordable and give higher satisfaction
than the previous solution, then a project that was a winning project before
will still be one after the budget is increased. Not satisfying this axiom could
provoke discontent among the voters when they realize that their approved
project is not funded anymore because the total budget has increased, as this is
somewhat counterintuitive. Unfortunately, none of the discussed rules satisfy
limit monotonicity. A counterexample for the greedy and proportional greedy
rules is \DIFdelbegin \DIFdel{one }\DIFdelend \DIFaddbegin \DIFadd{given by \mbox{%DIFAUXCMD
\cite[p.~2185]{talmonFrameworkApprovalBasedBudgeting2019}
}\hspace{0pt}%DIFAUXCMD
}\DIFaddend where there are three projects $a,b,c$ and $a$ gives the biggest satisfaction.
Project $a$ is therefore selected first. For the case where the budget limit has
not yet been increased, project $b$ is selected second because project $c$ is
too expensive even though it would provide more satisfaction.  When the budget
limit is increased, project $c$ can now be funded instead of $b$ and will
provide a higher total satisfaction. Voters which have approved project $b$ will
thus lose some of their satisfaction. This example is also applicable to the
maximum rules because the maximum satisfaction before the budget is increased is
provided by $\{ a,b \}$. Because $c$ can be funded additionally to $a$ after
increasing the budget and provides a higher total satisfaction, the winning set
is $\{ a,c \}$.

These three examples provide a rudimentary introduction to comparing aggregation
rules by their fulfillment of axiomatic properties. The social choice theory
often uses axioms such as \emph{strategyproofness}, \emph{pareto efficiency} and
\emph{non-dictatorship} to classify voting schemes. These properties are
concerned with making sure that each voter votes truthfully, that a solution
cannot \DIFdelbegin \DIFdel{be bettered }\DIFdelend \DIFaddbegin \DIFadd{achieve a higher satisfaction }\DIFaddend without making someone worse off while
improving another voter\DIFaddbegin \DIFadd{'s satisfaction }\DIFaddend and that results cannot only mirror one
person's preferences, respectively.

\section{Conclusion}
\label{sec:conclusion}

We have \DIFdelbegin \DIFdel{looked at different possibilities for conducting the voting and winner
selection process }\DIFdelend \DIFaddbegin \DIFadd{ introduced different methods for preference elicitation and aggregating
a winning selection of projects }\DIFaddend for participatory budgeting. A budgeting
scenario in the mathematical sense has been described and methods for modeling
voter satisfaction are discussed. \DIFdelbegin \DIFdel{A }\DIFdelend \DIFaddbegin \DIFadd{Afterwards, a }\DIFaddend deeper view on approval-based
budgeting models has been given where the voters are assumed to have dichotomous
preferences. \DIFdelbegin \DIFdel{The
complexity }\DIFdelend \DIFaddbegin \DIFadd{In section~\ref{sec:approval-based budgeting} we summarize
complexity results }\DIFaddend of the different rules\DIFdelbegin \DIFdel{has been evaluated and contrasted }\DIFdelend \DIFaddbegin \DIFadd{. Section~\ref{sec:normative axioms}
introduces three axioms by which participatory budgeting methods can be compared
}\DIFaddend to each other \DIFdelbegin \DIFdel{. We have seen that aggregation methods cannot only be compared in terms of
complexity but also by using axioms that formulate desirable outcomes}\DIFdelend \DIFaddbegin \DIFadd{and which allow for these methods to be tested in scenarios such
as when a project gets a discount}\DIFaddend .

Future research might focus on not only incorporating monetary cost and
satisfaction into aggregating winning projects but also other factors such as
environmental costs, practicability of participatory budgeting methods as well
as scalability of these methods to a very high amount of projects and voters.
\DIFaddbegin

\DIFaddend Interesting further questions are posed by the possibility to combine projects
that are indivisible with projects that are divisible under one aggregation
rule, leading to a host of \emph{hybrid models}. Because a lot of the methods
that have been theorized by researchers have not yet been implemented in
practice, research on feasibility could lead to a better understanding of what
works and what does not.
\DIFaddbegin

\DIFaddend Another area of research could focus on allowing projects to be related to each
other and reflecting those inter-relations in the outcome while still
maintaining a grip on the explosion of possible solutions.
\DIFdelbegin \DIFdel{Exploring more axioms and rule configurations is important for achieving a
complete picture of the possibilities within the field of computational social
choice. }\DIFdelend \DIFaddbegin

\DIFaddend As a final point, research into user interface design during the voting phase
might uncover previously unknown impacts of ballot design on the resulting
selection of winning projects.

\printbibliography

\end{document}