Abstract
We analyze a network coloring game on hypergraphs which can also describe a voter model. Each node represents a voter and is colored according to its preferred candidate (or undecided). Each hyperedge is a subset of voters that can interact and influence one another. In each round of the game, one hyperedge is chosen randomly, and the voters in the hyperedge can change their colors according to some prescribed probability distribution. We analyze this interaction model based on random walks on the associated weighted, directed state graph. We consider three scenarios — a memoryless game, a partially memoryless game and the general game using the memoryless game for comparison and analysis. Under certain ‘memoryless’ restrictions, we can use semigroup spectral methods to explicitly determine the spectrum of the state graph, and the random walk on the state graph converges to its stationary distribution in O(m logn) steps, where n is the number of voters and m is the number of hyperedges. This can then be used to determine an appropriate cut-off time for voting: we can estimate probabilities that events occur within an error bound of ε by simulating the voting game for O(log(1/ε) m logn) rounds. Next, we consider a partially memoryless game whose associated random walk can be written as a linear combination of a memoryless random walk and another given random walk. In such a setting, we provide bounds on the convergence time to the stationary distribution, highlighting a tradeoff between the proportion of memorylessness and the time required. To analyze the general interaction model, we will first construct a companion memoryless process and then choose an appropriate damping constant β to build a partially memoryless process. The partially memoryless process can serve as an approximation of the actual interaction dynamics for determining the cut-off time if the damping constant is appropriately chosen either by using simulation or depending on the rules of interaction.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aldous, D., Fill, J.A.: Reversible Markov chains and random walks on graphs (preprint), http://www.stat.berkeley.edu/~aldous/RWG/book.html
Bidigare, T.P., Hanlon, P., Rockmore, D.N.: A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements. Duke Mathematical Journal 99(1), 135–174 (1999)
Brown, K.S.: Semigroups, rings, and Markov chains. Journal of Theoretical Probability 13(3), 837–938 (2000)
Brown, K.S., Diaconis, P.: Random walks and hyperplane arrangements. Annals of Probability 26(4), 1813–1854 (1998)
Chung, F.: Laplacians and the Cheeger inequality for directed graphs. Annals of Combinatorics 9(1), 1–19 (2005)
Chung, F., Graham, R.: Edge flipping in graphs. Advances in Applied Mathematics 48(1), 37–63 (2012)
Clifford, P., Sudbury, A.: A model for spatial conflict. Biometrika 60(3), 581–588 (1973)
Ellison, G.: Learning, local interaction, and coordination. Econometrica 61(3), 1047–1071 (1993)
Fill, J.A.: An exact formula for the move-to-front rule for self-organizing lists. Journal of Theoretical Probability 9(1), 113–160 (1996)
Holley, R.A., Liggett, T.M.: Ergodic theorems for weakly interacting infinite systems and the voter model. Annals of Probability 3(4), 643–663 (1975)
Judd, S., Kearns, M.: Behavioral experiments in networked trade. In: Proceedings of the 9th ACM Conference on Electronic Commerce, pp. 150–159 (2008)
Judd, S., Kearns, M., Vorobeychik, Y.: Behavioral dynamics and influence in networked coloring and consensus. Proceedings of the National Academy of Sciences 107(34), 14978–14982 (2010)
Kandori, M., Mailath, G., Rob, R.: Learning, mutation, and long run equilibria in games. Econometrica 61(1), 29–56 (1993)
Kearns, M., Judd, S., Tan, T., Wortman, J.: Behavioral experiments on biased voting in networks. Proceedings of the National Academy of Sciences 106(5), 1347–1352 (2009)
Kearns, M., Suri, S., Montfort, N.: An experimental study of the coloring problem on human subject networks. Science 313(5788), 824–827 (2006)
Kearns, M., Tan, J.: Biased Voting and the Democratic Primary Problem. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 639–652. Springer, Heidelberg (2008)
Klein-Barmen, F.: On a broader analysis of lattice theory. Mathematische Zeitschrift 46(1), 472–480 (1940) (in German)
Montanari, A., Saberi, A.: Convergence to equilibrium in local interaction games. In: Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 303–312 (2009)
Mossel, E., Schoenebeck, G.: Reaching consensus on social networks. In: Proceedings of the First Symposium on Innovations in Computer Science (ICS), pp. 214–229 (2010)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press (1995)
Schützenberger, M.-P.: On left-regular bands. Comptes Rendus de l’Académie des Sciences 224, 777–778 (1947) (in French)
Suchecki, K., Eguíluz, V., San Miguel, M.: Voter model dynamics in complex networks: Role of dimensionality, disorder, and degree distribution. Physical Review E 72, 1–8 (2005)
Tahbaz-Salehi, A., Jadbabaie, J.: Consensus over ergodic stationary graph processes. IEEE Transactions on Automatic Control 55(1), 225–230 (2010)
Yildiz, M.E., Pagliari, A., Ozdaglar, A., Scaglione, A.: Voting models in random networks. In: Proceedings of the Information Theory and Applications Workshop (ITA), pp. 1–7 (2010)
Young, H.P.: The evolution of conventions. Econometrica 61(1), 57–84 (1993)
Zachary, W.W.: An information flow model for conflict and fission in small groups. Journal of Anthropological Research 33(4), 452–473 (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chung, F., Tsiatas, A. (2012). Hypergraph Coloring Games and Voter Models. In: Bonato, A., Janssen, J. (eds) Algorithms and Models for the Web Graph. WAW 2012. Lecture Notes in Computer Science, vol 7323. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30541-2_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-30541-2_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30540-5
Online ISBN: 978-3-642-30541-2
eBook Packages: Computer ScienceComputer Science (R0)