Friend of my friend: network formation with two-hop benefit.

*(English)*Zbl 1327.91059Summary: How and why people form ties is a critical issue for understanding the fabric of social networks. In contrast to most existing work, we are interested in settings where agents are neither so myopic as to consider only the benefit they derive from their immediate neighbors, nor do they consider the effects on the entire network when forming connections. Instead, we consider games on networks where a node tries to maximize its utility taking into account the benefit it gets from the nodes it is directly connected to (called direct benefit), as well as the benefit it gets from the nodes it is acquainted with via a two-hop connection (called two-hop benefit). We call such games Two-Hop Games. The decision to consider only two hops stems from the observation that human agents rarely consider “contacts of a contact of a contact” (3-hop contacts) or further while forming their relationships. We consider several versions of Two-Hop games which are extensions of well-studied games. While the addition of two-hop benefit changes the properties of these games significantly, we prove that in many important cases good equilibrium solutions still exist, and bound the change in the price of anarchy due to two-hop benefit both theoretically and in simulation.

##### MSC:

91D30 | Social networks; opinion dynamics |

91A80 | Applications of game theory |

91A43 | Games involving graphs |

PDF
BibTeX
XML
Cite

\textit{E. Anshelevich} et al., Theory Comput. Syst. 57, No. 3, 711--752 (2015; Zbl 1327.91059)

Full Text:
DOI

##### References:

[1] | Abraham, DJ; Levavi, A; Manlove, DF; O’Malley, G, The stable roommates problem with globally ranked pairs, Internet Math., 5, 493-515, (2008) · Zbl 1194.91133 |

[2] | Abramson, G; Kuperman, M, Social games in a social network, Phys. Rev. E, 63, 030901, (2001) |

[3] | Alon, N; Demaine, ED; Hajiaghayi, MT; Leighton, T, Basic network creation games, SIAM J. Discret. Math., 27, 656-668, (2013) · Zbl 1273.90167 |

[4] | Anshelevich, E., Das, S., Naamad, Y.: Anarchy, stability, and utopia: creating better matchings. In: SAGT (2009) · Zbl 1262.91059 |

[5] | Anshelevich, E; Hoefer, M, Contribution games in networks, Algorithmica, 63, 51-90, (2012) · Zbl 1237.91054 |

[6] | Baiou, M; Balinski, M, Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry), Discret. Appl. Math., 101, 1-12, (2000) · Zbl 0946.90033 |

[7] | Bei, Xi; Chen, W; Teng, S; Zhang, J; Zhu, J, Bounded budget betweenness centrality game for strategic network formations, Theor. Comput. Sci., 412, 7147-7168, (2011) · Zbl 1244.91020 |

[8] | Bramoullé, Y; Kranton, R, Public goods in networks, J. Econ. Theory, 135, 478-494, (2007) · Zbl 1186.91099 |

[9] | Brandes, U., Hoefer, M., Nick, B.: Network creation games with disconnected equilibria. In: WINE (2008) |

[10] | Buehler, R., Goldman, Z., Liben-Nowell, D., Pei, Y., Quadri, J., Sharp, A., Taggart, S., Wexler, T., Woods, K.: The price of civil society. WINE (2011) |

[11] | Chung, KS, On the existence of stable roommate matchings, Games Econ. Behav., 33, 206-230, (2000) · Zbl 1047.91012 |

[12] | Corbo, J., Calvó-Armengol, A., Parkes, D.: The importance of network topology in local contribution games. WINE (2007) · Zbl 1244.91020 |

[13] | Corbo, J., Parkes, D.: The price of selfish behavior in bilateral network formation. In: Proceedings of PODC, pp. 99-107. ACM (2005) · Zbl 1314.91051 |

[14] | Demaine, E., Hajiaghayi, M., Mahini, H., Zadimoghaddam, M.: The price of anarchy in network creation games. In: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, pp. 292-298. ACM (2007) · Zbl 1283.68053 |

[15] | Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C., Shenker, S.: On a network creation game. In: Proceedings of PODC, pp. 347-351. ACM (2003) · Zbl 1322.91013 |

[16] | Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon., 9-15 (1962) · Zbl 0109.24403 |

[17] | Galeotti, A; Goyal, S; Jackson, MO; Vega-Redondo, F; Yariv, L, Network games, Rev. Econ. Stud., 77, 218-244, (2010) · Zbl 1197.91168 |

[18] | Gusfield, D., Irving, R.W.: The stable marriage problem: structure and algorithms (1989) · Zbl 0703.68046 |

[19] | Hoefer, M., Krysta, P.: Geometric network design with selfish agents. In: Computing and Combinatorics, pp. 167-178. Springer (2005) · Zbl 1128.68302 |

[20] | Hoefer, M., Skopalik, A.: Social context in potential games. In: WINE (2012) · Zbl 1256.91008 |

[21] | Jackson, MO; Wolinsky, A, A strategic model of social and economic networks, J. Econ. Theory, 71, 44-74, (1996) · Zbl 0871.90144 |

[22] | Laoutaris, N., Poplawski, L., Rajaraman, R., Sundaram, R., Teng, S.: Bounded budget connection (bbc) games or how to make friends and influence people, on a budget. In: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, pp. 165-174. ACM (2008) · Zbl 1301.91007 |

[23] | Manlove, D.: Algorithmics of matching under preferences. World Scientific Publishing (2013) · Zbl 1283.68018 |

[24] | Osborne, M.J., Rubinstein, A.: A course in game theory. MIT press (1994) · Zbl 1194.91003 |

[25] | Roth, A.E., Sotomayor, M.A.O.: Two-sided matching: a study in game-theoretic modeling and analysis, vol. 18. Cambridge University Press (1992) · Zbl 0781.90005 |

[26] | Sethuraman, J; Teo, CP; Qian, L, Many-to-one stable matching: geometry and fairness, Math. Oper. Res., 31, 581-596, (2006) · Zbl 1278.91107 |

[27] | Sotomayor, M, Three remarks on the many-to-many stable matching problem, Math. Social Sci., 38, 55-70, (1999) · Zbl 0951.91045 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.