DESIGNING STRATEGYPROOF ELECTION SYSTEMS WITH SCORE VOTING A P REPRINT_2

2025-05-06 0 0 444.32KB 22 页 10玖币

侵权投诉

DESIGNING STRATEGYPROOF ELECTION SYSTEMS WITH

SCORE VOTING

A PREPRINT

Johanne Cohen

LISN-CNRS, Universit´

e Paris-Saclay, France

johanne.cohen@lri.fr

Daniel Cordeiro

University of S˜

ao Paulo, Brazil

daniel.cordeiro@usp.br

Valentin Dardilhac

Universit´

e Paris-Saclay, France

valentin.dardilhac@ens-paris-saclay.fr

Victor Glaser

Ecole normale sup´

erieure de Lyon, France

victor.glaser@ens-lyon.fr

October 7, 2022

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 ﬁnancing 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 deﬁne 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 satisﬁes CCP.

These results are combined to devise an algorithm that can ﬁnd the closest total score function that

makes any given score voting to be strategyproof.

arXiv:2210.02496v1 [cs.GT] 5 Oct 2022

Designing Strategyproof Election Systems with Score Voting A PREPRINT

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 ﬁrst 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, beneﬁ-

ciaries, 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 ﬁrst 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

atotal score function is strategyproof if and only if its score function satisﬁes CCP. We present an algorithm that use

this result to ﬁnd 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 deﬁne 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 ﬁrst 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 kprojects 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 ﬁtting a limited budget Bwhile

Designing Strategyproof Election Systems with Score Voting A PREPRINT

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 satisﬁes the budget constraint. They showed that this schema is strategyproof and welfare-

maximizing when the outcome for the voter is given by the `1distance 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 over-

prioritize majority preferences, resulting in unfairness problems [9]. The seminal work by Moulin [16] shows that `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 ﬁxed (“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 the-

orem 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].

Acommon Choice Mechanism (CM) is a 6-uplet (V,O,(uv)v∈V , Q, S,Algo)which is deﬁned as follows. We consider

a set of voters V= [n](where [i] = {1, . . . , i}, for i∈N) and a ﬁnite set of malternatives (objects) Othat answers

the set of questions Q requested from the voters. The set of all valid possible collective decisions is denoted by S ⊆ O.

Each voter v∈ V has a private preference over all solutions given by a utility function1uv:P(O)→R. According

to a set of questions Q, that deﬁnes the format of the ballots, each voter vanswers these questions via a ballot bv.

Adeclaration proﬁle B= (b1, . . . , bn)consists of a ballot bvfor each voter v. In the remaining of the document,

(bv;b−v)is a shorthand for (b1, . . . , bv, . . . , bn), used here to highlight the ballot of voter vagainst that of all other

voters.

Voting can mean different things depending on the speciﬁed form of a ballot and a collective decision. For example,

the ballot can be a subset e∈ P(O), a linear ordering of the objects, or the value function among all the objects. The

social choice function Algo, aggregates a set of individual ballots Binto a collective decision and returns a solution,

which is a winning set of objects Algo(B).

Our study focuses on the design of the social choice function that incentives an individual voter to vote sincerely. We

denote by b∗

vthe ballot of the voter vif she sincerely answers the questions based on her utility.

Deﬁnition 1. We say that a CM is strategyproof if: for all proﬁle ballots B, for all voters v∈ V, we have

uv(Algo(b∗

v;B−v)) ≥uv(Algo(bv;B−v)).

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

Deﬁnition 2. If the ballot is a valuation of the objects, a social welfare-maximizing function (SWF) is an optimization

function P(O)→Rthat maximizes a social welfare.

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

• a social welfare function denoted futilitarian is utilitarian if it maximizes Pv∈V Po∈sbv(o),∀s∈ S;

• a social welfare function denoted ffair, is fair if maximizes minv∈V Po∈sbv(o),∀s∈ S.

An algorithm Algo that ﬁnds the optimal solution of a utilitarian (resp. fair) function is denoted Algoutilitarian (resp.

Algof air).

In order to study different types of ballots, we use a particular class of CMs called Simple CMs that takes into ac-

count different weights of objects and uses the sincere ballot of the voter in its utility. Simple CM is a 5-uplet

(V,O, W, (b∗

v)v∈V ,Algo)deﬁned as follows. The ballots are functions: O → R. Every object ohas also a weight

denoted w(o)(hence, the weight is a function w:O → R). Value Wis a weight constraint that restricts valid solu-

tions, so that S={e∈ P(O) : Po∈ew(o)≤W}. The utility depends on the values of the set in the sincere ballot:

uv(e) = Po∈eb∗

v(o).

Now we deﬁne the type of the Simple CM according to the type of ballot:

1The set of all subsets of Sis denoted by P(S).

Designing Strategyproof Election Systems with Score Voting A PREPRINT

• a simple CM is an approval voting if the ballot bvis a a function bv:O → {0,1}. This ballot can also be

