# Designing Strategyproof Election Systems with Score Voting

Johanne Cohen
LISN-CNRS, Université Paris-Saclay, France
<EMAIL_ADDRESS>
&Daniel Cordeiro
University of São Paulo, Brazil
<EMAIL_ADDRESS>
&Valentin Dardilhac
Université Paris-Saclay, France
<EMAIL_ADDRESS>
&Victor Glaser
École normale supérieure de Lyon, France
<EMAIL_ADDRESS>
###### Abstract

We focus on the strategyproofness of voting systems where voters must choose a
number of options among several possibilities. These systems include those
that are used for Participatory Budgeting, where we organize an election to
determine the allocation of a community’s budget (city, region, etc.)
dedicated to the financing of projects.

We present a model for studying voting mechanisms and the Constrained Change
Property (CCP), which will be used to design voting mechanisms that are always
strategyproof. We also define a new notion of social choice function and use
it to design a new class of utilitarian voting mechanisms that we call score
voting. We prove that the mechanisms designed with core voting with a neutral
score function are equivalent to knapsack voting on the same instance and that
any score voting designed with a total score function is strategyproof if and
only if its score function satisfies CCP.

These results are combined to devise an algorithm that can find the closest
total score function that makes any given score voting to be strategyproof.

##  1 Introduction

Social choice theory is a branch of science that studies how individual
preferences can be aggregated in a collective choice [4]. Social choice theory
has been applied to study applications in several domains. In particular, it
has been used to study what is known in the literature as _Knapsack voting_ ,
adapted from Cabannes’ idea of Participatory Budgeting [5].

Knapsack Voting (KP) seeks to invite citizens to participate in the process of
deciding how public money is spent. This form of participatory democracy was
first employed by the city of Porto Alegre, Brazil, in 1989. Since then it has
been used by different cities around the world like Madrid, Seoul, Bogota, New
York, and Paris. For instance, in 2016 Paris applied KP to allow citizens to
vote on how to allocate a budget of 100 million Euros [6].

Citizens vote independently for a subset of projects considering multiple
criteria (cost of the project, location, beneficiaries, etc.). Their choices
are then used to reach a joint decision in a fair and principled way.

In this work, we are interested in studying the properties of voting
mechanisms—algorithms that select a solution by taking into account the
opinion of the voters—that make voting resilient to manipulation. We study the
concept of _strategyproofness_ (the equivalent for auctions being called
truthfulness) of those mechanisms, which is the idea that the best voting
strategy for a voter is to be sincere, i.e., the player has no incentive to
strategically change its preferred vote in order to increase its outcome.

Designing a strategyproof voting mechanism is hard due to several
impossibilities results resulting from the Gibbard-Satterthwaite theorem [10,
18] and its extensions. The main contributions of this work are the following.

The first contribution is a new model for voting mechanisms that allows the
study of voting mechanisms regardless of their type (utilitarian or fair). We
called this model the _common Choice Mechanism_ (CM). Using this model, we
describe conditions that make non-dictatorial mechanisms non-strategyproof and
show how the social choice functions respecting the “Constrained Change
Property” (CCP) can be used to design CMs that are strategyproof for the
unitary case.

The second contribution of this work is the notion of _score functions_. We
use this notion to design a new class of utilitarian voting mechanisms that we
call _score voting_. We show that the mechanisms designed with score voting
that have the “neutrality property” are equivalent to knapsack voting. We also
show that any score voting designed with a _total_ score function is
strategyproof if and only if its score function satisfies CCP. We present an
algorithm that use this result to find the closest total score function that
makes a score voting strategyproof.

The remaining of this document is organized as follows. Section 2 presents
works on computational social choice and Participatory Budgeting. In section 3
we present a model to study choice mechanisms (CMs) and the notations used in
this document; we also formally define the notion of strategyproofness.
Section 4 studies the strategyproofness of different mechanisms and shows how
the CCP property can be used to design CMs that are strategyproof. Section 5
studies several _score voting_ mechanisms, shows how they can be used to
design strategyproof mechanisms, and present an algorithm to compute the
closest strategyproof total score function. Finally, the appendix details all
the omitted proofs.

##  2 Related Work

Participatory budgeting (PB) [5, 6] has been applied by different
municipalities as a democratic tool to allow citizens to prioritize
investments on several projects given a limited budget. The idea was first
applied in 1989 in the city of Porto Alegre, Brazil, and has been used in
several cities, notably in Latin America and Europe [1].

Different electoral systems and their properties have been studied by
_Computational social choice_ [4], a branch of science that studies the
computational aspects of collective decision-making. It covers problems
regarding voting theory (including mechanisms design, the computational
complexity of choosing a winner, strategic voting), fairness in allocations,
coalition formation, etc.

In particular, there is a great deal of interest in studying the manipulation
of decisions by decision-makers. Voters can strategically change their true
preferences in order to obtain a better outcome. Decision-making mechanisms
that are immune to strategic voting are called _strategyproof_ (also called
truthful depending on the domain).

A common electoral system used in participatory budgeting is the $k$-approval
voting. Each voter chooses (“approves”) up to $k$ projects and the projects
with the highest number of approvals are funded (respecting the budget
constraints).

Goel et al. [11] introduced the _Knapsack Voting_ scheme. The idea comes from
the fact that applying PB is conceptually similar to solving the classical
Knapsack problem, with the set of chosen budget items fitting a limited budget
$B$ while maximizing societal value [7]. In this scheme, each citizen votes
for a subset of the objects such that the sum of the costs of the objects
satisfies the budget constraint. They showed that this schema is strategyproof
and welfare-maximizing when the outcome for the voter is given by the
$\ell^{1}$ distance from the outcome and its true preference and partially
strategyproof under additive concave utilities.

Aggregating budget division schemes that maximize the utilitarian social
welfare of voters have a tendency to overprioritize majority preferences,
resulting in unfairness problems [9]. The seminal work by Moulin [16] shows
that $\ell^{1}$ preferences are a particular case of single-peaked preferences
and presents a family of voting schemes that are both incentive compatible and
proportional by adding some fixed (“phantom”) ballots to the voter’s ballots
and choosing the median of the larger set. This result was later generalized
by several works [2, 3, 8, 9, 17].

Voting schemes that maximize the utilitarian social welfare are possible
because single-peaked preferences assume that there exists an ordering on the
alternatives. More general mechanisms may not be strategyproof due to an
important impossibility result was independently proved by Gibbard [10] and
Satterthwaite [18]. The Gibbard-Satterthwaite theorem states that every
resolute, non-imposed, and non-dictatorial social choice function for three or
more alternatives is susceptible to strategic manipulation [4].

##  3 Preliminaries for collective decision-making problems

The notations used in this paper are based on the standard notation given by
Brandt et al. [4].

A _common Choice Mechanism_ (CM) is a $6$-uplet
$(\mathcal{\mathcal{V}},\mathcal{O},({u}_{v})_{v\in\mathcal{\mathcal{V}}},Q,\mathcal{S},\mathcal{A}lgo)$
which is defined as follows. We consider a set of voters
$\mathcal{\mathcal{V}}=[n]$ (where $[i]=\\{1,\dots,i\\}$, for
$i\in\mathbb{N}$) and a finite set of $m$ alternatives (objects) $\mathcal{O}$
that answers the set of questions Q requested from the voters. The set of all
valid possible collective decisions is denoted by
$\mathcal{S}\subseteq\mathcal{O}$.

Each voter $v\in\mathcal{\mathcal{V}}$ has a private preference over all
solutions given by a utility function111The set of all subsets of $S$ is
denoted by $\mathcal{P}(S)$. ${u}_{v}:\mathcal{P}(\mathcal{O})\to\mathbb{R}$.
According to a set of questions _$Q$_ , that defines the format of the
ballots, each voter $v$ answers these questions via a ballot $b_{v}$. A
_declaration profile_ $\mathbf{B}=(b_{1},\dots,b_{n})$ consists of a ballot
$b_{v}$ for each voter $v$. In the remaining of the document, $(b_{v};b_{-v})$
is a shorthand for $(b_{1},\dots,b_{v},\dots,b_{n})$, used here to highlight
the ballot of voter $v$ against that of all other voters.

Voting can mean different things depending on the specified form of a ballot
and a collective decision. For example, the ballot can be a subset
$e\in\mathcal{P}(\mathcal{O})$, a linear ordering of the objects, or the value
function among all the objects. The _social choice function_ $\mathcal{A}lgo$,
aggregates a set of individual ballots $\mathbf{B}$ into a collective decision
and returns a _solution_ , which is a _winning set_ of objects
$\mathcal{A}lgo(\mathbf{B})$.

Our study focuses on the design of the social choice function that incentives
an individual voter to vote sincerely. We denote by _$b^{*}_{v}$_ the ballot
of the voter $v$ if she sincerely answers the questions based on her utility.

######  Definition 1.

We say that a CM is _strategyproof_ if: for all profile ballots $\mathbf{B}$,
for all voters $v\in\mathcal{\mathcal{V}}$, we have
${u}_{v}(\mathcal{A}lgo(b^{*}_{v};\mathbf{B}_{-v}))\geq{u}_{v}(\mathcal{A}lgo(b_{v};\mathbf{B}_{-v}))$.

Our work focuses on mechanisms designed to maximize social welfare assuming
voters have utilities over alternatives.

######  Definition 2.

If the ballot is a valuation of the objects, a _social welfare-maximizing
function (SWF)_ is an optimization function
$\mathcal{P}(\mathcal{O})\to\mathbb{R}$ that maximizes a social welfare.

In this work, we distinguish two forms of social welfare-maximizing functions:

  * •

a social welfare function denoted $f_{utilitarian}$ is _utilitarian_ if it
maximizes $\sum_{v\in\mathcal{\mathcal{V}}}\sum_{o\in s}b_{v}(o)$, $\forall
s\in\mathcal{S}$;

  * •

a social welfare function denoted $f_{fair}$, is _fair_ if maximizes
$\min_{v\in\mathcal{\mathcal{V}}}\sum_{o\in s}b_{v}(o),$ $\forall
s\in\mathcal{S}$.

An algorithm $\mathcal{A}lgo$ that finds the optimal solution of a utilitarian
(resp. fair) function is denoted $\mathcal{A}lgo_{utilitarian}$ (resp.
$\mathcal{A}lgo_{fair}$).

In order to study different types of ballots, we use a particular class of CMs
called _Simple CMs_ that takes into account different weights of objects and
uses the sincere ballot of the voter in its utility. _Simple CM_ is a
$5$-uplet
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo)$
defined as follows. The ballots are functions: $\mathcal{O}\to\mathbb{R}$.
Every object $o$ has also a weight denoted $w(o)$ (hence, the weight is a
function $w:\mathcal{O}\to\mathbb{R}$). Value $W$ is a weight constraint that
restricts valid solutions, so that
$\mathcal{S}=\\{e\in\mathcal{P}(\mathcal{O}):\sum_{o\in e}w(o)\leq W\\}$. The
utility depends on the values of the set in the sincere ballot:
${u}_{v}(e)=\sum_{o\in e}b^{*}_{v}(o)$.

Now we define the type of the Simple CM according to the type of ballot:

  * •

a simple CM is an _approval voting_ if the ballot $b_{v}$ is a a function
$b_{v}:\mathcal{O}\to\\{0,1\\}$. This ballot can also be defined as a vector
of $\\{0,1\\}^{|\mathcal{O}|}$;

  * •

a simple CM is a _ranking voting_ if the ballot $b_{v}$ of voter $v$ is a rank
of the objects, i.e. a bijection $b_{v}:\mathcal{O}\to\\{1,|\mathcal{O}|\\}$;

  * •

a simple CM is the _value function voting_ if the ballot is a valuation of the
objects of $\mathcal{O}$, i.e. a function $b_{v}:\mathcal{O}\to\mathbb{R}$.

Example of participatory budgeting problem: Given a set of projects
$\mathcal{O}$ (the alternatives), a set of voters $\mathcal{\mathcal{V}}$
needs to select a set of projects they have identified to be interested in.
Each project $o$ has a cost $w(o)$, and there is a fixed total budget of $W$.
The question $Q$ arises of which projects should be funded. Each voter $v$
votes for a subset $d_{v}\subseteq\mathcal{O}$, such that it satisfies the
budget constraint $W$ (i.e., $\sum_{o\in d_{v}}w(o)\leq W$). Since the ballot
is a subset $\mathcal{O}$, it is also possible to describe participatory
budgeting with a simple CM, which is
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{utilitarian})$.
The participatory budgeting problem has a utilitarian social welfare function
because the objective is to find the set of objects that maximize the number
of votes.

Finally, Knapsack voting is an approval voting
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{utilitarian})$
when all objects have the same weight and $\mathcal{A}lgo_{utilitarian}$
returns the optimal solution for the utilitarian social welfare function.

##  4 Properties on different votes

Before understanding the strategyproofness of CM, we focus on the optimization
problem of the social welfare function. The considered optimization problems
are formally related to the Knapsack problems. We focus on different types of
ballots, different social welfare-maximizing functions (utilitarian or fair),
and the weight of objects (unitary weight, i.e. all the objects have the same
weight $1$, or without no restriction of weight). For simplicity, we gather
all our results in Table 1 (all the proofs are in the appendix).
Unfortunately, most of the variants of Knapsack problems are NP-complete (see
[15]). To our knowledge, no work in the literature studies the knapsack
problem using the fair optimization function.

