research-article

Possible and necessary winner problem in social polls

Authors:

Victor Naroditskiy,

Nina Narodytska,

Toby WalshAuthors Info & Claims

AAMAS '14: Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems

Pages 613 - 620

Published: 05 May 2014 Publication History

Abstract

Social networks are increasingly being used to conduct polls. We introduce a simple model of such social polling. We suppose agents vote sequentially, but the order in which agents choose to vote is not necessarily fixed. We also suppose that an agent's vote is influenced by the votes of their friends who have already voted. Despite its simplicity, this model provides useful insights into a number of areas including social polling, sequential voting, and manipulation. We prove that the number of candidates and the network structure affect the computational complexity of computing which candidate necessarily or possibly can win in such a social poll. For social networks with bounded treewidth and a bounded number of candidates, we provide polynomial algorithms for both problems. In other cases, we prove that computing which candidates necessarily or possibly win are computationally intractable.

References

[1]

N. Alon, M. Babaioff, R. Karidi, R. Lavi, and M. Tennenholtz. Sequential voting with externalities: herding in social networks. In Proc. of EC'12, pages 36--36. ACM, 2012.

Digital Library

[2]

M. Battaglini, R. Morton, and T. Palfrey. Efficiency, Equity, and Timing of Voting Mechanisms. Am. Polit. Sci. Rev., 101(03):409--424, 2007.

[3]

R. van Bevern, M. R. Fellows, S. Gaspers, and F. A. Rosamond. Myhill-nerode methods for hypergraphs. In Proc. of ISAAC 2013, LNCS, pages 372--382. Springer, 2013.

[4]

S. Bikhchandani, D. Hirshleifer, and I. Welch. A theory of fads, fashion, custom, and cultural change as informational cascades. J. Polit. Econ., 100(5):992--1026, 1992.

[5]

H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305--1317, 1996.

Digital Library

[6]

H. L. Bodlaender, M. R. Fellows, and T. Warnow. Two strikes against perfect phylogeny. In Proc. of ICALP 1992, volume 623 of LNCS, pages 273--283. Springer, 1992.

Digital Library

[7]

V. Conitzer, T. Sandholm, and J. Lang. When are elections with few candidates hard to manipulate. J. ACM, 54, 2007.

Digital Library

[8]

V. Conitzer, T. Walsh, and L. Xia. Dominating manipulations in voting wih partial information. In W. Burgard and D. Roth, editors, Proc. of AAAI 2011. AAAI Press, 2011.

[9]

E. Dekel and M. Piccione. Sequential voting procedures in symmetric binary elections. J. Polit. Econ., 108(1):pp. 34--55, 2000.

[10]

R. Diestel. Graph Theory. Springer, 2010.

[11]

B. Doerr, M. Fouz, and T. Friedrich. Why rumors spread so quickly in social networks. Communications of the ACM, 55(6):70--75, 2012.

Digital Library

[12]

R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013.

Digital Library

[13]

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra. Using complexity to protect elections. Communications of the ACM, 53(11):74--82, 2010.

Digital Library

[14]

P. Faliszewski and A. Procaccia. AI's war on manipulation: Are we winning? AI Magazine, 31(4):53--64, 2010.

Digital Library

[15]

M. R. Fellows, S. Gaspers, and F. Rosamond. Multivariate complexity theory. In Computer Science: The Hardware, Software and Heart of It, chapter 13, pages 269--293. Springer, 2011.

[16]

M. R. Fellows and M. A. Langston. An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In Proc. of FOCS 1989, pages 520--525, 1989.

Digital Library

[17]

J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006.

Digital Library

[18]

M. R. Garey and D. R. Johnson. Computers and Intractability. W. H. Freeman and Company, 1979.

Digital Library

[19]

S. Gaspers, V. Naroditskiy, N. Narodytska, and T. Walsh. Possible and necessary winner problem in social polls. Technical Report 1302.1669, arXiv, 2013.

[20]

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

[21]

M. Grabisch and A. Rusinowska. Different approaches to influence based on social networks and simple games. In A. Van Deemen and A. Rusinowska, editors, Collective Decision Making, volume 43 of Theory and Decision Library C, pages 185--209. Springer, 2010.

[22]

F. Harary and E. M. Palmer. Graphical Enumeration. Academic Press, 1973.

[23]

T. Kloks. Treewidth, Computations and Approximations. Springer, 1994.

[24]

K. Konczak and J. Lang. Voting procedures with incomplete preferences. In Proc. of the IJCAI-2005 workshop on Advances in Preference Handling, 2005.

[25]

V. A. Liskovets. More on counting acyclic digraphs. Technical Report 0804.2496 {math.CO}, arXiv, 2008.