deﬁned as a vector of {0,1}|O|;

• a simple CM is a ranking voting if the ballot bvof voter vis a rank of the objects, i.e. a bijection bv:O →

{1,|O|};

• a simple CM is the value function voting if the ballot is a valuation of the objects of O, i.e. a function

bv:O → R.

Example of participatory budgeting problem: Given a set of projects O(the alternatives), a set of voters Vneeds

to select a set of projects they have identiﬁed to be interested in. Each project ohas a cost w(o), and there is a

ﬁxed total budget of W. The question Qarises of which projects should be funded. Each voter vvotes for a subset

dv⊆ O, such that it satisﬁes the budget constraint W(i.e., Po∈dvw(o)≤W). Since the ballot is a subset O, it

is also possible to describe participatory budgeting with a simple CM, which is (V,O, W, (b∗

v)v∈V ,Algoutilitarian).

The participatory budgeting problem has a utilitarian social welfare function because the objective is to ﬁnd the set of

objects that maximize the number of votes.

Finally, Knapsack voting is an approval voting (V,O, W, (b∗

v)v∈V ,Algoutilitarian)when all objects have the same

weight and Algoutilitarian 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 func-

tion. 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).

Designing Strategyproof Election Systems with Score Voting A PREPRINT

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 theorem2gives some impossibility results about

strategyproofness.

Theorem 3 ([10]).Whenever the utility uvis 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.

Deﬁnition 5. Let CM=(V,O,(uv)v∈V , Q, S,Algo)be a common choice mechanism. A feasible solution s∈ S is

called ﬁrst-class set if for every s∗∈ S, there is a permutation σs∗such that ∀v∈ V, uσs∗(v)(s)≥uv(s∗).

A common choice mechanism CM=(V,O,(uv)v∈V , Q, S,Algo)is called ﬁrst-class if it always chooses a ﬁrst-class

set whenever there is one.

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

Theorem 6. A ﬁrst-class CM (E, S,V,{uv}v∈V , Q, Algo) is not strategyproof if both those conditions hold:

•Qforces the type of the ballots so that the ballot of voter vhas to contain the feasible solution mv=

argmax{uv(s) : s∈ S} and the feasible solution m∗

v=argmax{uv(s) : s∈ S\{mv}}. Plus, given the

two preferred feasible solutions of a voter v,Qalso forces the type of the ballots so that the ballots contain

their images given by the utility function uv, which must be distinct; and

•the utilities can take at least 3distinct values (e.g., 0,1,2, or a ranking on at least 3objects, and only one is

selected) independently for each feasible solution.

Proof. Lets take two voters v1and v2such that m∗

v2=mv1and m∗

v1=mv2and uv1(mv1) = uv2(mv2)and

uv2(mv1) = uv1(mv2)6=uv1(mv1).

The only ﬁrst-class sets are mv1and mv2(because one of the voters of a ﬁrst-class set must have a preference greater

or equal than uv1(mv1)for this set, which is only the case for mv1and mv2). Hence, if the ballots are sincere, the CM

chooses either mv1or mv2(lets say w.l.o.g. that it is mv2). If v1lies on her ballot by telling that uv1(mv2)is lower

than the reality (it does not change the other values of the utility because of their independence), then mv2is not a

ﬁrst-class set anymore. Thus, mv1is chosen (being the only ﬁrst-class set), and the utility of v1increases. Hence, this

CM is not strategyproof.

Theorem 6 applies in different cases than Gibbard-Satterthwaite’s theorem because the next proposition is an applica-

tion of Theorem 6 (it is not the case for Gibbard-Satterthwaite’s theorem).

Proposition 7. There exists an approval voting (V,O, W, (b∗

v)v∈V ,Algof air)with uv(e) = Po∈e∩d∗

vw(o)such that

the social choice function that returns the optimal solution is not strategyproof.

Now, we characterize a sufﬁcient property on CMs to be strategyproof. From now on, we only consider approval

voting (the ballots can also be deﬁned as a vector of {0,1}|O|).

2Theorem 3 is a rephrasing of this theorem using our notation.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

DESIGNINGSTRATEGYPROOFELECTIONSYSTEMSWITHSCOREVOTINGAPREPRINTJohanneCohenLISN-CNRS,Universit´eParis-Saclay,Francejohanne.cohen@lri.frDanielCordeiroUniversityofSaoPaulo,Brazildaniel.cordeiro@usp.brValentinDardilhacUniversit´eParis-Saclay,Francevalentin.dardilhac@ens-paris-saclay.frVictorGlaser´Ecole...

展开>> 收起<<

DESIGNING STRATEGYPROOF ELECTION SYSTEMS WITH SCORE VOTING A P REPRINT_2.pdf

共22页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

DESIGNING STRATEGYPROOF ELECTION SYSTEMS WITH SCORE VOTING A P REPRINT_2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: