Abstract
We present a game-theoretic model for the creation of content networks such as the worldwide web. The action space of a node in our model consists of choosing a set of outgoing links as well as click probabilities on these links. A node’s utility is then the product of the traffic through this node, captured by its PageRank in the Markov chain created by the strategy profile, times the quality of the node, a surrogate for the website’s utility per visit, such as repute or monetization potential. The latter depends on the intrinsic quality of the node’s content, as modified by the chosen outgoing links and probabilities. We only require that the quality be a concave function of the node’s strategy (the distribution over outgoing links), and we suggest a natural example of such a function. We prove that the resulting game always has a pure Nash equilibrium. Experiments suggest that these equilibria are not hard to compute, avoid the reciprocal equilibria of other such models, have characteristics broadly consistent with what we know about the worldwide web, and seem to have favorable price of anarchy.
Research supported by the European Union (European Social Fund- ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) - Research Funding Program: THALES, investing in knowledge society through the European Social Fund. Also supported by NSF grants CCF0964033 and CCF1408635.
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
Similar content being viewed by others
References
Adamic, L., Huberman, B.: Power law distribution of the world wide web. Science 287(5461), 2115–2115 (2000)
Albers, S., Eilts, S., Even-Dar, E., Mansour, Y., Roditty, L.: On Nash equilibria for a network creation game. ACM Trans. Econ. Comput. 2(1), 1–27 (2014)
Avis, D., Iwama, K., Paku, D.: Verifying Nash equilibria in PageRank games on undirected web graphs. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 415–424. Springer, Heidelberg (2011)
Barabasi, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)
Bollobás, B., Riordan, O., Spencer, J., Tusnády, G.E.: The degree sequence of a scale-free random graph process. Random Struct. Algorithms 18(3), 279–290 (2001)
Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. Comput. Netw. ISDN Syst. 30(1–7), 107–117 (1998)
Broder, A.Z., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., Wiener, J.L.: Graph structure in the web. Comput. Netw. 33(1–6), 309–320 (2000)
Cooper, C., Frieze, A.M.: A general model of web graphs. Random Struct. Algorithms 22(3), 311–335 (2003)
Debreu, G.: A social equilibrium existence theorem. Proc. Natl. Acad. Sci. (PNAS) 38(10), 886–893 (1952)
Dellarocas, C., Katona, Z., Rand, W.: Media, aggregators, and the link economy: strategic hyperlink formation in content networks. Manage. Sci. 59(10), 2360–2379 (2013)
Fabrikant, A., Koutsoupias, E., Papadimitriou, C.: Heuristically optimized trade-offs: a new paradigm for power laws in the internet. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, p. 110. Springer, Heidelberg (2002)
Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C., Shenker, S.: On a network creation game. In: Proceedings of the 22nd Symposium on Principles of Distributed Computing (PODC 2003), pp. 347–351 (2003)
Fan, K.: Fixed-point and minimax theorems in locally convex topological linear spaces. Proc. Natl. Acad. Sci. (PNAS) 38, 121–126 (1952)
Fan, K.: Applications of a theorem concerning sets with convex sections. Math. Ann. 163, 189–203 (1966)
Foudalis, I., Jain, K., Papadimitriou, C., Sideri, M.: Modeling social networks through user background and behavior. In: Frieze, A., Horn, P., Prałat, P. (eds.) WAW 2011. LNCS, vol. 6732, pp. 85–102. Springer, Heidelberg (2011)
Hopcroft, J., Sheldon, D.: Manipulation-resistant reputations using hitting time. In: Bonato, A., Chung, F.R.K. (eds.) WAW 2007. LNCS, vol. 4863, pp. 68–81. Springer, Heidelberg (2007)
Hopcroft, J., Sheldon, D.: Network reputation games. Techical report, Cornell University (2008)
Katona, Z., Sarvary, M.: Network formation and the structure of the commercial world wide web. Mark. Sci. 27(5), 764–778 (2008)
Kominers, S.D.: Sticky content and the structure of the commercial web. Technical report, Harvard University (2009)
Kouroupas, G., Koutsoupias, E., Papadimitriou, C., Sideri, M.: Experiments with an economic model of the worldwide web. In: Deng, X., Ye, Y. (eds.) WINE 2005. LNCS, vol. 3828, pp. 46–54. Springer, Heidelberg (2005)
Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., Upfal, E.: Stochastic models for the web graph. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), pp. 57–65 (2000)
Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., Upfal, E.: The web as a graph. In: Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2000), pp. 1–10 (2000)
Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.: Trawling the web for emerging cyber-communities. In: Proceedings of the 8th International Conference on the World Wide Web (WWW 1999), pp. 1481–1493 (1999)
Laura, L., Leonardi, S., Millozzi, S., Meyer, U., Sibeyn, J.F.: Algorithms and experiments for the webgraph. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 703–714. Springer, Heidelberg (2003)
Leskovec, J., Kleinberg, J., Faloutsos, C.: Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2005), pp. 177–187 (2005)
Mitzenmacher, M.: A brief history of generative models for power law and lognormal distributions. Internet Math. 1(2), 226–251 (2004)
Nash, J.F.: Non-cooperative games. Ann. Math. 54, 286–295 (1951)
Roughgarden, T.: Intrinsic robustness of the price of anarchy. Commun. ACM 55(7), 116–123 (2012)
Tardos, E., Wexler, T.: Network formation games and the potential function method. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory, pp. 487–516. Cambridge University Press, Cambridge (2007). (Chap. 19)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kouroupas, G., Markakis, E., Papadimitriou, C., Rigas, V., Sideri, M. (2015). The Web Graph as an Equilibrium. In: Hoefer, M. (eds) Algorithmic Game Theory. SAGT 2015. Lecture Notes in Computer Science(), vol 9347. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48433-3_16
Download citation
DOI: https://doi.org/10.1007/978-3-662-48433-3_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48432-6
Online ISBN: 978-3-662-48433-3
eBook Packages: Computer ScienceComputer Science (R0)