Skip to main content

Finite local consistency characterizes generalized scoring rules

Publication ,  Journal Article
Xia, L; Conitzer, V
Published in: IJCAI International Joint Conference on Artificial Intelligence
January 1, 2009

An important problem in computational social choice concerns whether it is possible to prevent manipulation of voting rules by making it computationally intractable. To answer this, a key question is how frequently voting rules are manipulable. We [Xia and Conitzer, 2008] recently defined the class of generalized scoring rules (GSRs) and characterized the frequency of manipulability for such rules. We showed, by examples, that most common rules seem to fall into this class. However, no natural axiomatic characterization of the class was given, leaving the possibility that there are natural rules to which these results do not apply. In this paper, we characterize the class of GSRs based on two natural properties: it is equal to the class of rules that are anonymous and finitely locally consistent. Generalized scoring rules also have other uses in computational social choice. For these uses, the order of the GSR (the dimension of its score vector) is important. Our characterization result implies that the order of a GSR is related to the minimum number of locally consistent components of the rule. We proceed to bound the minimum number of locally consistent components for some common rules.

Duke Scholars

Published In

IJCAI International Joint Conference on Artificial Intelligence

ISSN

1045-0823

Publication Date

January 1, 2009

Start / End Page

336 / 341
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Xia, L., & Conitzer, V. (2009). Finite local consistency characterizes generalized scoring rules. IJCAI International Joint Conference on Artificial Intelligence, 336–341.
Xia, L., and V. Conitzer. “Finite local consistency characterizes generalized scoring rules.” IJCAI International Joint Conference on Artificial Intelligence, January 1, 2009, 336–41.
Xia L, Conitzer V. Finite local consistency characterizes generalized scoring rules. IJCAI International Joint Conference on Artificial Intelligence. 2009 Jan 1;336–41.
Xia, L., and V. Conitzer. “Finite local consistency characterizes generalized scoring rules.” IJCAI International Joint Conference on Artificial Intelligence, Jan. 2009, pp. 336–41.
Xia L, Conitzer V. Finite local consistency characterizes generalized scoring rules. IJCAI International Joint Conference on Artificial Intelligence. 2009 Jan 1;336–341.

Published In

IJCAI International Joint Conference on Artificial Intelligence

ISSN

1045-0823

Publication Date

January 1, 2009

Start / End Page

336 / 341