[26]

N. Maudet, M. S. Pini, K. B. Venable, and F. Rossi. Influence and aggregation of preferences over combinatorial domains. In Proc. of AAMAS 2012, pages 1313--1314, 2012.

Digital Library

[27]

R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.

[28]

S. Obraztsova and E. Elkind. Optimal manipulation of voting rules. In Proc. of AAMAS 2012, pages 619--626, 2012.

Digital Library

[29]

M. S. Pini, F. Rossi, K. B. Venable, and T. Walsh. Incompleteness and incomparability in preference aggregation. In Proc. of IJCAI 2007, pages 1464--1469, 2007.

Digital Library

[30]

N. Robertson and P. D. Seymour. Graph minors III: Planar tree-width. J. Combin. Theor. B, 36(1):49--64, 1984.

[31]

R. W. Robinson. Counting labeled acyclic digraphs. In New Directions in the Theory of Graphs, pages 239--273. Academic Press, 1973.

[32]

M. Satterthwaite. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. JET, 10:187--216, 1975.

[33]

C. A. Tovey. A simplified NP-complete satisfiability problem. Discrete Appl. Math., 8(1):85--89, 1984.

[34]

T. Walsh. Uncertainty in preference elicitation and aggregation. In Proc. of AAAI 2007, pages 3--8. AAAI, 2007.

Digital Library

[35]

L. Xia and V. Conitzer. Determining possible and necessary winners under common voting rules given partial orders. In Proc. of AAAI 2008, pages 196--201. AAAI Press, 2008.

Digital Library

Cited By

Blanchard N(2018)Building Trust for Sample VotingInternational Journal of Decision Support System Technology10.4018/IJDSST.201810010410:4(50-64)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.4018/IJDSST.2018100104
Dey PMisra NNarahari Y(2016)Complexity of manipulation with partial information in votingProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060654(229-235)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3060621.3060654
Vaish RMisra NAgarwal SBlum AJonker CMarsella SThangarajah JTuyls K(2016)On the Computational Hardness of Manipulating Pairwise Voting RulesProceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems10.5555/2936924.2936978(358-367)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/2936924.2936978
Show More Cited By

Index Terms

Possible and necessary winner problem in social polls
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Possible and necessary winner problem in social polls
AAMAS '13: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems

Social networks are increasingly being used to conduct polls. We introduce a simple model of such social polling. We suppose agents vote sequentially, but the order in which agents choose to vote is not necessarily fixed. We also suppose that an agent's ...
The possible winner with uncertain weights problem
Abstract
The original possible winner problem consists of an unweighted election with partial preferences and a distinguished candidate c and asks whether the preferences can be extended to total ones such that c wins the given election. We ...
Computing the Extremal Possible Ranks with Incomplete Preferences
AAMAS '21: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems

Various voting rules are based on ranking the candidates by scores induced by aggregating voter preferences. A winner (respectively, unique winner) is a candidate who receives a score not smaller than (respectively, strictly greater than) the remaining ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

AAMAS '14: Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems

May 2014

1774 pages

ISBN:9781450327381

General Chairs:
Ana Bazzan
UFRGS, Brazil
,
Michael Huhns
University of South Carolina, USA
,
Program Chairs:
Alessio Lomuscio
Imperial College London, UK
,
Paul Scerri
Carnegie Mellon University, USA

Sponsors

IFAAMAS

In-Cooperation

SIGAI: ACM Special Interest Group on Artificial Intelligence

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 05 May 2014

Check for updates

Author Tags

Qualifiers

Research-article

Conference

AAMAS '14

Sponsor:

AAMAS '14: International conference on Autonomous Agents and Multi-Agent Systems

May 5 - 9, 2014

Paris, France

Acceptance Rates

AAMAS '14 Paper Acceptance Rate 169 of 709 submissions, 24%;

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
71
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Blanchard N(2018)Building Trust for Sample VotingInternational Journal of Decision Support System Technology10.4018/IJDSST.201810010410:4(50-64)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.4018/IJDSST.2018100104
Dey PMisra NNarahari Y(2016)Complexity of manipulation with partial information in votingProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060654(229-235)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3060621.3060654
Vaish RMisra NAgarwal SBlum AJonker CMarsella SThangarajah JTuyls K(2016)On the Computational Hardness of Manipulating Pairwise Voting RulesProceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems10.5555/2936924.2936978(358-367)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/2936924.2936978
Tsang ADoucette JHosseini HWeiss GYolum PBordini RElkind E(2015)Voting with Social InfluenceProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2773464(1841-1842)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2773464

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents