A weak version of Barberà-Kelly's Theorem

Jahn Franklin Leal; Ramón Pino Pérez

doi:10.15446/recolma.v51n2.70900

Veröffentlicht

2017-07-01

A weak version of Barberà-Kelly's Theorem

Una versión débil del teorema de Barberà-Kelly

DOI:

https://doi.org/10.15446/recolma.v51n2.70900

Schlagworte:

Preferences, Manipulation, Social Choice, Merging (en)
Preferencias, Manipulación, Elección Social, Fusión (es)

Downloads

PDF (Español)

Autor/innen

Jahn Franklin Leal Universidad de Los Andes
Ramón Pino Pérez Universidad de Los Andes

Abstract (en)
Abstract (es)

Lifting preferences over candidates to preferences over sets of candidates allows us to give a very natural notion of manipulability for social choice functions. In particular, we give simple conditions over the liftings entailing the manipulability of reasonable social choice functions. Our result is a weak version of Barberà and Kelly's Theorem, indeed it can be obtained from this last Theorem. However, we give a direct and very natural proof of our manipulability Theorem which is informative about the nature of the liftings allowing manipulability.

Transferir preferencias sobre candidatos a preferencias sobre conjuntos de candidatos permite dar una noción muy natural de manipulación para funciones de elección social. En este trabajo damos condiciones sobre esas funciones de transferencia que implican la manipulabilidad de funciones de elección social con un mínimo de propiedades razonables. Nuestro resultado es una versión débil del teorema de Barberà y Kelly, de hecho puede ser obtenido como una consecuencia de éste. Sin embargo, damos una prueba directa y natural de nuestro teorema de manipulabilidad, la cual da una información clara sobre la naturaleza de las funciones de transferencia que permiten la manipulación.

Literaturhinweise

C. E. Alchourrón, P. Gärdenfors, and D. Makinson, On the logic of theory

change: Partial meet contraction and revision functions, J. Symb. Log. 50

(1985), no. 2, 510-530.

K. J. Arrow, Social Choice and Individual Values, Cowles Commission

Monograph No. 12, John Wiley & Sons, Inc., New York, N. Y.; Chapman

& Hall, Ltd., London, 1951.

S. Barberà, Manipulation of social decision functions, J. Econom. Theory

(1977), no. 2, 266-278.

S. Barberà, Strategy-proof social choice, Handbook of Social Choice and Welfare (A. K. Sen K. J. Arrow and K. Suzumura, eds.), vol. 2, Elsevier, 2010,

pp. 731-832.

S. Barberà, W. Bossert, and P. K. Pattanaik, Ranking sets of objects,

Handbook of Utility Theory (C. Seidl S. Barber~A , P.J. Hammond, ed.),

vol. 2, Kluwer Publisher, 2004, pp. 893-978.

S. Barberà, B. Dutta, and A. Sen, Strategy-proof social choice correspondences, J. Econom. Theory 101 (2001), no. 2, 374-394.

J.-P. Benoît, Strategic manipulation in voting games when lotteries and

ties are permitted, J. Econom. Theory 102 (2002), no. 2, 421-436.

W. Bossert, P. K. Pattanaik, and Y. Xu, Ranking opportunity sets: an

axiomatic approach, J. Econom. Theory 63 (1994), no. 2, 326-345.

S. Brams and P. C. Fishburn, Voting procedures, Handbook of Social

Choice and Welfare (K. J. Arrow, A. K. Sen, and K. Suzumura, eds.),

vol. 1, 2002, pp. 173-236.

F. Brandt, Group-strategyproof irresolute social choice functions, IJCAI

, Proceedings of the 22nd International Joint Conference on Artificial

Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011 (T.Walsh, ed.),

IJCAI/AAAI, 2011, pp. 79-84.

F. Brandt and M. Brill, Necessary and sufficient conditions for the strategyproofness of irresolute social choice functions, Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2011), Groningen, The Netherlands, July 12-14, 2011 (R. A. Krzysztof, ed.), ACM, 2011, pp. 136-142.

S. Chopra, A. K. Ghose, and T. A. Meyer, Social choice theory, belief

merging, and strategy-proofness, Information Fusion 7 (2006), no. 1, 61-79.

S. Coste-Marquis, J. Lang, P. Liberatore, and P. Marquis, Expressive power and succinctness of propositional languages for preference representation, Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth International Conference (KR2004), Whistler, Canada, June 2-5, 2004 (D. Dubois, C. A. Welty, and M.-A. Williams, eds.), AAAI Press, 2004, pp. 203-212.

B. de Finetti, La prévision: ses lois logiques, ses sources subjectives, Annales de l'Institut Henri Poincaré 7 (1937), 1-68.

K. Downing and M. van Hees, In praise of manipulation, British Journal

of Political Science 38 (2008), 1-15.

D. Dubois and H. Fargier, A unified framework for order-of-magnitude

confidence relations, Proceedings of the 20th conference on Uncertainty in

artificial intelligence (Arlington, Virginia, United States), UAI '04, AUAI

Press, 2004, pp. 138-145.

D. Dubois, H. Fargier, and P. Perny, Qualitative decision theory with preference relations and comparative uncertainty: An axiomatic approach, Artif. Intell. 148 (2003), no. 1-2, 219-260.

D. Dubois, H. Fargier, H. Prade, and P. Perny, Qualitative decision theory: from savage's axioms to nonmonotonic reasoning, J. ACM 49 (2002), no. 4, 455-495.

D. Dubois, J. Lang, and H. Prade, Possibilistic logic, Handbook of logic

in artificial intelligence and logic programming, Vol. 3 (Dov M. Gabbay,

C. H. Hogger, and J. A. Robinson, eds.), Oxford Univ. Press, New York,

, pp. 439-513.

D. Dubois and H. Prade, Possibilistic logic: a retrospective and prospective view, Fuzzy Sets and Systems 144 (2004), no. 1, 3-23.

J. Duggan and T. Schwartz, Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized, Soc. Choice Welf. 17 (2000), no. 1, 85-93.

H. Egli, A mathematical model for nondeterministic computations, Tech. report, ETH, 1975.

P. Everaere, S. Konieczny, and P. Marquis, The strategy-proofness land-scape of merging, J. Artif. Intell. Res. 28 (2007), 49-105.

P. C. Fishburn, Even-chance lotteries in social choice theory, Theory and Decision 3 (1972), no. 1, 18-40.

D. M. Gabbay, O. Rodrigues, and G. Pigozzi, Connections between belief revision, belief merging and social choice, J. Log. Comput. 19 (2009), no. 3, 445-446.

P. Gärdenfors, Manipulation of social choice functions, Journal of Economic Theory 13 (1976), no. 2, 217-228.

C. Geist and U. Endriss, Automated search for impossibility theorems in social choice theory: Ranking sets of objects, Journal of Artificial Intelligence Research 40 (2011), 143-174.

A. Gibbard, Manipulation of voting schemes: a general result, Econometrica 41 (1973), 587-601.

D. Grossi, Correspondences in the theory of aggregation, Logic and the

Foundations of Game and Decision Theory - LOFT 8, Revised and selected

papers (W. van der Hoek G. Bonanno, B. Loewe, ed.), vol. 1, 2010, pp. 34-60.

J. Y. Halpern, Defining relative likelihood in partially-ordered preferential structures, Journal of Artificial Intelligence Research 7 (1997), 1-24.

J. S. Kelly, Strategy-proofness and social choice functions without single-valuedness, Econometrica 45 (1977), no. 2, 439-446.

J. S. Kelly, Social Choice theory: An introduction, Springer-Verlag, Berlin, 1988.

J. G. Kemeny, Mathematics without numbers, Daedalus 18 (1959), 577-591.

S. Konieczny and R. Pino Pérez, Merging information under constraints: A logical framework, J. Log. Comput. 12 (2002), no. 5, 773-808.

S. Konieczny and R. Pino Pérez, Propositional belief base merging or how to merge beliefs/goals coming from several sources and some links with social choice theory, European Journal of Operational Research 160 (2005), no. 3, 785-802.

S. Konieczny and R. Pino Pérez, Logic based merging, J. Philosophical Logic 40 (2011), no. 2, 239-270.

J. F. Leal, Manipulabilidad en la teoría de elección social, Master's thesis, Departamento de Matemáticas, Universidad de Los Andes, Mérida,

Venezuela, 2005.

D. Makinson, Combinatorial versus decision-theoretic components of impossibility theorems, Theory and Decision 40 (1996), no. 2, 181-189.

R. Milner, Processes: a mathematical model of computing agents, Logic

Colloquium '73 (Bristol, 1973), Studies in Logic and the Foundations of

Mathematics, Vol. 80, North-Holland, Amsterdam, 1975, pp. 157-173.

R. Pino Perez and F. Leal, A notion of manipulability based on lifting preferences, Tech. report, No 252. Departamento de Matemáticas, Universidad de Los Andes, 2007.

M. S. Pini, F. Rossi, K. B. Venable, and T. Walsh, Aggregating partially

ordered preferences, J. Log. Comput. 19 (2009), no. 3, 475-502.

P. J. Reny, Arrow's theorem and the Gibbard-Satterthwaite theorem: a unified approach, Econom. Lett. 70 (2001), no. 1, 99-105.

M. A. Satterthwaite, Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions, J. Econom. Theory 10 (1975), no. 2, 187-217.

G. L. S. Shackle, On the meaning and measure of uncertainty, Metroeconomica 5 (1953), 97-115.

G. L. S. Shackle, Uncertainty in economics and other reflections, Cambridge University Press, Cambridge, UK, 1995.

A. D. Taylor, Social choice and the mathematics of manipulation, Cambridge University Press, Cambridge, UK, 2005.

J. van Benthem, P. Girard, and O. Roy, Everything else being equal: A

modal logic for ceteris paribus preferences, Journal of Philosophical Logic

(2009), 83-125.

P. Vincke, Arrow's theorem is not a surprising result, European J. Oper.

Res. 10 (1982), no. 1, 22-25.

Zitationsvorschlag

APA

Leal, J. F. und Pino Pérez, R. (2017). A weak version of Barberà-Kelly’s Theorem. Revista Colombiana de Matemáticas, 51(2), 173–194. https://doi.org/10.15446/recolma.v51n2.70900

ACM

[1]

Leal, J.F. und Pino Pérez, R. 2017. A weak version of Barberà-Kelly’s Theorem. Revista Colombiana de Matemáticas. 51, 2 (Juli 2017), 173–194. DOI:https://doi.org/10.15446/recolma.v51n2.70900.

ACS

(1)

Leal, J. F.; Pino Pérez, R. A weak version of Barberà-Kelly’s Theorem. rev.colomb.mat 2017, 51, 173-194.

ABNT

LEAL, J. F.; PINO PÉREZ, R. A weak version of Barberà-Kelly’s Theorem. Revista Colombiana de Matemáticas, [S. l.], v. 51, n. 2, p. 173–194, 2017. DOI: 10.15446/recolma.v51n2.70900. Disponível em: https://revistas.unal.edu.co/index.php/recolma/article/view/70900. Acesso em: 22 jan. 2025.

Chicago

Leal, Jahn Franklin, und Ramón Pino Pérez. 2017. „A weak version of Barberà-Kelly’s Theorem“. Revista Colombiana De Matemáticas 51 (2):173-94. https://doi.org/10.15446/recolma.v51n2.70900.

Harvard

Leal, J. F. und Pino Pérez, R. (2017) „A weak version of Barberà-Kelly’s Theorem“, Revista Colombiana de Matemáticas, 51(2), S. 173–194. doi: 10.15446/recolma.v51n2.70900.

IEEE

[1]

J. F. Leal und R. Pino Pérez, „A weak version of Barberà-Kelly’s Theorem“, rev.colomb.mat, Bd. 51, Nr. 2, S. 173–194, Juli 2017.

MLA

Leal, J. F., und R. Pino Pérez. „A weak version of Barberà-Kelly’s Theorem“. Revista Colombiana de Matemáticas, Bd. 51, Nr. 2, Juli 2017, S. 173-94, doi:10.15446/recolma.v51n2.70900.

Turabian

Leal, Jahn Franklin, und Ramón Pino Pérez. „A weak version of Barberà-Kelly’s Theorem“. Revista Colombiana de Matemáticas 51, no. 2 (Juli 1, 2017): 173–194. Zugegriffen Januar 22, 2025. https://revistas.unal.edu.co/index.php/recolma/article/view/70900.

Vancouver

1.

Leal JF, Pino Pérez R. A weak version of Barberà-Kelly’s Theorem. rev.colomb.mat [Internet]. 1. Juli 2017 [zitiert 22. Januar 2025];51(2):173-94. Verfügbar unter: https://revistas.unal.edu.co/index.php/recolma/article/view/70900

Bibliografische Angaben herunterladen

CrossRef Cited-by

3

1. Amílcar Mata Díaz, Ramón Pino Pérez. (2023). On manipulation in merging epistemic states. International Journal of Approximate Reasoning, 155, p.66. https://doi.org/10.1016/j.ijar.2023.01.005.

2. Amílcar Mata Díaz, Ramón Pino Pérez. (2021). Symbolic and Quantitative Approaches to Reasoning with Uncertainty. Lecture Notes in Computer Science. 12897, p.457. https://doi.org/10.1007/978-3-030-86772-0_33.

3. Amílcar Mata Díaz, Ramón Pino Pérez, Jahn Franklin Leal. (2023). Taxonomy of powerful voters and manipulation in the framework of social choice functions. Social Choice and Welfare, 61(2), p.277. https://doi.org/10.1007/s00355-022-01448-w.