Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Autonomous Agents and Multi-Agent Systems
Erschienen in: Autonomous Agents and Multi-Agent Systems 3/2019

27.02.2019

Inferring true voting outcomes in homophilic social networks

verfasst von: John A. Doucette, Alan Tsang, Hadi Hosseini, Kate Larson, Robin Cohen

Erschienen in: Autonomous Agents and Multi-Agent Systems | Ausgabe 3/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We investigate the problem of binary opinion aggregation in a social network regarding an objective outcome. Agents receive independent noisy signals relating to the outcome, but may converse with their neighbors in the network before opinions are aggregated, resulting in incorrect opinions gaining prominence in the network. Recent work has shown that, in the general case, there is no procedure for inferring the correct outcome that incorporates information from the connections between agents (i.e. the structure of the social network). We develop a new approach for inferring the true outcome that can benefit from the additional information provided by the social network, under the simple assumption that agents will more readily convert to the true opinion than to a false one, generating a homophilic effect for voters with the correct opinion. Our proposed approach is computationally efficient, and provides significantly more accurate inference in many domains, which we demonstrate via both simulated and real-world datasets. We also theoretically characterize the properties that are necessary for our approach to perform well. Finally, we extend our approach to directed social networks, and cases with many alternatives, and outline areas for future research.
Vorheriger Artikel Algorithms for destructive shift bribery
Nächster Artikel Decomposition methods with deep corrections for reinforcement learning

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Throughout, we use inference in the sense of its common usage in statistics: inferring the value of a variable or parameter on the basis of a given set of data. For us, the variable of interest is usually the winner of an election, while the data are usually the votes.
 
2
Note also, that if other inequalities are known (e.g. \(h^\prime (V_i=\lambda , V_j=\lambda | W=\lambda ) < h^\prime (V_i \ne \lambda , V_j \ne \lambda | W=\lambda )\), our techniques can often be naturally extended to infer the true outcome by changing the interpretation of the counts described below. However, we believe these other cases are less likely to arise in practice.
 
3
\(\varPhi ^{-1}\) being the inverse of the CDF of the normal distribution: \(\varPhi (y) = \frac{1}{\sqrt{2\pi }}\int _{-\infty }^y e^{-x^2/2} dt\).
 
4
Note, this class is not limited to problems where linkages do not depend on other linkage decisions that have been made. Scalefree networks, for example, have the same probability of any two agents being connected in the final graph a priori, before any connections have been added. This is all that is required.
 
5
Despite the state of a node being influenced only by its out-neighbors, we need to examine both \(\overleftarrow{h}\) and \(\overrightarrow{h}\), because we are evaluating the likelihood of observing the configuration of the entire directed graph.
 
6
Actually, to generate a graph on n vertices, the process terminates only when we attempt to add the \(n+1\)th vertex.
 
Literatur
1.
Acemoglu, D., Bimpikis, K., & Ozdaglar, A. (2014). Dynamics of information exchange in endogenous social networks. Theoretical Economics, 9(1), 41–97.MathSciNetCrossRefMATH
2.
3.
Auletta, V., Caragiannis, I., Ferraioli, D., Galdi, C., & Persiano, G. (2015). Minority becomes majority in social networks. In International conference on web and internet economics (pp. 74–88). Springer.
4.
Billingsley, P. (1995). Probability and measure. Wiley series in probability and mathematical statistics. New York: Wiley.MATH
5.
Black, D. (1958). The theory of committees and elections. Berlin: Springer.MATH
6.
Boldi, P., Bonchi, F., Castillo, C., & Vigna, S. (2009). Voting in social networks. In Proceedings of the 18th ACM conference on information and knowledge management (pp. 777–786). ACM.
7.
Bollobás, B., Borgs, C., Chayes, J., & Riordan, O. (2003). Directed scale-free graphs. In Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms (pp. 132–139). Society for Industrial and Applied Mathematics.
8.
Bredereck, R., & Elkind, E. (2017). Manipulating opinion diffusion in social networks. In Proceedings of the twenty-sixth international joint conference on artificial intelligence (IJCAI-17) (pp. 894–900).
9.
Brill, M., Elkind, E., Endriss, U., & Grandi, U. (2016). Pairwise diffusion of preference rankings in social networks. In Proceedings of the 25th international joint conference on artificial intelligence (pp. 130–136).
10.
Caragiannis, I., Nath, S., Procaccia, A. D., & Shah, N. (2017). Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research, 58, 123–152.MathSciNetCrossRefMATH
11.
Caragiannis, I., Procaccia, A. D., & Shah, N. (2013). When do noisy votes reveal the truth? In Proceedings of the fourteenth ACM conference on electronic commerce (pp. 143–160). ACM
12.
Coleman, J., Katz, E., & Menzel, H. (1957) . The diffusion of an innovation among physicians. Sociometry (pp. 253–270).
13.
Coleman, J., Menzel, H., & Katz, E. (1966). Medical innovations: A diffusion study. New York: Bobbs Merrill.
14.
Conitzer, V. (2012). Should social network structure be taken into account in elections? Mathematical Social Sciences, 64(1), 100–102.MathSciNetCrossRefMATH
15.
Conitzer, V. (2013). The maximum likelihood approach to voting on social networks. In Proceedings of the 51st annual Allerton conference on communication, control, and computing (Allerton-13) (pp. 1482–1487). Allerton Retreat Center, Monticello, IL, USA, 2013.
16.
de Caritat, M. J. A. N., et al. Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. L’imprimerie royale, 1785. [Translation found in Black, 1958].
17.
Erdős, P., & Rényi, A. (1959). On random graphs. Publicationes Mathematicae Debrecen, 6, 290–297.MathSciNetMATH
18.
Faliszewski, P., Gonen, R., Kouteckỳ, M., & Talmon, N. (2018). Opinion diffusion and campaigning on society graphs. In Proceedings of the 27th international joint conference on artificial intelligence (pp. 219–225).
19.
Fish, B., Huang, Y., & Reyzin, L. (2016). Recovering social networks by observing votes. In Proceedings of the 2016 international conference on autonomous agents & multiagent systems (pp. 376–384). International Foundation for Autonomous Agents and Multiagent Systems.
20.
Friedkin, N. E., & Johnsen, E. C. (1990). Social influence and opinions. Journal of Mathematical Sociology, 15(3–4), 193–206.CrossRefMATH
21.
Grandi, U. (2017). Social choice and social networks. Trends in Computational Social Choice (pp. 169–184).
22.
Granovetter, M. S . (1977) . The strength of weak ties. In Social networks (pp. 347–367). Elsevier.
23.
Halberstam, Y., & Knight, B. (2016). Homophily, group size, and the diffusion of political information in social networks: Evidence from twitter. Journal of Public Economics, 143, 73–88.CrossRef
24.
Hastings, W. K. (1970). Monte carlo sampling methods using Markov chains and their applications. Biometrika, 57(1), 97–109.MathSciNetCrossRefMATH
25.
Ismaili, A., & Perny, P. (2016). Computational social choice for coordination in agent networks. Annals of Mathematics and Artificial Intelligence, 77(3–4), 335–359.MathSciNetCrossRefMATH
26.
Izsak, R., Talmon, N., & Woeginger, G. J. (2018). Committee selection with intraclass and interclass synergies. In Proceedings of the 32nd AAAI conference (pp. 1071–1078).
27.
Kapferer, B. (1972). Strategy and transaction in an African factory: African workers and Indian management in a Zambian town. Manchester: Manchester University Press.
28.
Katakis, I., Tsapatsoulis, N., Mendez, F., Triga, V., & Djouvas, C. (2014). Social voting advice applications—Definitions, challenges, datasets and evaluation. IEEE Transactions on Cybernetics, 44(7), 1039–1052.CrossRef
29.
Kempe, D., Kleinberg, J., & Tardos, É. (2003). Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining (pp. 137–146). ACM.
30.
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6), 1087–1092.CrossRef
31.
Mossel, E., Neeman, J., & Tamuz, O. (2014). Majority dynamics and aggregation of information in social networks. Autonomous Agents and Multi-Agent Systems, 28(3), 408–429.CrossRef
32.
Procaccia, A. D., Shah, N., & Sodomka, E. (2015). Ranked voting on social networks. In Proceedings of the 24th international joint conference on artificial intelligence (pp. 2040–2046). AAAI Press.
33.
Rogers, E. M. (2010). Diffusion of innovations. New York: Simon and Schuster.
34.
Salehi-Abari, A., & Boutilier, C. (2014). Empathetic social choice on social networks. In Proceedings of the 2014 international conference on autonomous agents and multi-agent systems (pp. 693–700). International Foundation for Autonomous Agents and Multiagent Systems.
35.
Salehi-Abari, A., & Boutilier, C. (2015). Preference-oriented social networks: Group recommendation and inference. In Proceedings of the 9th ACM conference on recommender systems (pp. 35–42). ACM.
36.
Strang, D., & Soule, S. A. (1998). Diffusion in organizations and social movements: From hybrid corn to poison pills. Annual Review of Sociology, 24, 265–290.CrossRef
37.
Tosatto, S. C., & Van Zee, M. (2014). Bridging social network analysis and judgment aggregation. In International conference on social informatics (pp. 17–33). Springer.
38.
Tsang, A., & Larson, K. (2016). The echo chamber: Strategic voting and homophily in social networks. In Proceedings of the 2016 international conference on autonomous agents & multiagent systems (pp. 368–375). International Foundation for Autonomous Agents and Multiagent Systems.
39.
Viswanath, B., Bashir, M. A., Crovella, M., Guha, S., Gummadi, K. P., Krishnamurthy, B., et al. (2014). Towards detecting anomalous user behavior in online social networks. In USENIX security symposium (pp. 223–238).
40.
Watts, A. (2014). The influence of social networks and homophily on correct voting. Network Science, 2(1), 90–106.CrossRef
41.
Wilder, B., & Vorobeychik, Y. (2018). Controlling elections through social influence. In Proceedings of the 17th international conference on autonomous agents and multiagent systems (pp. 265–273). International Foundation for Autonomous Agents and Multiagent Systems.
42.
Xia, L. (2015). Generalized decision scoring rules: Statistical, computational, and axiomatic properties. In Proceedings of the sixteenth ACM conference on economics and computation (pp. 661–678). ACM.
Metadaten
Titel
Inferring true voting outcomes in homophilic social networks
verfasst von
John A. Doucette
Alan Tsang
Hadi Hosseini
Kate Larson
Robin Cohen
Publikationsdatum
27.02.2019
Verlag
Springer US
Erschienen in
Autonomous Agents and Multi-Agent Systems / Ausgabe 3/2019
Print ISSN: 1387-2532
Elektronische ISSN: 1573-7454
DOI
https://doi.org/10.1007/s10458-019-09405-1

Premium Partner

    Bildnachweise