Optimization | Ballot
---|---
objective | approval voting | ranking voting | value function
utilitarian | P | P for the unitary case (Proposition 30 )
| (Proposition 34 and Proposition 42) | NP-complete (Proposition 33)
fair | NP-complete even for the unitary case.
| Proposition 31 | Proposition 32 | Proposition 43
Table 1: Complexity to compute the winning set.  Optimization | Ballot
---|---
objective | approval voting | ranking voting | value function
| strategyproof for the unitary case | Not-strategyproof even for the
| (Goel et al. [11]) | unitary case
utilitarian | not-strategyproof for the non-unitary case |  |
| Proposition 35 | Proposition 36 | Proposition 37
fair | not-strategyproof even for the unitary case
| Proposition 38 | Proposition 39 | Proposition 41
Table 2: Strategyproofness on the CM when the social choice function returns
the optimal solution of a social welfare-maximizing function.

Now, we study the strategyproofness and the complexity to compute the result
on some simple CMs. We study scores and types of algorithms (utilitarian or
fair).

We study the strategyproofness property on simple CM when its social choice
function returns the optimal solution of the social welfare-maximizing
function. The Gibbard-Satterthwaite theorem222Theorem 3 is a rephrasing of
this theorem using our notation. gives some impossibility results about
strategyproofness.

######  Theorem 3 ([10]).

Whenever the utility ${u}_{v}$ is represented by a ranking of the objects, one
of the following propositions is true:

  * •

The ballot only considers two possible outcomes (ex: a yes/no question);

  * •

The social choice function is dictatorial; a voter can choose the outcome;

  * •

The CM is not strategyproof.

This theorem is powerful because it can be used for many existing voting
mechanisms. Goel et al. shows a surprising result:

######  Theorem 4 ([11]).

Unitary approval voting is strategyproof.

We want to generalize Goel et al.’s result to other CM. Hence, we study the
strategyproofness property on simple CM when its social choice function
returns the optimal solution of the social welfare-maximizing function.
Unfortunately, we obtain only results of impossibilities (by giving some
counterexample or by applying the Gibbard-Satterthwaite theorem). For
simplicity, we gather all our results in Table 2.

The Gibbard-Satterthwaite theorem cannot be easily extended to more general
utilities. We use the common Choice Mechanism model to study the limitations
of strategyproofness. Let us now describe the tools that will be used for an
impossibility result on CM.

######  Definition 5.

Let
CM=$(\mathcal{\mathcal{V}},\mathcal{O},({u}_{v})_{v\in\mathcal{\mathcal{V}}},Q,\mathcal{S},\mathcal{A}lgo)$
be a common choice mechanism. A _feasible_ solution $s\in\mathcal{S}$ is
called _first-class_ set if for every $s^{*}\in\mathcal{S}$, there is a
permutation $\sigma_{s^{*}}$ such that
$\forall~{}v\in\mathcal{\mathcal{V}},{u}_{\sigma_{s^{*}}(v)}(s)\geq{u}_{v}(s^{*})$.

A common choice mechanism
CM=$(\mathcal{\mathcal{V}},\mathcal{O},({u}_{v})_{v\in\mathcal{\mathcal{V}}},Q,\mathcal{S},\mathcal{A}lgo)$
is called _first-class_ if it always chooses a first-class set whenever there
is one.

The notion of a first-class CM can be used to show a new impossibility result:

######  Theorem 6.

A first-class CM
($E,\mathcal{S},\mathcal{\mathcal{V}},\\{{u}_{v}\\}_{v\;\in\mathcal{\mathcal{V}}},Q,\mathcal{A}lgo$)
is not strategyproof if both those conditions hold:

  * •

$Q$ forces the type of the ballots so that the ballot of voter $v$ has to
contain the feasible solution $m_{v}=argmax\\{{u}_{v}(s):s\in\mathcal{S}\\}$
and the feasible solution
$m^{*}_{v}=argmax\\{{u}_{v}(s):s\in\mathcal{S}\backslash\\{m_{v}\\}\\}$. Plus,
given the two preferred feasible solutions of a voter $v$, $Q$ also forces the
type of the ballots so that the ballots contain their images given by the
utility function $u_{v}$, which must be distinct; and

  * •

the utilities can take at least $3$ distinct values (e.g., $0,1,2$, or a
ranking on at least $3$ objects, and only one is selected) independently for
each feasible solution.

###### Proof.

Lets take two voters $v_{1}$ and $v_{2}$ such that $m^{*}_{v_{2}}=m_{v_{1}}$
and $m^{*}_{v_{1}}=m_{v_{2}}$ and
${u}_{v_{1}}(m_{v_{1}})={u}_{v_{2}}(m_{v_{2}})$ and
${u}_{v_{2}}(m_{v_{1}})={u}_{v_{1}}(m_{v_{2}})\neq{u}_{v_{1}}(m_{v_{1}})$.

The only first-class sets are $m_{v_{1}}$ and $m_{v_{2}}$ (because one of the
voters of a first-class set must have a preference greater or equal than
${u}_{v_{1}}(m_{v_{1}})$ for this set, which is only the case for $m_{v_{1}}$
and $m_{v_{2}}$). Hence, if the ballots are sincere, the CM chooses either
$m_{v_{1}}$ or $m_{v_{2}}$ (lets say w.l.o.g. that it is $m_{v_{2}}$). If
$v_{1}$ lies on her ballot by telling that ${u}_{v_{1}}(m_{v_{2}})$ is lower
than the reality (it does not change the other values of the utility because
of their independence), then $m_{v_{2}}$ is not a first-class set anymore.
Thus, $m_{v_{1}}$ is chosen (being the only first-class set), and the utility
of $v_{1}$ increases. Hence, this CM is not strategyproof. ∎

Theorem 6 applies in different cases than Gibbard-Satterthwaite’s theorem
because the next proposition is an application of Theorem 6 (it is not the
case for Gibbard-Satterthwaite’s theorem).

######  Proposition 7.

There exists an approval voting
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{fair})$
with ${u}_{v}(e)=\sum_{o\in e\cap d^{*}_{v}}w(o)$ such that the social choice
function that returns the optimal solution is not strategyproof.

Now, we characterize a sufficient property on CMs to be strategyproof. From
now on, we only consider approval voting (the ballots can also be defined as a
vector of $\\{0,1\\}^{|\mathcal{O}|}$).

We find that another property seems essential to characterize
strategyproofness. From now on, any voting mechanism that we study will be
used on at least $3$ objects. We focus on a compelling property:

######  Definition 8 (Constrained Change Property (CCP)).

Let us consider the approval voting
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo)$.
The social choice function $\mathcal{A}lgo$ respects the Constrained Change
Property (CCP) if a voter $v$ switches from an object $\alpha$ to an object
$\beta$ in a ballot, the social choice function can either:

  * •

Eject $\alpha$ of the output solution and have it replaced by another object;

  * •

Get $\beta$ to be chosen and eject a previously chosen object (and only one);

  * •

Not change the output solution.

For the first condition, it is enough to consider an approval voting with a
single voter. The social choice functions should select only the objects in
her ballot: if the voter does not vote for the object $\alpha$, it must no
longer be in the output solution. For the last two conditions, modifying a
ballot by replacing an object with another does not have to alter the whole
solution because the projects have the same cost. Hence there should be a
relative symmetry between the objects.

This property on the social choice function implies the strategyproofness
(corresponding to the following theorem):

######  Theorem 9.

Let us consider an approval voting CM
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo)$,
in the unitary case. If the social choice function respects CCP, then the CM
is strategyproof.

###### Proof.

Let $v$ be a voter and $b_{v}^{*}$ her sincere ballot. Suppose that $v$ gives
a ballot $b_{v}$ that is not sincere, which is optimal to maximize her
utility. We prove that voting $b_{v}^{*}$ or $b_{v}$ would give the same
utility for voter $v$: _i. e_ ,
${u}_{v}(\mathcal{A}lgo(b_{v};\mathbf{B}_{-v}))={u}_{v}(\mathcal{A}lgo(b_{v}^{*};\mathbf{B}_{-v}))$
for all ballot profiles $\mathbf{B}$.

We prove the statement by induction on a parameter $|b_{v}\backslash
b_{v}^{*}|$, corresponding to the number of different objects between $b_{v}$
and $b_{v}^{*}$.

$|b_{v}\backslash b_{v}^{*}|=0$ means that $b_{v}=b_{v}^{*}$. So, the
strategyproof ballot is optimal, and the statement for $k=0$ is proved.
Suppose the statement holds when $|b_{v}\backslash b_{v}^{*}|\leq k$ for some
value of $k\geq 0$ (Assumption $R_{k}$).

Now, assume $|b_{v}\backslash b_{v}^{*}|=k+1$. Moreover, we consider that the
utility of $v$, having voted $b_{v}$ is than the one if she voted $b_{v}^{*}$,
because $b_{v}$ is optimal (if they are the same, just set $b_{v}=b_{v}^{*}$,
and the proof is over).

Lets take an object $\beta$ which is in $b_{v}^{*}$ and not in $b_{v}$ and
$\alpha$ which is in $b_{v}$ and not in $b_{v}^{*}$. It is possible because
$b_{v}^{*}\neq b_{v}$.

Let $b_{v}^{\prime}$ be $b_{v}$ by adding $\beta$ and removing $\alpha$ :
$b_{v}^{\prime}=b_{v}-\\{\alpha\\}\cup\\{\beta\\}$. We focus on
${u}_{v}(\mathcal{A}lgo(b_{v}^{\prime};\mathbf{B}_{-v}))$. Due to CCP
property, there are three possibilities:

  1. 1.

Assume that $\alpha$ gets ejected and an object $\gamma$ replaces it. In other
words, we have
$\mathcal{A}lgo(b_{v}^{\prime};\mathbf{B}_{-v})=\mathcal{A}lgo(b_{v};\mathbf{B}_{-v})-\\{\alpha\\}\cup\\{\gamma\\}$.
We have
${u}_{v}(\mathcal{A}lgo(b_{v},\mathbf{B}_{-v})\cup\\{\gamma\\}-\\{\alpha\\})\geq{u}_{v}(\mathcal{A}lgo(b_{v},\mathbf{B}_{-v})$,
because $b_{v}^{*}(\alpha)=0$ and $b_{v}^{*}(\gamma)\geq 0$. So,
${u}_{v}(\mathcal{A}lgo(b_{v}^{\prime},\mathbf{B}_{-v}))\geq{u}_{v}(\mathcal{A}lgo(b_{v},\mathbf{B}_{-v}))$.

  2. 2.

If $\beta$ is chosen and an object $\gamma$ is ejected, then
$\mathcal{A}lgo(b_{v}^{\prime};\mathbf{B}_{-v})=\mathcal{A}lgo(b_{v};\mathbf{B}_{-v})-\\{\gamma\\}\cup\\{\beta\\}$.
We have
${u}_{v}(\mathcal{A}lgo(b^{\prime}_{v},\mathbf{B}_{-v})\cup\\{\beta\\}-\\{\gamma\\})\geq{u}_{v}(\mathcal{A}lgo(b_{v},\mathbf{B}_{-v})$
because $b^{*}_{v}(\beta)=1$, and $b^{*}_{v}(\gamma)\leq 1$. Thus,
${u}_{v}(\mathcal{A}lgo(b_{v}^{\prime},\mathbf{B}_{-v}))\geq{u}_{v}(\mathcal{A}lgo(b_{v},\mathbf{B}_{-v}))$.

  3. 3.

Assume that the solution is not modified. Then,
$\mathcal{A}lgo(b_{v}^{\prime};\mathbf{B}_{-v})=\mathcal{A}lgo(b_{v};\mathbf{B}_{-v})$
and
${u}_{v}(\mathcal{A}lgo(b_{v}^{\prime},\mathbf{B}_{-v}))\geq{u}_{v}(\mathcal{A}lgo(b_{v},\mathbf{B}_{-v}))$.

In every case,
${u}_{v}(\mathcal{A}lgo(b_{v}^{\prime};\mathbf{B}_{-v}))\geq{u}_{v}(\mathcal{A}lgo(b_{v};\mathbf{B}_{-v}))\geq{u}_{v}(\mathcal{A}lgo(b_{v}^{*};\mathbf{B}_{-v}))$.
The difference between $b_{v}^{\prime}$ and the sincere ballot $b_{v}^{*}$,
$|b_{v}^{*}\backslash b_{v}^{\prime}|$, is $k$. By assumption $R_{k}$,
${u}_{v}(\mathcal{A}lgo(b_{v}^{*},\mathbf{B}_{-v}))={u}_{v}(\mathcal{A}lgo(b_{v}^{\prime};\mathbf{B}_{-v}))\geq{u}_{v}(\mathcal{A}lgo(b_{v};\mathbf{B}_{-v}))$.
Hence,
${u}_{v}(\mathcal{A}lgo(b_{v}^{*},\mathbf{B}_{-v}))={u}_{v}(\mathcal{A}lgo(b_{v};\mathbf{B}_{-v}))$
and $R_{k+1}$ is true.

With the induction,
${u}_{v}(\mathcal{A}lgo(p_{v};\mathbf{B}_{-v}))={u}_{v}(\mathcal{A}lgo(b_{v}^{*};\mathbf{B}_{-v}))$
for every optimal ballot $b_{v}$. ∎

In the next section, we present results regarding the CCP property. In order
to study the conditions on which the converse of Theorem 9 does hold, we
introduce the concept of _score functions_.

##  5 Score Voting

We design an extension of the simple CM
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{utilitarian})$
model for the case where objects have unitary weight, which is always
strategyproof. We introduce the notion of _score functions_ , which allows us
to introduce a correlation between objects: selecting an object will impact
the selection of another object. Each time an object is taken, it can favour
another object via a scoring process.

######  Definition 10 (Score functions).

A _score function_ on $m$ objects is defined by a couple ($M$,
$\mathcal{A}lgo$) with $m\times m$ real matrix $M$ and an associated social
choice function $\mathcal{A}lgo$. Given an integer $W$, and a ballot profile
$\mathbf{B}=(b_{1},\dots,b_{n})$, with $b_{1},\dots,b_{n}$ seen as a column
vector of $m$ elements, the social choice function $\mathcal{A}lgo$ taking
$\mathbf{B}$ as input returns the winning set of $W$ objects which maximizes
the inner product $M\cdot\mathbf{e}$ where the $i^{th}$ element of vector
$\mathbf{e}$ represents the number of times where $o_{i}$ is in $b_{1}$,
$\dots$, $b_{n}$. If such objects are not clearly defined, we use a tie break,
a strict order given by the social choice function $\mathcal{A}lgo$.

######  Definition 11 (Score Voting).

A simple CM
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo)$
in which the social choice function is a score function is called a _Score
Voting_.

Score Votings can be used to model utilitarian election systems where the
voter must choose several options among a set of possible choices. The model
is similar to Knapsack Voting [11], where every ballot that contains an object
$o$ gives one point to $o$, and the winner is the object with the most points.
The idea of a score function is to generalize the votes, allowing voters to
give any amount of points to any given object

Example: The city council would like to propose four projects to the
residents, such as “renovating a library” ($o_{1}$), “creating a bike path”
($o_{2}$), “funding a soccer team” ($o_{3}$), or “funding a basketball team”
($o_{4}$). However, it can only fund two of the four, and she wants to avoid
funding two sports-related projects. Thus, she can construct a score function
with $M=\begin{pmatrix}3&0&0&0\\\ 0&3&0&0\\\ 0&0&3&-2\\\ 0&0&-2&3\\\
\end{pmatrix}$.

The ballot distribution is the following: four voters want to fund only the
sports projects, two voters want to fund only the non-sports projects, and two
voters want to fund the “creating a bike path”, and “funding a basketball
team”. The following vector is summarized by $\begin{pmatrix}2\\\ 4\\\ 4\\\
6\\\ \end{pmatrix}$. Since $\begin{pmatrix}3&0&0&0\\\ 0&3&0&0\\\ 0&0&3&-2\\\
0&0&-2&3\\\ \end{pmatrix}\begin{pmatrix}2\\\ 4\\\ 4\\\ 6\\\
\end{pmatrix}=in\begin{pmatrix}6\\\ 12\\\ 4=(12-8)\\\ 10=(18-8)\\\
\end{pmatrix}$, the winner set is $\\{$“creating a bike path”, “funding a
basketball team” $\\}$ because the scores of these objects are the highest.

We will study in the following sections the strategyproofness of score voting
systems. We show that the strategyproofness of such systems can be
characterized by their score function. In the remaining text, we will extend
the use of the word strategyproof also to apply it to score functions that
guarantee score voting systems to be strategyproof. In other words, we say
that a score function is strategyproof if all score votings that use this
function are strategyproof.

###  5.1 Neutrality Property Over the Score Voting

In this section, we show how to use score voting to design an election system
where objects receive equal treatment. We use the standard matrix notations
where $M_{i,j}$ is the coordinate $(i,j)$ of matrix $M$, and $\mathbf{U}_{i}$
the coordinate $i$ of vector $\mathbf{U}$. The vector such that
$(\delta_{i})_{i}=1$ and $\forall j\neq i$, $(\delta_{i})_{j}=0$, is denoted
by $\mathbf{\delta_{i}}$.

We start defining the _neutrality property_ for election systems that treat
objects equally:

######  Definition 12.

A score function ($M$, $\mathcal{A}lgo$) is _neutral_ if score matrix $M$ has
the following form: $\forall k\in[m],i_{1}\neq\dots\neq i_{k}\in[m],$

  * •

$M(\mathbf{\delta_{i_{1}}}+\dots+\mathbf{\delta_{i_{k}}})_{i_{1}}=\dots=M(\mathbf{\delta_{i_{1}}}+\dots+\mathbf{\delta_{i_{k}}})_{i_{k}}$
;

  * •

For all other coordinates $j\neq i_{1},\dots,i_{k}$,
$M(\mathbf{\delta_{i_{1}}}+\dots+\mathbf{\delta_{i_{k}}})_{j}$ is strictly
less than $M(\mathbf{\delta_{i_{1}}}+\dots+\mathbf{\delta_{i_{k}}})_{i_{1}}$.

For example, knapsack voting is a score voting respecting neutral property.
Indeed, it is enough to notice that the identity matrix333The identity matrix
is a $m\times m$ square matrix with ones on the main diagonal and zeros
elsewhere. of size $m$

$\begin{pmatrix}1&0&\cdots&0\\\ 0&1&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&1\end{pmatrix}.$

with a tie break algorithm $\mathcal{A}lgo$ corresponds to their score
function.

We will now establish the set of score functions that are neutral. All of the
following proofs are in the appendix.

######  Proposition 13.

If ($M$, $\mathcal{A}lgo$) is a neutral score function, then
$M=D+\lambda_{1}A^{(1)}+\dots+\lambda_{m}A^{(m)}_{m}$ with
$\lambda_{1},\dots,\lambda_{m}\in\mathbb{R}$, $D$ is a positive constant
diagonal matrix and $\forall i,j,k\in[m],i\neq j$ $A^{(j)}$ is such that
$A^{(j)}_{k,j}=1$ and $A^{(j)}_{k,i}=0$.

We can now compute the winning set of all scoring votes according to knapsack
voting.

######  Theorem 14.

Every neutral score voting has the same winning set as knapsack voting.

###  5.2 Total score functions

The previous results show that neutrality is a hypothesis that is too
restrictive for election systems. If neutrality is satisfied, then there is
only one possible winning set: the one of knapsack voting.

We use score functions to study a class of mechanisms that are strategyproof
under a less restrictive hypothesis. For that, we introduce the notion of the
totality of score functions:

######  Definition 15.

A score function ($M$, $\mathcal{A}lgo$) is called _total_ if there exists a
ballot profile $\mathbf{B}=(b_{1},\dots,b_{n})$ such that
$\mathcal{A}lgo(b_{1}+\dots+b_{n})=s$, $\forall s\in\mathcal{S}$.

Observe that Knapsack voting is not equivalent to total score functions (see
Proposition 16).

######  Proposition 16.

There exists a score voting such that the associated score function ($M$,
$\mathcal{A}lgo$) is total and verifies CCP property. It does not have the
same winning set as knapsack voting.

###### Proof.

We can take as an example the matrix $\begin{pmatrix}1&0\\\ 0&3\end{pmatrix}$.
($M$, $\mathcal{A}lgo$) is total. Indeed, if $W=1$, to obtain the winning set
$\\{o_{i}\\}$, a ballot should be $\\{i\\}$. If $W=0$ or $W=2$, only one
winning set is possible. Moreover, ($M$, $\mathcal{A}lgo$) respects CCP since
$M$ is diagonal. The winning set on the ballots
$\\{o_{1}\\},\\{o_{1}\\},\\{o_{2}\\}$ is $\\{o_{1}\\}$ with knapsack voting
and $\\{o_{2}\\}$ with ($M$, $\mathcal{A}lgo$). ∎

From that, and from the fact that knapsack voting is total, we conclude that
the set of total score functions strictly contains and is greater the set of
neutral score functions. We now characterize the strategyproofness of total
score functions. To do so, we will define another set of constraints
_$\Delta$_ on the matrix of score functions. We will prove for the restricted
case of $m=3$ ($3$ objects) that strategyproofness is equal to CCP and to this
new set _$\Delta$_ restricted to total functions.

######  Definition 17.

We define $\Delta$ the following set of constraints on a score function ($M$,
$\mathcal{A}lgo$):

$\displaystyle\forall i,j,k,\ \ \ $ $\displaystyle M_{i,i}-M_{i,j}\geq
M_{k,i}-M_{k,j}$ $\displaystyle\forall i,j,j\neq i,\ \ \ $ $\displaystyle
M_{i,j}<M_{j,j}\ if\ i>j$ $\displaystyle M_{i,j}\leq M_{j,j}\ otherwise$

We denote by _$T_{\Delta}$_ the set of all total score functions that respect
$\Delta$.

######  Proposition 18.

The set $T_{\Delta}$ is not equal to the set of score functions that respect
$\Delta$.

###### Proof.

Let $M$ be $\begin{pmatrix}4&0&0\\\ 0&4&0\\\ 3&3&100\end{pmatrix}$. It
respects $\Delta$ but is not total (with $W=2$, $\\{o_{1},o_{2}\\}$ is not a
feasible winning set). ∎

To prove that CCP and strategyproofness are equivalent whenever $m=3$, we will
prove that:

  * •

any strategyproof total score function satisfies $\Delta$; and

  * •

for any total score function ($M$, $\mathcal{A}lgo$) that satisfies $\Delta$,
$\mathcal{A}lgo$ satisfies CCP.

We will first prove in Proposition 19 that if ($M$, $\mathcal{A}lgo$) is a
strategyproof total score function, the equations $M_{i,j}<M_{j,j}$ are
satisfied for all $i,j,j\neq i$. Then, we will use Lemma 20 to prove in
Proposition 21 that if ($M$, $\mathcal{A}lgo$) is a strategyproof total score
function, the equations $M_{j,k}-M_{j,i}\geq M_{k,k}-M_{k,i}$ are satisfied.

######  Proposition 19.

If ($M$, $\mathcal{A}lgo$) is a strategyproof total score function, then, for
all $i,j$, $j\neq i$:

  * •

if $i$ is chosen over $j$ in the tie break of $\mathcal{A}lgo$, then,
$M_{i,j}<M_{j,j}$;

  * •

otherwise, $M_{i,j}\leq M_{j,j}$.

###### Proof.

We build a score voting such that $W=1$ (the winning set is a singleton).

Let $i,j$ be two distinct integers in $[m]$ such that $M_{i,i}<M_{j,i}$ or
$M_{i,i}=M_{j,i}$ and $j>i$ in the tie break.

Let $\mathbf{\delta_{i}}$ be a vector whose coordinates are $0$ except the
$i$th coordinate which is $1$. By definition, the outcome (the winning set) on
ballot $\mathbf{\delta_{i}}$ is not $\\{o_{i}\\}$:
$\mathcal{A}lgo(M(\mathbf{\delta_{i}}))\neq\\{o_{i}\\}$.

Since ($M$, $\mathcal{A}lgo$) is a total score function, there exists a set of
ballots $\mathbf{B}=(b_{1},\dots,b_{n})$ such that the winning set
$\mathcal{A}lgo(M(\mathbf{B}))$ of the score voting on $\mathbf{B}$ is
$\\{o_{i}\\}$.

Several cases are possible. If $b_{1}=\dots=b_{n}=\mathbf{\delta_{i}}$, then
$\mathcal{A}lgo(M(b_{1}+\dots+b_{n}))=\mathcal{A}lgo(M(\mathbf{\delta_{i}}))$.
This leads to a contradiction with
$\mathcal{A}lgo(M(\mathbf{\delta_{i}}))\neq\\{o_{i}\\}$.

Assume now that there exists a voter $k$ such that
$b_{k}\neq\mathbf{\delta_{i}}$. If voter $k$ wants object $o_{i}$ and changes
her ballot to $\mathbf{\delta_{i}}$, two cases are possible:

  1. 1.

The winning set is $\\{o_{i}\\}$. The new set of ballots is
$\mathbf{B}^{\prime}=(b_{1},\dots,b_{k-1},\mathbf{\delta_{i}},\dots,b_{n})$.
In this case, another voter $k^{\prime}$ such that
$b_{k^{\prime}}\neq\mathbf{\delta_{i}}$ on the set $\mathbf{B}^{\prime}$
changes her ballot, and the process repeats. This process can be repeated at
most $n$ times, until the set of ballot becomes $\mathbf{B}^{\prime\prime}$
with $b_{1}=\dots=b_{n}=\mathbf{\delta_{i}}$, since the winning set on
$\mathbf{B}^{\prime\prime}$ is not $\\{o_{i}\\}$. Thus, after some steps, the
other case must happen.

  2. 2.

The winning set is not $\\{o_{i}\\}$. Thus voter $k$ should vote $b_{k}$. That
shows that $M$ is not strategyproof.

Hence, $M$ is either not total or not strategyproof. That shows that the
contraposition of the proposition is true. ∎

The next lemma highlights the strength of total score functions. We show that
given objects $x,y,z$ there exists a set of ballots such that $z$ gets the
best score out of all of the winning sets, and $y$ gets a higher score than
$x$.

We use this result to prove propositions 21 and 26 by contraposition.

######  Lemma 20.

If ($M$, $\mathcal{A}lgo$) is a total score function with a matrix of size at
least $3\times 3$ and $x,y,z$ are three objects, then there exists a set of
ballot
$\mathbf{B}=k_{1}\delta_{1}+\dots+k_{x}\delta_{x}+k_{y}\delta_{y}+k_{z}\delta_{z}+\dots+k_{m}\delta_{m}$
such that $M(\mathbf{B})=\begin{pmatrix}t_{1}\\\ \dots\\\ t_{x}\\\ t_{y}\\\
t_{z}\\\ \dots\end{pmatrix}$ with $t_{z}>t_{y}>t_{x}$, $t_{z}>t_{i}$ for every
other object $i$ and $k_{1},k_{2},k_{3},\dots\neq 0$.

######  Proposition 21.

For the total score functions, respecting CCP property implies respecting the
set of constraints $\Delta$.

######  Proposition 22.

For the total score functions, with $3$ objects, respecting the set of
equations $\Delta$ implies respecting property $CCP$.

The results show that for total score functions, the set of functions that
respect CCP is included in the set of those that respect $\Delta$ and that
they are equal whenever $m=3$.

Also, we can state the following important result regarding strategyproofness:

######  Proposition 23.

Strategyproof total score functions respect the set of constraints $\Delta$.

Combining this proposition, Theorem 9 and Proposition 21, we can show that
using a total score function with $m=3$, respecting CCP or being strategyproof
are equivalent properties. Moreover, they show that voting mechanisms designed
with a total score function respect the set of constraints $\Delta$ if and
only if they are strategyproof.

Unfortunately, this result cannot be extended for $m>3$ objects.

######  Proposition 24.

With strictly more than $3$ objects, there exist some score functions that
respect the set of constraints $\Delta$ and are not strategyproof.

###  5.3 Total score functions with m¿3

In the previous section, we have defined the set of constraints $\Delta$ which
helped us prove that CCP and strategyproofness are equivalent for total score
functions whenever $m=3$.

When $m>3$, the set of constraints $\Delta$ does not hold, even though the set
$T_{\Delta}$ of total score functions that respect $\Delta$ is larger than the
set of total score functions that are strategyproof. We study additional
constraints for $\Delta$ that allow us to show the strategyproofness of some
score voting systems with $m>3$. We denote this extended set of restrictions
_$\Delta^{+}$_.

######  Definition 25.

Given a score function ($M$, $\mathcal{A}lgo$), we define $\Delta^{+}$ is the
following set of constraints that contains $\Delta$ and $\forall
a,b,c,d\in\mathcal{O},M_{c,a}-M_{c,b}=M_{d,a}-M_{d,b}$. The set of total score
functions that respect $\Delta^{+}$ is called _$T_{\Delta}^{+}$._

######  Proposition 26.

If $m>3$, every strategyproof total score function satisfies $\Delta^{+}$.

######  Proposition 27.

If $m>3$, every total score function that satisfies $\Delta^{+}$ satisfies
CCP.

From the result when $m=3$, and $m>3$:

######  Theorem 28.

A total score function is strategyproof if and only if it satisfies CCP.

###  5.4 Finding the closest strategyproof total score function

The set of total score functions $T_{\Delta}^{+}$ can be used to devise an
algorithm capable of computing the closest (with respect to Frobenius
norm444$\|A\|_{\text{F}}=\sqrt{\sum_{i,j=1}^{n}|a_{ij}|^{2}}=\sqrt{\operatorname{Tr}\left(A^{*}A\right)}$
[12] on matrix) strategyproof total score function to another given score
function, if it exists. Since $T_{\Delta}^{+}$ is a convex polyhedron,
quadratic optimization helps us to project the score function on
$T_{\Delta}^{+}$.

An issue is that some of the inequations of $\Delta$ are strict, but the
projection is done on the closed set $\overline{T_{\Delta}^{+}}$. This leads
to two possibilities:

  1. 1.

the projection gives a strategyproof total score function;

  2. 2.

the notion of the closest strategyproof total score function does not exist,
and the projection gives a non-strategyproof score function.

In the first case, the projection is the result of the algorithm. We now show
a way to handle the second case.

We project a matrix $M$ on $\overline{T_{\Delta}^{+}}$, which gives a matrix
$M^{\prime}$. If $M^{\prime}$ is not strategyproof, we cover the sphere
centered in $M^{\prime}$, of radius $\delta$ (a small constant) with a set of
points, so that every point on the sphere is at most at a distance $\epsilon$
to a point of the cover. To cover such a sphere, in dimension $n^{2}$, we
consider the points
$(k_{1}\epsilon,k_{2}\epsilon,\dots,k_{n^{2}-1}\epsilon,\sqrt{1-k_{1}^{2}\epsilon^{2}-\dots-
k_{n^{2}-1}^{2}\epsilon^{2}})$ $\forall
k_{1},\dots,k_{n^{2}-1}\in[-\frac{1}{\epsilon},\frac{1}{\epsilon}]$ whenever
the square root is defined. With this cover, when $\epsilon$ is close to $0$,
the distance between a point of the cover, and a point of the sphere is at
most $n^{2}*\sqrt{2\epsilon}$.

Using the inequations of $\Delta^{+}$, we can check on every point of the
cover whether they are strategyproof or not and output a “close” strategyproof
matrix. This procedure gives an algorithm that outputs the closest
strategyproof total score function if it exists. It outputs a strategyproof
total score function at distance $\delta$ from the optimal if the closest
matrix does not exist.

Given a score function ($M$, $\mathcal{A}lgo$), the algorithm can be described
as follows:

  1. 1.

Solve the quadratic optimization problem to project $M$ on $\Delta^{+}$;

  2. 2.

Verify if the projection ($M^{\prime}$, $\mathcal{A}lgo$) respects the
constraints of $\Delta^{+}$ and if so, return ($M^{\prime}$,
$\mathcal{A}lgo$);

  3. 3.

Otherwise, find and return a score function that respects the constraints of
$\Delta^{+}$ on the sphere centered in $M^{\prime}$, of radius $\epsilon$.

######  Theorem 29.

Given a score function ($M$, $\mathcal{A}lgo$), there exists an algorithm that
returns the closest strategyproof total score function.

##  6 Conclusion and perspectives

In this paper, we studied the design of strategyproof election systems. We
focused on voting systems like the ones used in Participatory Budgeting, where
one must choose a fixed number of options among several possibilities (e.g.,
projects to be funded restricted to a given budget).

Using a new model for describing choice mechanisms, we detailed the conditions
that make non-dictatorial mechanisms non-strategyproof. We also presented the
Constrained Change Property (CCP), a powerful tool to characterize the
strategyproofness of voting mechanisms. Using CCP, we showed how to design
choice mechanisms that are strategyproof for the unitary case.

We proposed the notion of score functions and a new class of utilitarian
voting mechanisms called Score Voting. Score functions turned out to be a
flexible tool to characterize the strategyproofness of voting mechanisms. We
proved that the mechanisms designed with score voting with a neutral score
function are equivalent to knapsack voting on the same instance. Also, if the
score function satisfies CCP, then, the score voting is strategyproof. These
results were combined to devise an algorithm that can find the closest total
score function that makes any given score voting to be strategyproof.

In future works, we intend to further improve the notion of score voting (and
its score functions) to better characterize the relation of the CCP property
and strategyproofness. We are also interested in the problem of quantifying
the strategyproofness of a vote and in creating approximation algorithms for
the problem.

## References

  * [1] Haris Aziz and Nisarg Shah.  Participatory Budgeting: Models and Approaches, pages 215–236.  Springer, Cham, 2021.  doi:10.1007/978-3-030-54936-7_10.
  * [2] Salvador Barberà and Matthew Jackson.  A characterization of strategy-proof social choice functions for economies with pure public goods.  Social Choice and Welfare, 11(3):241–252, 1994.  doi:10.1007/BF00193809.
  * [3] Kim C. Border and James S. Jordan.  Straightforward elections, unanimity and phantom voters.  The Review of Economic Studies, 50(1):153–170, 1983.  doi:10.2307/2296962.
  * [4] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia.  Handbook of computational social choice.  Cambridge University Press, 2016.  doi:10.1017/CBO9781107446984.
  * [5] Yves Cabannes.  Participatory budgeting: a significant contribution to participatory democracy.  Environment and urbanization, 16(1):27–46, 2004.  doi:10.1177/095624780401600104.
  * [6] Yves Cabannes.  Another City is Possible with Participatory Budgeting.  University of Chicago Press, 2 edition, December 2023.
  * [7] Yiling Chen, Arpita Ghosh, Michael Kearns, Tim Roughgarden, and Jennifer Wortman Vaughan.  Mathematical foundations for social computing.  Communications of the ACM, 59(12):102–108, 2016.  doi:10.1145/2960403.
  * [8] Conal Duddy.  Fair sharing under dichotomous preferences.  Mathematical Social Sciences, 73:1–5, 2015.  doi:10.1016/j.mathsocsci.2014.10.005.
  * [9] Rupert Freeman, David M. Pennock, Dominik Peters, and Jennifer Wortman Vaughan.  Truthful aggregation of budget proposals.  Journal of Economic Theory, 193, 2021.  doi:10.1016/j.jet.2021.105234.
  * [10] Allan Gibbard.  Manipulation of voting schemes: a general result.  Econometrica: journal of the Econometric Society, pages 587–601, 1973.  doi:10.2307/1914083.
  * [11] Ashish Goel, Anilesh K. Krishnaswamy, Sukolsak Sakshuwong, and Tanja Aitamurto.  Knapsack voting for participatory budgeting.  ACM Transactions on Economics and Computation (TEAC), 7(2):1–27, 2019.
  * [12] Gene H. Golub and Charles F. Van Loan.  Matrix computations.  JHU press, 2013.
  * [13] David S. Johnson and Michael R. Garey.  Computers and intractability: A guide to the theory of NP-completeness.  WH Freeman, 1979.
  * [14] Richard M. Karp.  Reducibility among Combinatorial Problems, pages 85–103.  Springer, Boston, MA, 1972.  doi:10.1007/978-1-4684-2001-2_9.
  * [15] Hans Kellerer, Ulrich Pferschy, and David Pisinger.  Knapsack problems.  Springer, 2004.  doi:10.1007/978-3-540-24777-7.
  * [16] Hervé Moulin.  On strategy-proofness and single peakedness.  Public Choice, 35(4):437–455, 1980.  doi:10.1007/BF00128122.
  * [17] Hans Peters, Hans van der Stel, and Ton Storcken.  Pareto optimality, anonymity, and strategy-proofness in location problems.  International Journal of Game Theory, 21(3):221–235, 1992.  doi:10.1007/BF01258276.
  * [18] Mark Allen Satterthwaite.  Strategy-proofness and arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions.  Journal of economic theory, 10(2):187–217, 1975.  doi:10.1016/0022-0531(75)90050-2.

##  Appendix A Appendix: omitted proofs and examples

###  A.1 Proofs of Section 4

######  Proposition 30.

Given a simple CM
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{utilitarian})$,
a polynomial time algorithm can compute the winning set of objects in the
unitary case.

###### Proof.

This problem can be seen as the problem of the knapsack: the objects are the
same size, and the value of an object $o$ is equal to
$\sum_{v\in\mathcal{O}}b_{v}(o)$. In this context, the problem of the knapsack
can be solved with a greedy algorithm. ∎

The NP-completeness proofs are based on the two NP-complete problems:

######  Definition.

Problem $Knapsack(\mathcal{O},w,u,W,T)$
Input: A set $\mathcal{O}$ of objects with a value function
$u:\mathcal{O}\to\mathbb{N}^{+}$ and with a weight function
$w:\mathcal{O}\to\mathbb{N}^{+}$, a capacity $W$ of the knapsack, an integer
$T$.
Question: Does there exist a set S such that $\sum_{o\in S}u(S)\geq T$ and
$\displaystyle\sum_{o\in S}w(o)\leq W$?

######  Definition.

Problem Vertex Cover $VC(G,k)$
Input: A graph $G=(V,E)$ where $V$ is the vertex set and $E$ is an edge set, a
positive integer $K\leq|V|$.
Question: Is there a vertex cover of size $k$ or less for $G$ (a subset $S$ of
$V$ of size at most $K$ such that for every $\\{u,v\\}\in E$, $u\in S$ or
$v\in S$)

As shown by Karp [14], problems Knapsack and Vertex Cover are NP-complete.

######  Proposition 31.

The following problem called $BvMm_{1}$:

Input: A set of voters $\mathcal{\mathcal{V}}$, a set of objects
$\mathcal{O}$, ballots: $\mathcal{O}\to\\{0,1\\}$ with $T$ images of value
$1$.

Question: Does there exist a set $S$ of $\mathcal{O}$ such that
$min\\{{u}_{v}(S)\mid v\in\mathcal{\mathcal{V}}\\}\geq 1$ and $|S|\leq W$?

is NP-complete.

###### Proof.

It is easy to see that $BvMm_{1}$ is in NP because a nondeterministic
algorithm only needs to guess a subset $S$ of objects and check in polynomial
time whether $min\\{{u}_{v}(S)\mid v\in\mathcal{\mathcal{V}}\\}\geq 1$ and
$|S|\leq W$.

We transform an instance of Vertex Cover into an instance of Problem
$BvMm_{1}$. Let $G=(Vertices,Edges)$ and $k$ be an instance of Vertex Cover.
We must construct an instance of Problem $BvMm_{1}$.

The set $\mathcal{O}$ of objects is the set of vertices $Vertices$ and $k-2$
distinct new objects for every edge $e$ in $Edges$. We call $\mathbf{e}_{s}$
this set of the new objects for edge $e$. Every object $o$ has its weight
$w(o)$ equal to $1$. Finally, we set $k$ to $W$. For every edge $e=(a,b)\in
Edges$, we create a voter $v_{e}$ which votes for $a,b$, and all objects in
$\mathbf{e}_{s}$: $b_{v_{e}}=\\{a,b\\}\cup\mathbf{e}_{s}$.

This construction can be built in polynomial time.

Assume that there is a solution $S$ for the instance built of $BvMm_{1}$.

We assume that $S$ only contains objects corresponding to a vertex. If it is
not the case, we can modify $S$ as follows. If $S$ contains an object $o$ of
$\mathbf{e}_{s}$ for some $e=(a,b)$, we build a new set $S^{\prime}$ such that
$S^{\prime}=S-\\{object\\}\cup\\{a\\}$. Observe that
${u}_{v_{e^{\prime}}}(S^{\prime})={u}_{v_{e^{\prime}}}(S^{\prime})$ for all
$e^{\prime}\in Edges$ and $min\\{{u}_{v}(S^{\prime})\mid
v\in\mathcal{\mathcal{V}}\\}\geq 1$. So $S^{\prime}$ is also a solution for an
instance built of $BvMm_{1}$.

Since $|S|\leq W$, at most $W(=k)$ objects are chosen. Also, since for every
voter $v_{e}$, ${u}_{v_{e}}(S)\geq 1$, at least one extremity of edge $e$ is
in $S$. Thus, $S$ is also a vertex cover of $G$.

Conversely, assume that graph $G$ admits a vertex cover $S$ of size at most
$k$. We prove that $S$ is a solution for the instance of $BvMm_{1}$. Since $S$
is a vertex cover, at most, one extremity of each edge is in $S$, then
${u}_{v_{e}}(S)\geq 1$ for all $v_{e}\in\mathcal{\mathcal{V}}$. Thus $S$ is a
solution of our instance of $BvMm_{1}$. This proposition holds. ∎

######  Proposition 32.

The following problem MaxMinRankingBallot
Input: A set of voters $\mathcal{\mathcal{V}}$, a set of objects
$\mathcal{O}$, ballots which are bijections: $\mathcal{O}\to[m]$ , a positive
integer $T$.
Question: Does there exist a subset $S$ of $\mathcal{O}$ such that
$\min\\{{u}_{v}(S):v\in\mathcal{\mathcal{V}}\\}\geq T$ and $|S|\leq W$
is NP-complete.

###### Proof.

It is easy to see that MaxMinRankingBallot is in NP because a nondeterministic
algorithm only needs to guess a subset $S$ of objects and check in polynomial
time whether $\max\min\\{{u}_{v}(S):v\in\mathcal{\mathcal{V}}\\}\geq T$ and
$|S|\leq W$.

Recall that Problem $BvMm_{1}$ is NP-complete due to Proposition 31.

Let us take an instance $S$ of $BvMm_{1}$ and create an instance that for
every ballot, has $W+1$ times this ballot (in the end, we get $W+1$ times the
ballots of the first instance). We get an instance $S^{*}$ which has the same
solution as the one of $S$ (By multiplying (resp dividing) the value of a
solution of $S$ (resp $S^{*}$), we get a solution of the other instance. This
transforms an optimal solution of one into an optimal solution of the other).
Now, let us create an instance $S^{**}$ of MaxMinRankingBallot. The objects
and maximum weight $W$ are the same as those of $S^{*}$. For every voter
$v_{i}$ of $S^{*}$, we create two voters $v_{i,1}$ and $v_{i,2}$. Lets take an
order on the $W$ objects $v_{i}$ votes for: $(o_{1},\dots,o_{W})$.
$v_{i,1}(o_{i})=i$, $v_{i,2}(o_{i})=W+1-i$, they give value $0$ to the other
objects. $v_{i}(o)=v_{i,1}(o)+v_{i,2}(o)$, hence, the optimal solutions of $S$
and $S^{**}$ are the same. This transformation is clearly polynomial, so
MaxMinRankingBallot is NP-complete. ∎

######  Proposition 33.

The following problem
Input: A simple CM
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{utilitarian})$,
the ballot is a valuation of the objects of $\mathcal{O}$ (a function
$b_{v}:\mathcal{O}\to\mathbb{R}$).

Question: Does there exist a subset $S$ of $\mathcal{O}$ such that
$\displaystyle\sum_{v\in\mathcal{\mathcal{V}}}{u}_{v}(S)\geq T$ and such that
and $|S|\leq W$

is NP-complete.

###### Proof.

This problem is clearly in NP. Any instance of a knapsack problem is an
instance of this Problem considering a single voter. The desired result holds.
∎

######  Proposition 34.

Given a simple CM
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{utilitarian})$
where the ballot of each voter is defined as a subset of $\mathcal{O}$
(approval voting), a polynomial time algorithm can compute a set $S$ of
$\mathcal{O}$ such that
$max\displaystyle\sum_{v\in\mathcal{\mathcal{V}}}{u}_{v}(S)\geq T$ and such
that $\displaystyle\sum_{o\in S}w(o)\leq W$.

###### Proof.

Let us first give the idea of the algorithm. The Knapsack algorithm (dynamic
programming) inspires our algorithm. Using the terminology, we compute the
minimal capacity of a knapsack that can contain a subset $S$ of objects that
maximizes the function ${u}$.

The first step is to sum up all the values given to the object to calculate
the value
$\mu=\max_{o\in\mathcal{O}}\sum_{v\in\mathcal{\mathcal{V}}}{u}_{v}(o)$. Then,
the algorithm proceeds in a dynamic way. We create a dynamic vector
$\mathbf{dynamic\\_weight}$ to have more entries than the values of all
possible solutions. This vector has $\mu*m$ elements.

We initialize this vector with $0$ on the first entry $0$ and $\infty$
everywhere less. The value of an entry $\ell$ represents the minimum total
weight required to get, with a set $S$, a score
$\sum_{v\in\mathcal{\mathcal{V}}}{u}_{v}(S)$ of $\ell$.

We then fill this vector in a dynamic way, with a loop on the objects (at each
step of this loop, we update the vector).

Data: A set of objects $\mathcal{O}$, a set of voters $\mathcal{\mathcal{V}}$
with ballots: $\mathcal{O}\times\mathcal{\mathcal{V}}\to\\{0,1\\}$, a maximum
weight $W$, the ballot being a approval voting.

Result: A set S that maximizes
$max\displaystyle\sum_{v\in\mathcal{\mathcal{V}}}{u}_{v}(S)$ and such that
$\displaystyle\sum_{o\in S}w_{o}\leq W$.

for  _every object $o_{i}$_ do

$values[i]\leftarrow\sum_{v\in\mathcal{\mathcal{V}}}{u}_{v}(o_{i})$ ;

$\mu\leftarrow max(\\{values[i]:o_{i}\in\mathcal{O}\\})$ ;

$weight_{max}\leftarrow max(\\{w(o_{i}):o_{i}\in\mathcal{O}\\})$ ;

$\mathbf{dynamic\\_weight}\leftarrow\\{0,weight_{max}*m+1,\dots,weight_{max}*m+1\\}$
a list of length $\mu*m$ ;

$dynamic\\_outcome\leftarrow\\{\\{\\},...,\\{\\}\\}$ a list of length $\mu*m$
;

for  _$i$ varying from $1$ to m_ do

for  _$k$ varying from $\mu*m$ to $1$ decreasingly_ do

$j\leftarrow k-values[i]$;

if  _$j <0$_ then

break ;

else

if  _$\mathbf{dynamic\\_weight}[j]+w(o_{i}) <\mathbf{dynamic\\_weight}[k]$ and
$\mathbf{dynamic\\_weight}[j]+w(o_{i})<W$_ then

$\mathbf{dynamic\\_weight}[k]\leftarrow\mathbf{dynamic\\_weight}[j]+w(o_{i})$;

$\mathbf{dynamic\\_outcome}[k]\leftarrow\mathbf{dynamic\\_outcome}[j]+\\{o_{i}\\}$;

return The highest entry $k$ of $\mathbf{dynamic\\_outcome}$ such that
$\mathbf{dynamic\\_weight}[k]$ is different to $weight_{max}*m+1$;

Algorithm 1 Algorithm for the multiplayer knapsack voting with raking approval
ballots.

Let us prove Algorithm 1.

Correctness: In the double ‘for’ loop, an invariant is: At the $i$th step, for
every $\ell$, $\mathbf{dynamic\\_weight}[\ell]$ contains the least weight
necessary to get value $\ell$ only using the $i$-th first objects (or
$weight_{max}*m+1$).
Indeed, when $\mathbf{dynamic\\_weight}$ is created, it is true. At every step
of the loop on $i$, every possible value is updated according to the object
$i$: if using this object always gives a higher value, the algorithm looks at
the next value, and using the recurrence, the property is still verified. If
using this object requires having a certain value $j$ from another item to
reach the target value, then the weight of $\mathbf{dynamic\\_weight}[value]$
is updated based on which one is the lowest (using object $i$, or not).

$weight_{max}*m+1$ is not a reachable weight, and if the value is different
than $weight_{max}*m+1$ in $\mathbf{dynamic\\_weight}$ at the end of the
loops, then it is an attainable value (based on the invariant). Hence, the
highest value, with a weight different than $weight_{max}*m+1$ in
$\mathbf{dynamic\\_weight}$ is the highest value attainable. The sets inside
the $\mathbf{dynamic\\_outcome}$ are modified when necessary so that the
scores of these sets are equal to those of the entry. Hence, the set in the
highest entry attainable is optimal.

Complexity: The complexity of the first loop is $O(|\mathcal{O}|)$. The
complexity of the combination of two for loops is $O(|\mathcal{O}|^{2}*\mu)$.
The complexity of searching the minimum in the table is
$O(|\mathcal{O}|*\mu)$. Thus, the complexity of the algorithm is
$O(|\mathcal{O}|^{2}*\mu)=O(|\mathcal{O}|^{2}*|\mathcal{\mathcal{V}}|)$ ∎

####  A.1.1 About strategyproofness

######  Proposition 35.

Considering the approval voting
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{fair})$
when all objects have the same weight, the social choice function that returns
the optimal solution is not strategyproof.

###### Proof.

Let us consider an instance with $W=60$, $6$ voters and $9$ objects
$a,b,c,d,e,f,g$. $w(a)=w(b)=w(f)=5$, $w(c)=10$, $w(d)=20$, $w(e)=15$,
$w(g)=40$. We define the preference ranking as follows using approval voting:

  * •

$a,e,g$ for voter $v_{1}$;

  * •

$d,g$ for voter $v_{2}$;

  * •

$a,e,g$ for voter $v_{3}$;

  * •

$d,g$ for voter $v_{4}$;

  * •

$b,c,f,g$ for voter $v_{5}$;

  * •

$a,e,g$ for voter $v_{6}$.

Let us consider the instance in which all voters vote sincerely:

|  $a$ |  $b$ |  $c$ |  $d$ |  $e$ |  $f$ |  $g$
---|---|---|---|---|---|---|---
$v_{1}$ |  $1$ |  $0$ |  $0$ |  $0$ |  $1$ |  $0$ |  $1$
$v_{2}$ |  $0$ |  $0$ |  $0$ |  $1$ |  $0$ |  $0$ |  $1$
$v_{3}$ |  $1$ |  $0$ |  $0$ |  $0$ |  $1$ |  $0$ |  $1$
$v_{4}$ |  $0$ |  $0$ |  $0$ |  $1$ |  $0$ |  $0$ |  $1$
$v_{5}$ |  $0$ |  $1$ |  $1$ |  $0$ |  $0$ |  $1$ |  $1$
$v_{6}$ |  $1$ |  $0$ |  $0$ |  $0$ |  $1$ |  $0$ |  $1$
total |  $3$ |  $1$ |  $1$ |  $2$ |  $3$ |  $1$ |  $6$

The set $\\{a,e,g\\}$ is the best one and is selected.

So the utility of each voter are: ${u}_{1}(\\{a,c,h\\})=3$,
${u}_{2}(\\{a,c,h\\})=1$, ${u}_{3}(\\{a,c,h\\})=3$, ${u}_{4}(\\{a,c,h\\})=1$,
${u}_{5}(\\{a,c,h\\})=1$, ${u}_{6}(\\{a,c,h\\})=3$.

Assume voter $5$ changes her vote to $\textbf{a},b,c,\textbf{d,e},f$. Now the
scores change and are:

|  $a$ |  $b$ |  $c$ |  $d$ |  $e$ |  $f$ |  $g$
---|---|---|---|---|---|---|---
$v_{1}$ |  $1$ |  $0$ |  $0$ |  $0$ |  $1$ |  $0$ |  $1$
$v_{2}$ |  $0$ |  $0$ |  $0$ |  $1$ |  $0$ |  $0$ |  $1$
$v_{3}$ |  $1$ |  $0$ |  $0$ |  $0$ |  $1$ |  $0$ |  $1$
$v_{4}$ |  $0$ |  $0$ |  $0$ |  $1$ |  $0$ |  $0$ |  $1$
$v_{5}$ |  1 |  $1$ |  $1$ |  1 |  1 |  $1$ |  0
$v_{6}$ |  $1$ |  $0$ |  $0$ |  $0$ |  $1$ |  $0$ |  $1$
total |  4 |  $1$ |  $1$ |  3 |  4 |  $1$ |  5

The set $\\{a,b,c,d,e,f\\}$ is the best one and is selected.

So the utility of each voter are: ${u}_{1}(\\{a,c,h\\})=2$,
${u}_{2}(\\{a,c,h\\})=1$, ${u}_{3}(\\{a,c,h\\})=2$, ${u}_{4}(\\{a,c,h\\})=1$,
${u}_{5}(\\{a,c,h\\})=3$, ${u}_{6}(\\{a,c,h\\})=2$.

The utility of $v_{5}$ increases. Hence, she has incentives to give a non-
sincere vote. Thus, this mechanism is not strategyproof.∎

######  Proposition 36.

There exists a ranking voting
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{utilitarian})$
without restriction on weights such that the social choice function that
returns the optimal solution is not strategyproof.

###### Proof.

Gibbard-Satterthwaite’s theorem applies when $W=1$. ∎

######  Proposition 37.

There exists a value function voting
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{utilitarian})$
when all objects have the same weight such that the social choice function
that returns the optimal solution is not strategyproof.

###### Proof.

The mechanism may simulate a ranking voting, which is already not
strategyproof. ∎

######  Proposition 38.

There exists an approval voting
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{utilitarian})$
when all objects have the same weight such that the social choice function
that returns the optimal solution is not strategyproof.

###### Proof.

We build the strategyproof approval voting. There are $4$ objects $a,b,c,d$
and $2$ voters (even if the objects chosen by everyone are chosen in the end).
The weight constraint $W$ is equal to $2$. First : if we have an order
$a>b>c>d$ on the objects. We define the approval voting with sincere ballots
as follows:

  * •

$v_{1}$: $a,c$

  * •

$v_{2}$: $a,b$

With this ranking, according to the order, the best solution is $a,b$, thus,
this solution is chosen.

Assume voter $2$ changes her vote to $c,\textbf{d}$.
With this ranking, according to the order, the best solution is $a,c$ (because
with the optimization function, $a,b$ has score $0$ and so cannot be chosen),
thus, $a,c$ is chosen, increasing the utility of player $1$ from $1$ to $2$.∎

######  Proposition 39.

There exists a ranking voting
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{fair})$
without restriction on weights such that the social choice function that
returns the optimal solution is not strategyproof.

###### Proof.

If all the weights are the same and $W=1$, then Gibbard-Satterthwaite’s
theorem applies. ∎

######  Proposition 40.

There exists a ranking voting
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{fair})$
with equal weights (unitary) such that the social choice function that returns
the optimal solution is not strategyproof.

###### Proof.

Gibbard-Satterthwaite’s theorem applies when $W=1$. ∎

######  Proposition 41.

There exists a value function voting
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{fair})$
with equal weights (unitary) such that the social choice function that returns
the optimal solution is not strategyproof.

###### Proof.

It is already not strategyproof if the value function simulates a ranking. ∎

######  Proposition.

7 There exists an approval voting
$(\mathcal{\mathcal{V}},\mathcal{O},W,(b^{*}_{v})_{v\in\mathcal{\mathcal{V}}},\mathcal{A}lgo_{fair})$
with ${u}_{v}(e)=\sum_{o\in e\cap d^{*}_{v}}w(o)$ such that the social choice
function that returns the optimal solution is not strategyproof.

###### Proof.

We are looking at a strongly non-dictatorial first-class CM, the utility can
take more than three values, and if we create an object of weight. We can
lower the utility of a solution by removing an object from the sincere vote,
it does not change the utility of the other solutions that are not included in
the first one if the object is selected the right way. Hence, the proof of 6
adapts and this CM is not strategyproof. ∎

######  Proposition 42.

The following problem

Input: A set of voters $\mathcal{\mathcal{V}}$, a set of objects
$\mathcal{O}$, ballots which are bijections: $\mathcal{O}\to[m]$ , a positive
integer $T$.

Output: A set $S$ such that
$max\displaystyle\sum_{v\in\mathcal{\mathcal{V}}}{u}_{v}(S)\geq T$ and such
that $\displaystyle\sum_{o\in S}w(o)\leq W$.

can be solved in polynomial time.

###### Proof.

The algorithm in the proof of Proposition 34 still works in this case. ∎

######  Proposition 43.

The following problem $MMmK_{1}$

Input: A set of voters $\mathcal{\mathcal{V}}$, a set of objects
$\mathcal{O}$, ballots: $\mathcal{O}\to\mathbb{R}$, a positive integer $T$.

Question: Does there exists a set S such that
$maxmin\\{{u}_{v}(S):v\in\mathcal{\mathcal{V}}\\}\geq T$ and $|S|\leq W$?

is NP-complete.

###### Proof.

First, it is easy to see that _MMmK_ 1 is in NP. A non-deterministic algorithm
can exhibit a solution and check whether a subset of $\mathcal{O}$ is a
solution.

Now, we transform _PARTITION_ to $MMmK_{1}$. We recall the definition of this
NP-complete problem [13]:

Input: A finite set $A$ of integers.

Question: Is there a subset $A^{\prime}\subseteq A$ such that $\sum_{a\in
A^{\prime}}a=\sum_{a\in A\backslash A^{\prime}}a$ and
$|A^{\prime}|=|A\backslash A^{\prime}|$?

Let us take an instance $A$ of the _PARTITION_ problem. Then, we create $n+2$
voters and $|A|$ objects. Thus $\mathcal{O}=\\{o_{j}:j\in A\\}$. Every object
$object$ has its weight equal to $1$ ($w(o)=1$), $W=|A|/2$, and
$T=1/2\sum_{a\in A}a$. We build the utility.

  * •

For voter $v_{1}$, ${u}_{v_{1}}(o_{j})=a_{j}$, for every $j\leq|A|$.

  * •

For voter $v_{2}$, ${u}_{v_{2}}(o_{2j})=a_{2j+1}$ for every $j$ such that
$2j\leq|A|$, and ${u}_{v_{2}}(o_{2j+1})=a_{2j}$, for every $j$ such that
$2j+1\leq|A|$.

  * •

For all other voters $v_{i}$, ($i\geq 3$), ${u}_{i}(o_{j})=0$ for every object
$object_{j}$ with $j\leq|A|$, except for
${u}_{i}(o_{2\cdot(i-2)})={u}_{i}(o_{2\cdot(i-2)+1})=(\sum_{a\in A}a)$.

This transformation can be performed in polynomial time.

Assume problem  _PARTITION_ has a solution $A^{\prime}$. Let
$\mathcal{O}^{\prime}$ be the set $\mathcal{O}^{\prime}$ of the
$\frac{|A|}{2}$ objects such that $o_{k}\in\mathcal{O}^{\prime}$ if $j\in
A^{\prime}$. The utility of voters $v_{1}$ and $v_{2}$ gives
$\sum_{o\in\mathcal{O}^{\prime}}{u}_{v}(o)=\frac{\sum_{a\in A}a}{2}$, and the
utility of all the other voters is $\sum_{a\in A}a$.

Conversely, assume there is a set of objects $\mathcal{O}^{\prime}$ such that
the utility of all the voters for $\mathcal{O}^{\prime}$ is greater than
$T=\frac{\sum_{a\in A}a}{2}$.

Every voter gives the selected set of objects the value
$\sum_{o\in\mathcal{O}^{\prime}}{u}_{i}(o)=\frac{\sum_{a\in A}a}{2}$. Then,
for every one of the $n$ last voters, the object $o_{2k-1}$ or the object
$o_{2k}$ has to be selected. Hence, the selected set of objects respects the
constraint: “the elements of $A$ are ordered as $a_{1},\dots,a_{2n}$ and we
require that $A^{\prime}$ contains exactly one of $a_{2k-1}$ or $a_{2k}$ for
$1\leq k\leq n$”. Plus, because of the $n/2$ voters $o_{2k-1}$ or $o_{2k}$
selected, for the two first voters, $\sum_{a\in A^{\prime}}a=\sum_{a\in
A\backslash A^{\prime}}a$. Thus, there is a solution to the problem
_PARTITION_.

Thus the desired result follows. ∎

###  A.2 Proofs of Section 5

######  Proposition.

13 If ($M$, $\mathcal{A}lgo$) is a neutral score function, then
$M=D+\lambda_{1}A^{(1)}+\dots+\lambda_{m}A^{(m)}_{m}$ with
$\lambda_{1},\dots,\lambda_{m}\in\mathbb{R}$, $D$ is a positive constant
diagonal matrix and $\forall i,j,k\in[m],i\neq j$ $A^{(j)}$ is such that
$A^{(j)}_{k,j}=1$ and $A^{(j)}_{k,i}=0$.

###### Proof.

We will prove this result by recurrence on the size of the matrix, i.e., the
number of objects of the vote. In this proof, we will also prove this result
in the case of only $2$ objects (it helps with the recurrence).

If $M$ is the $2\times 2$ left corner submatrix, then $M_{1,1}\geq M_{2,1}$
because $\forall i~{}\mathcal{A}lgo(\delta_{i})=i$.
$M(\delta_{1}+\delta_{2})_{1}=M(\delta_{1}+\delta_{2})_{2}$ so
$M_{1,1}+M_{1,2}=M_{2,1}+M_{2,2}$ so, by taking $c=M_{1,1}-M_{2,1}$, then,
$M_{2,2}-M_{1,2}=c$, hence, with $\lambda_{1}=M_{2,1}$ and
$\lambda_{2}=M_{1,2}$ we proved the result for $n=2$.

If $M$ is the $n+1*n+1$ left corner submatrix, then let us suppose that the
proposition is true for the $n*n$ left corner submatrix.

$M(\delta_{1}+\dots+\delta_{i_{n+1}})_{1}=\dots=M(\delta_{1}+\dots+\delta_{i_{n+1}})_{n+1}$.
Hence, for $k$ such that $2\leq k<n+1$,
$M_{1,1}+\dots+M_{1,n+1}=M_{k,1}+\dots+M_{k,n+1}$. But due to the result at
rank $n$, $M_{1,1}+\dots+M_{1,n}=M_{k,1}+\dots+M_{k,n}$. Hence,
$M_{1,n+1}=M_{k,n+1}=\lambda_{n+1}$.

Now take $k$ such that $1\leq k<n+1$;
$M(\delta_{k}+\delta_{i_{n+1}})_{k}=M(\delta_{k}+\delta_{i_{n+1}})_{n+1}$ so
$M_{k,k}+M_{k,n+1}=M_{n+1,k}+M_{n+1,n+1}$,
$c+\lambda_{k}+\lambda_{n+1}=M_{n+1,k}+M_{n+1,n+1}$. Let us take
$c^{\prime}=M_{n+1,n+1}-\lambda_{n+1}$. Now,
$M_{n+1,k}=\lambda_{k}+c-c^{\prime}$.

Due to
$M(\delta_{1}+\dots+\delta_{i_{n+1}})_{1}=\dots=M(\delta_{1}+\dots+\delta_{i_{n+1}})_{n+1}$,
$M_{1,n+1}+\dots+M_{n+1,n+1}=M_{1,1}+\dots+M_{n+1,1}=c+\lambda_{1}+\dots+\lambda_{n+1}$.
$\lambda_{1}+\dots+\lambda_{n+1}+n*c-(n-1)c^{\prime}=c+\lambda_{1}+\dots+\lambda_{n+1}$.
Hence, $c=c^{\prime}$, so $M_{n+1,n+1}=c+\lambda_{n+1}$ and
$M_{n+1,k}=\lambda_{k}+c-c^{\prime}=\lambda_{k}$, which proves the proposition
at rank $n+1$ ∎

######  Theorem.

14 If ($M$, $\mathcal{A}lgo$) is a neutral score function, then the winning
set of the social score function is the same as knapsack voting ($I_{m}$).

###### Proof.

Let us choose two objects $a$ and $b$ and $@a$ (resp $@b$) the number of times
that $a$ (resp $b$) appears in the ballots. If $@a=@b+k$ with k a constant,
due to $M(@a,@b)_{a}=M(@a,@b)_{b}$ and that voting for another object $c$
gives the same score to $a$ and $b$ (Proposition 13), the score of $a$ is
higher than the one of $b$. Hence, the winners are the objects with the
highest amount of vote. This is exactly the mechanism of knapsack voting. ∎

######  Lemma.

20 If ($M$, $\mathcal{A}lgo$) is a total score function with a matrix of size
at least $3\times 3$ and $x,y,z$ are three objects, then there exists a set of
ballot
$\mathbf{B}=k_{1}\delta_{1}+\dots+k_{x}\delta_{x}+k_{y}\delta_{y}+k_{z}\delta_{z}+\dots+k_{m}\delta_{m}$
such that $M(\mathbf{B})=\begin{pmatrix}t_{1}\\\ \dots\\\ t_{x}\\\ t_{y}\\\
t_{z}\\\ \dots\end{pmatrix}$ with $t_{z}>t_{y}>t_{x}$, $t_{z}>t_{i}$ for every
other object $i$ and $k_{1},k_{2},k_{3},\dots\neq 0$.

###### Proof.

$M$ is total, hence there exists $k_{x,1},k_{y,1},k_{z,1},\dots,k_{m,1}$ such
that
black$M(k_{x,1}\delta_{x}+k_{y,1}\delta_{y}+k_{z,1}\delta_{z}+\dots+k_{m,1}\delta_{i})=\\{z\\}$.

$M$ is total, hence there exists $k_{x,2},k_{y,2},\dots,k_{m,1}$ such that
black$M(k_{x,2}\delta_{x}+k_{y,2}\delta_{y}+k_{z,2}\delta_{z}+\dots+k_{m,2})=\\{y,z\\}$

(blackw.l.o.g, for $i\in[|1,m|]$, $k_{i,2}\neq 0$, else, just multiply
$k_{x,2}$, $k_{y,2}$,…enough so that
$M(k_{x,2}\delta_{x}+k_{y,2}\delta_{y}+k_{z,2}\delta_{z}+\dots)=\\{y,z\\}$ and
set $k_{i,2}=1$).

We will now show that there exists $\lambda_{1},\lambda_{2}\neq 0$ such that,
with $W=2$,
$M(\lambda_{1}k_{x,1}\delta_{x}+\lambda_{1}k_{y,1}\delta_{y}+\lambda_{1}k_{z,1}\delta_{z}+\dots+\lambda_{1}k_{m,1}\delta_{m}+\lambda_{2}k_{x,2}\delta_{x}+\lambda_{2}k_{y,2}\delta_{y}+\lambda_{2}k_{z,2}\delta_{z}+\dots+\lambda_{2}k_{m,1}\delta_{m})=\\{y,z\\}$

and with $W=1$,
$M(\lambda_{1}k_{x,1}\delta_{x}+\lambda_{1}k_{y,1}\delta_{y}+\lambda_{1}k_{z,1}\delta_{z}+\dots+\lambda_{1}k_{m,1}\delta_{m}+\lambda_{2}k_{x,2}\delta_{x}+\lambda_{2}k_{y,2}\delta_{y}+\lambda_{2}k_{z,2}\delta_{z}+\dots+\lambda_{2}k_{m,1}\delta_{m})=\\{z\\}$.

To have that, if with $W=1$,
$M(k_{x,2}\delta_{x}+k_{y,2}\delta_{y}+k_{z,2}\delta_{z}+\dots+k_{m,2}\delta_{m})=\\{z\\}$,
lets just take $\lambda_{1}=0,\lambda_{2}=1$.

Else, note $score_{1}(x),score_{1}(y),score_{1}(z)$ the scores of $x$, $y$ and
$z$ on votes
$k_{x,1}\delta_{x}+k_{y,1}\delta_{y}+k_{z,1}\delta_{z}+\dots+k_{m,1}\delta_{m}$
and $score_{2}(x),score_{2}(y),score_{2}(z)$ the scores of $x$, $y$ and $z$ on
votes
$k_{x,2}\delta_{x}+k_{y,2}\delta_{y}+k_{z,2}\delta_{z}+\dots+k_{m,2}\delta_{m}$.

Take $\lambda_{2}$ such that
$\lambda_{2}score_{2}(z)-\lambda_{2}score_{2}(x)>2*score_{1}(z)-score_{1}(x)$
($score_{2}(z)-score_{2}(x)\neq 0$).

Then, with
$\lambda_{1}=\lceil\frac{\lambda_{2}score_{2}(y)-\lambda_{2}score_{2}(z)}{score_{1}(z)-score_{1}(y)}\rceil$
(or
$\lambda_{1}=\frac{\lambda_{2}score_{2}(y)-\lambda_{2}score_{2}(z)}{score_{1}(z)-score_{1}(y)}+1$
if
$\frac{\lambda_{2}score_{2}(y)-\lambda_{2}score_{2}(z)}{score_{1}(z)-score_{1}(y)}$
is an integer),

black$\lambda_{1}score_{1}(z)+\lambda_{2}score_{2}(z)>\lambda_{1}score_{1}(y)+\lambda_{2}score_{2}(y)$
by definition of $\lambda_{1}$.

Now we will show that
black$\lambda_{1}score_{1}(y)+\lambda_{2}score_{2}(y)>\lambda_{1}score_{1}(x)+\lambda_{2}score_{2}(x)$
$\lambda_{1}$ is the smallest possible integer to get
$\lambda_{1}score_{1}(z)+\lambda_{2}score_{2}(z)>\lambda_{1}score_{1}(y)+\lambda_{2}score_{2}(y)$
and
$\lambda_{2}score_{2}(z)-\lambda_{2}score_{2}(x)>2*score_{1}(z)-*score_{1}(x)$
so

$\lambda_{2}score_{2}(y)+\lambda_{1}score_{1}(y)\geq$
$\lambda_{2}score_{2}(z)+\lambda_{1}score_{1}(z)-score_{1}(z)>$
($\lambda_{1}\neq 0$ due to
$M(k_{x,2}\delta_{x}+k_{y,2}\delta_{y}+k_{z,2}\delta_{z})=\\{y\\}$)
$\lambda_{2}score_{2}(x)+score_{1}(z)-score_{1}(x)+\lambda_{1}score_{1}(z)>$
$\lambda_{2}score_{2}(x)+score_{1}(z)-score_{1}(x)+\lambda_{1}score_{1}(x)>$
$\lambda_{1}score_{1}(x)+\lambda_{2}score_{2}(x)$
Hence, there exists
$k_{x,3},k_{y,3},k_{z,3},\dots,k_{m,3}=\lambda_{1}k_{x,1}+\lambda_{2}k_{x,2},\dots,\lambda_{1}k_{m,1}+\lambda_{2}k_{m,2}$
such that $M(k_{x,3}\delta_{x}+k_{y,3}\delta_{y}+k_{z,3}\delta_{z})$ is a
vector $\begin{pmatrix}t_{x,3}\\\ t_{y,3}\\\ t_{z,3}\\\ ..\end{pmatrix}$ with
$t_{z,3}>t_{y,3}>t_{x,3}$, $t_{z,3}>t_{i,3}$ for every other object $i$ and
$k_{x,3},k_{y,3},k_{z,3},\dots\neq 0$ ∎

######  Proposition.

21 For the total score functions, respecting CCP property implies respecting
the set of constraints $\Delta$.

###### Proof.

Assume that $M$ does not verify $\Delta$. We already proved that if $M$ does
not respect $\forall i,j,j\neq i~{}M_{i,j}<M_{j,j}$, then it is not
strategyproof, so it does not verify CCP, else, there exists
$x,y,z~{}s.t.~{}M_{y,z}-M_{y,x}\geq M_{z,z}-M_{z,x}$.

Lets take $x,y,z~{}s.t.~{}M_{y,z}-M_{y,x}-M_{z,z}+M_{z,x}=\epsilon_{1}>0$,

Due to Lemma 20, there exist a vote
$k_{x,1}\delta_{x}+k_{y,1}\delta_{y}+k_{z,1}\delta_{z}+\dots+k_{m,1}\delta_{m}$
such that
$M(k_{x,1}\delta_{x}+k_{y,1}\delta_{y}+k_{z,1}\delta_{z}+k_{m,1}\delta_{m})=\begin{pmatrix}t_{x,1}\\\
t_{y,1}\\\ t_{z,1}\\\ \dots\end{pmatrix}$ with $t_{z,1}>t_{y,1}>t_{x,1}$,
$t_{z,1}>t_{i,1}$ for every other object $i$ and
$k_{x,1},k_{y,1},k_{z,1},\dots\neq 0$.

Lets set $\epsilon_{2}=M_{y,y}-M(z,y)$. Lets multiply
$k_{x,1},k_{y,1},k_{z,1},\dots,t_{x,1},t_{y,1},t_{z,1},\dots$ by
$\lceil\frac{\epsilon_{2}}{\epsilon_{1}}\rceil+1$ to obtain
$k_{x,2},k_{y,2},k_{z,2},\dots,t_{x,2},t_{y,2},t_{z,2},\dots$.
Now, increase $k_{y,2}$ to $k_{y,3}$ and induce
$k_{x,3},k_{z,3},\dots,t_{x,3},t_{y,3},t_{z,3},\dots$ so that
$0<t_{z,3}-t_{y,3}\leq\epsilon_{2}$; it is possible because of the definition
of $\epsilon_{2}$, and that keeps the order $t_{x,3}<t_{y,3}<t_{z,3}$, because
$M_{y,y}>M_{x,z}$.

$k_{x,3}\geq\lceil\frac{\epsilon_{2}}{\epsilon_{1}}\rceil+1$, so we can change
$k_{x,3}$ and $k_{z,3}$ to
$k_{x,4}=k_{x,3}-\lceil\frac{\epsilon_{2}}{\epsilon_{1}}\rceil+1$ and
$k_{z,4}=k_{z,3}+\lceil\frac{\epsilon_{2}}{\epsilon_{1}}\rceil+1$.
With $W=1$,
$M(k_{x,3}\delta_{x}+k_{y,3}\delta_{y}+k_{z,3}\delta_{z})_{z}>M(k_{x,3}\delta_{x}+k_{y,3}\delta_{y}+k_{z,3}\delta_{z})_{y}$
but
$M(k_{x,4}\delta_{x}+k_{y,3}\delta_{y}+k_{z,4}\delta_{z})_{y}>M(k_{x,3}\delta_{x}+k_{y,3}\delta_{y}+k_{z,3}\delta_{z})_{z}$.
Let W be the number of object that have a better score than
$M(k_{x,3}\delta_{x}+k_{y,3}\delta_{y}+k_{z,3}\delta_{z})_{z}$ plus one ($x$
and $y$ are not in the solution). By swapping the votes one by one, when
$k_{x,3}$ gets changed to $k_{x,4}$ and $k_{z,3}$ to $k_{z,4}$, there is a
swap from $x$ to $z$ that changes the solution. During the swap of a solution,
$x$ cannot leave the solution since it was not in the solution, and $z$ cannot
enter it, since it was already in the solution. Thus, CCP is not verified. ∎

######  Proposition.

22 For the total score functions, with $3$ objects, respecting the set of
equations $\Delta$ implies respecting property $CCP$.

###### Proof.

Let us suppose that

  * •

$M$ satisfies $\Delta$;

  * •

A voter $v$ changes her ballot by removing $a$ and putting $b$ instead.

Let us denote $order_{1}$ (resp $order_{2}$) the order of the objects
according to their score before (resp after) $v$ changes her vote.

Due to $M_{c,b}-M_{c,a}<M_{b,b}-M_{b,a}$, if $c$ has a lower rank than $b$ in
$order_{1}$, it still has a lower rank in $order_{2}$.

Due to $M_{c,a}-M_{c,b}<M_{a,a}-M_{a,b}$, if $a$ has a higher rank than $c$ in
$order_{2}$, it has a higher rank in $order_{1}$. Hence, if $c$ has a higher
rank than $a$ in $order_{1}$, it still has a higher rank in $order_{2}$.

Due to $M_{a,a}>M_{b,a}$ and $M_{b,b}>M_{a,b}$ (or with cases of equality and
the tie break breaking for the object that is not voted), if $a$ has a higher
rank than $b$ in $order_{2}$, it has a higher rank than $b$ in $order_{1}$,
thus, if $b$ has a higher rank in $order_{1}$, it has a higher rank in
$order_{2}$.

The ties are broken the same way for $order_{1}$ and $order_{2}$.

With all these things coming together, the only change that can happen in the
winning set are the ones of CCP. ∎

######  Proposition.

23 Strategyproof total score functions respect $\Delta$.

###### Proof.

Assume that $M$ does not verify $\Delta$. We already proved that if $M$ does
not respect $\forall i,j,j\neq i~{}M_{i,j}<M_{j,j}$, then it is not
strategyproof, hence, there exists $x,y,z~{}s.t.~{}M_{y,x}-M_{y,z}\geq
M_{x,x}-M_{x,z}$.

Lets take $x,y,z~{}s.t.~{}M_{y,x}-M_{y,z}-M_{x,x}+M_{x,z}=\epsilon_{1}>0$,

Due to Lemma 20, there exists a set of ballots $\mathbf{B}_{1}$, cast by a set
of voters as large as necessary, such that
$k_{x,1}\delta_{x}+k_{y,1}\delta_{y}+k_{z,1}\delta_{z}+\dots+k_{m,1}\delta_{m}$
and such that
$M(k_{x,1}\delta_{x}+k_{y,1}\delta_{y}+k_{z,1}\delta_{z}+\dots+k_{m,1}\delta_{m})=\begin{pmatrix}t_{x,1}\\\
t_{y,1}\\\ t_{z,1}\\\ \dots\end{pmatrix}$ with $t_{z,1}>t_{y,1}>t_{x,1}$,
$t_{z,1}>t_{i,1}$ for every other object $i$ and
$k_{x,1},k_{y,1},k_{z,1},\dots\neq 0$.

There also exists a set of ballots $\mathbf{B}_{2}$, cast by a set of voters
as large as necessary, such that
$k_{x,2}\delta_{x}+k_{y,2}\delta_{y}+k_{z,2}\delta_{z}+\dots+k_{m,2}\delta_{m}$
and such that
$M(k_{x,2}\delta_{x}+k_{y,2}\delta_{y}+k_{z,2}\delta_{z}+\dots+k_{m,2}\delta_{m})=\begin{pmatrix}t_{x,2}\\\
t_{y,2}\\\ t_{z,2}\\\ \dots\end{pmatrix}$, with $t_{z,2}>t_{x,2}>t_{y,2}$,
$t_{z,2}>t_{i,2}$ for every other object $i$ and
$k_{x,2},k_{z,2},k_{y,2},\dots\neq 0$

Let $dist$ be $k_{x,2}-k_{y,2}$. For any $k_{b_{1}}$, there exists $k_{b_{2}}$
such that if
$k_{x,3}=k_{b_{1}}*k_{x,1}+k_{b_{2}}*k_{x,2}$,
$k_{y,3}=k_{b_{1}}*k_{y,1}+k_{b_{2}}**k_{y,2}$,
$k_{z,3}=k_{b_{1}}*k_{z,1}+k_{b_{2}}*k_{z,2}$, etc…then
$M(k_{x,3}\delta_{x}+k_{y,3}\delta_{y}+k_{z,3}\delta_{z}+k_{m,3}\delta_{m})=\begin{pmatrix}t_{x,3}\\\
t_{y,3}\\\ t_{z,3}\\\ \dots\end{pmatrix}$ with $t_{z,3}>t_{x,3}>t_{y,3}$,
$t_{z}>t_{i}$ for every other object $i$, $k_{x,3},k_{z,3},k_{y,3},\dots\neq
0$, $t_{x,3}-t_{y,3}\leq dist$ and due to the definition of $\mathbf{B}_{1}$
and $\mathbf{B}_{2}$, $t_{z,3}-t_{x,3}\geq k_{b_{1}}*(t_{z,1}-t_{y,1})$.
$t_{z,1}-t_{y,1}>0$ and $k_{b_{1}}$ is as high as we want, so we will now
assume that $t_{z,3}-t_{x,3}$ is the infinity and that the amount of votes for
each object is also the infinity.

$dist$ is finite. Due to $M_{y,x}-M_{y,z}\geq M_{x,x}-M_{x,z}$, there exists a
number $exch$ such that exchanging $exch$ votes from $z$ to $x$ leads to a
better score for $y$ than for $x$.

Let us multiply all the $t_{.,3}$ by $m!$ to obtain $t_{.,4}$. Now, note that
any number between $1$ and $m$ divides the sum of votes for the objects, that
is to say that for any $W$, with enough voters, such a set of ballots
$\mathbf{B}_{4}$ is possible to obtain, while keeping coherence between the
number of objects in the ballot and the number of objects in the solution.
Hence, it is now possible to choose $W$ as we want.

Now denote by $order_{1}$ the list of objects ordered by the score given by
$M(\mathbf{B}_{4})$. Now exchange $m!*exch$ votes from $z$ to $x$ (it is
possible because there is an infinity of votes for $z$). This gives a new set
of ballots $\mathbf{B}_{5}$ in which we take $order_{2}$, the list of objects
ordered by the score given by $M(\mathbf{B}_{5})$.

Now let us set $W$ to be the rank of $y$ (in case of equality, which cannot
happen between $x$ and $y$, by choice of $exch$, set $W$ so that every object
in equality with $y$ is selected) in $order_{2}$ and assume that a voter $v$
favorite outcome would be the one of $order_{2}$ (her strategyproof vote would
be to vote for the objects selected in $order_{2}$). $W<m$ because $x$ is not
selected. $z$ is selected both in $order_{1}$ and $order_{2}$, because it
cannot have a lower score than $y$ in $order_{2}$ since it was at infinity in
$order_{4}$ and we only changed a finite ($exch*m!$) amount of vote. The
solution as changed between $order_{1}$ and $order_{2}$, because either $x$
was selected in $order_{1}$ and is not in $order_{2}$, either $x$ was not
selected in $order_{1}$, hence, $y$ was not selected either, and $y$ is
selected in $order_{2}$. Thus, the utility of $v$ is higher in $order_{2}$
than in $order_{1}$. There is one change in a ballot from $z$ to $x$ (from a
set of ballots $\mathbf{B}_{5}$ to a set of ballots $\mathbf{B}_{6}$) that led
to this improvement of utility. Assume that $v$ votes a strategyproof way and
that the other ballots lead to $\mathbf{B}_{5}$ (it is possible because there
is an infinity of votes for every object). $z$ is part of the solution of
$order_{2}$, which is optimal for $v$; hence, in her strategyproof vote, she
votes for $z$ The same way, $x$ is not in her strategyproof vote. $v$ can now
change her vote from $z$ to $x$ and increase her utility. ∎

######  Proposition.

24 With strictly more than $3$ objects, there exist some score functions that
respect the set of constraints $\Delta$ and are not strategyproof.

###### Proof.

Let $M$ be a score matrix $\begin{pmatrix}101&0&0&0\\\ 0&3&0&0\\\ 0&0&100&0\\\
0&2&0&99\end{pmatrix}$. There are $2$ voters. The rows of the matrix
correspond to objects $a,b,c,d$.

  * •

$v_{1}$ votes $a,d$

  * •

$v_{2}$ votes $a,c$

$\\{a,c\\}$ wins. If, instead, the votes are:

  * •

$v_{1}$ votes $b,d$

  * •

$v_{2}$ votes $a,c$

now $\\{a,d\\}$ wins. Hence, if $v_{1}$ wants $\\{a,d\\}$, she should lie on
her ballot.

One can easily verify that this matrix respects $\Delta$ ∎

######  Proposition.

26 If $m>3$, every strategyproof total score function satisfies $\Delta^{+}$.

###### Proof.

Assume that $M$ does not verify $\Delta$. We already proved that if $M$ does
not respect $\forall i,j,j\neq i~{}M_{i,j}<M_{j,j}$ or
$x,y,z~{}s.t.~{}M_{y,x}-M_{y,z}\leq M_{x,x}-M_{x,z}$, then it is not
strategyproof, hence, there exists
$a,x,y,z\in\mathcal{O},M_{x,a}-M_{x,z}>M_{y,a}-M{y,z}$.

Lets take
$a,x,y,z\in\mathcal{O}~{}s.t.~{}M_{x,a}-M_{x,z}-M_{y,a}+M{y,z}=\epsilon_{1}>0$,

Due to Lemma 20, there exists a set of ballots $\mathbf{B}_{1}$ with as many
voters as necessary such that
$k_{x,1}\delta_{x}+k_{y,1}\delta_{y}+k_{z,1}\delta_{z}+\dots+k_{m,1}\delta_{m}$
and such that
$M(k_{x,1}\delta_{x}+k_{y,1}\delta_{y}+k_{z,1}\delta_{z}+\dots+k_{m,1}\delta_{m})=\begin{pmatrix}t_{x,1}\\\
t_{y,1}\\\ t_{z,1}\\\ \dots\end{pmatrix}$ with $t_{z,1}>t_{y,1}>t_{x,1}$,
$t_{z,1}>t_{i,1}$ for every other object $i$ and
$k_{x,1},k_{y,1},k_{z,1},\dots\neq 0$

There also exists a set of ballots $\mathbf{B}_{2}$ with as many voters as
necessary such that
$k_{x,2}\delta_{x}+k_{y,2}\delta_{y}+k_{z,2}\delta_{z}+\dots+k_{m,2}\delta_{m}$
and such that
$M(k_{x,2}\delta_{x}+k_{y,2}\delta_{y}+k_{z,2}\delta_{z}+\dots+k_{m,2}\delta_{m})=\begin{pmatrix}t_{x,2}\\\
t_{y,2}\\\ t_{z,2}\\\ \dots\end{pmatrix}$ with $t_{z,2}>t_{x,2}>t_{y,2}$,
$t_{z,2}>t_{i,2}$ for every other object $i$ and
$k_{x,2},k_{z,2},k_{y,2},\dots\neq 0$

Let $dist$ be $k_{x,2}-k_{y,2}$. For any $k_{b_{1}}$, there exists $k_{b_{2}}$
such that if
$k_{x,3}=k_{b_{1}}*k_{x,1}+k_{b_{2}}*k_{x,2}$,
$k_{y,3}=k_{b_{1}}*k_{y,1}+k_{b_{2}}**k_{y,2}$,
$k_{z,3}=k_{b_{1}}*k_{z,1}+k_{b_{2}}*k_{z,2}$, etc…then
$M(k_{x,3}\delta_{x}+k_{y,3}\delta_{y}+k_{z,3}\delta_{z}+k_{m,3}\delta_{m})=\begin{pmatrix}t_{x,3}\\\
t_{y,3}\\\ t_{z,3}\\\ \dots\end{pmatrix}$ with $t_{z,3}>t_{x,3}>t_{y,3}$,
$t_{z}>t_{i}$ for every other object $i$, $k_{x,3},k_{z,3},k_{y,3},\dots\neq
0$, $t_{x,3}-t_{y,3}\leq dist$ and due to the definition of $\mathbf{B}_{1}$
and $\mathbf{B}_{2}$, $t_{z,3}-t_{x,3}\geq k_{b_{1}}*(t_{z,1}-t_{y,1})$.
$t_{z,1}-t_{y,1}>0$ and $k_{b_{1}}$ is as high as we want, so we will now
assume that $t_{z,3}-t_{x,3}$ is the infinity and that the amount of votes for
each object is also the infinity.

$dist$ is finite. Due to $M_{y,x}-M_{y,z}\geq M_{x,x}-M_{x,z}$, there exists a
number $exch$ such that exchanging $exch$ votes from $z$ to $a$ leads to a
better score for $y$ than for $x$.

Let us multiply all the $t_{.,3}$ by $m!$ to obtain $t_{.,4}$. Now, note that
any number between $1$ and $m$ divides the sum of votes for the objects, that
is to say that for any $W$, with enough voters, such a vote $\mathbf{B}_{4}$
is possible to obtain, while keeping coherence between the number of objects
in the ballot and the number of objects in the solution. Hence, it is now
possible to choose $W$ as we want.

Now denote by $order_{1}$ the list of objects ordered by the score given by
$M(\mathbf{B}_{4})$. Now exchange $m!*exch$ votes from $z$ to $a$ (it is
possible because there is an infinity of votes for $z$). This gives a new vote
$\mathbf{B}_{5}$ in which we take $order_{2}$, the list of objects ordered by
the score given by $M(\mathbf{B}_{5})$.

Now let us set $W$ to be the rank of $y$ (in case of equality, which cannot
happen between $x$ and $y$, by choice of $exch$, set $W$ so that every object
in equality with $y$ is selected) in $order_{2}$ and assume that a voter $v$
favorite outcome would be the one of $order_{2}$ (her strategyproof vote would
be to vote for the objects selected in $order_{2}$). $W<m$ because $x$ is not
selected. $z$ is selected both in $order_{1}$ and $order_{2}$, because it
cannot have a lower score than $y$ in $order_{2}$ since it was at infinity in
$order_{4}$ and we only changed a finite ($exch*m!$) amount of vote. The
solution as changed between $order_{1}$ and $order_{2}$, because either $x$
was selected in $order_{1}$ and is not in $order_{2}$, either $x$ was not
selected in $order_{1}$, hence, $y$ was not selected either, and $y$ is
selected in $order_{2}$. Thus, the utility of $v$ is higher in $order_{2}$
than in $order_{1}$. There is one change a vote from $z$ to $x$ (from a vote
$\mathbf{B}_{5}$ to a vote $\mathbf{B}_{6}$) that led to this improvement of
utility. Assume that $v$ votes a strategyproof way and that the other ballots
lead to $\mathbf{B}_{5}$ (it is possible because there is an infinity of votes
for every object). $z$ is part of the solution of $order_{2}$, which is
optimal for $v$; hence, in her strategyproof vote, she votes for $z$ The same
way, $x$ is not in her strategyproof vote. $v$ can now change her vote from
$z$ to $x$ and increase her utility. ∎

######  Proposition.

27 If $m>3$, every total score function that satisfies $\Delta^{+}$ satisfies
CCP.

###### Proof.

Let us suppose that

  * •

$M$ satisfies $\Delta^{+}$;

  * •

A voter $v$ changes her ballot by removing $a$ and putting $b$ instead.

Let us denote $order_{1}$ (resp $order_{2}$) the order of the objects
according to their score before (resp after) $v$ changes her vote.

If $\forall c,d\in\mathcal{O},M_{d,b}-M_{d,a}=M_{c,b}-M{c,a}$, then every
$c,d\in\mathcal{O}$ have the same relative rank.

Due to $b,c,a~{}~{}M_{c,b}-M_{c,a}\leq M_{b,b}-M_{b,a}$, for every object
$c\neq a,b$, if $c$ has a lower rank than $b$ in $order_{1}$, it still has a
lower rank in $order_{2}$.

Due to $M_{a,b}<M_{b,b}$ and $M_{b,a}<M_{a,a}$ (or with cases of equality and
the tie break breaking for the object that is not voted), if $a$ has a lower
rank than $b$ in $order_{1}$, it still has a lower rank in $order_{2}$.

Due to $b,c,a~{}~{}M_{c,a}-M_{c,b}\leq M_{a,a}-M_{a,b}$, for every object
$c\neq a$, if $a$ has a higher rank than $c$ in $order_{2}$, it has a higher
rank in $order_{1}$. Hence, if $c$ has a higher rank than $a$ in $order_{1}$,
it still has a higher rank in $order_{2}$.

The ties are broken the same way for $order_{1}$ and $order_{2}$.

With all these things coming together, the only change that can happen in the
winning set are the ones of CCP. ∎