The socialite game 
[Nov. 26th, 200911:09 pm]
Arvind Narayanan

Socialites are often famous for being famous. Although this description is used pejoratively, a variety of human activities center around social games where one gains power by associating with those who are already powerful. Power is defined purely in terms of the network of relationships, with no inherent measure of skill, quality or worth of an individual.
I will try to formulate this game mathematically. The hope is that the analysis will have some ability to predict and/or explain human social structures and behavior.
Consider a graph with N nodes or players. Players compete by creating or destroying edges in the graph. Mutual agreement is required for an edge to exist. Players have limited social capital, i.e., there is a bound on the degree of each node. All players have the same degree bound, which captures the fact that there is no intrinsic measure of strength of a node.
The goal of each player is to maximize their (relative) centrality in the network. This can be captured in various ways, but a natural measure is Eigenvector centrality, which is basically PageRank.
Unfortunately, as presented, the game is trivial because of the algebraic fact that the only Eigenvector with no negative values of the adjacency matrix of a regular connected graph is (1, 1, ... 1). Therefore socialites cannot exist—everyone is equally popular.
I see two main ways to make the model more realistic and make socialites possible: one is to make edges directional (and weighted.) This captures asymmetric power relationships between individuals, and enables hierarchical tree structures, among other things. The other is to remove the restriction that every player has the same degree bound. This would let us ask, "if some people have more social capital than others, can they leverage it to become vastly more influential?"
I played around with these alternatives for a few hours, but couldn't find what I wanted—a model that is halfway between the studies of game theorists such as a network creation game (which is too abstract to imply anything about human networks) and the techniques of social anthropologists, such as the well known 1977 Karate Club study by Zachary (which is not abstract enough to prove anything of general importance).
So I'm just going to leave this here on the off chance that it might inspire someone to take it forward.
[P.S. Two concepts that I think are important are stability and connectedness. A graph is kstable if no k players can collude to improve each of their scores. By connectedness I refer to the standard graphtheoretic concept; I think it is important to study which types of of initial conditions result in connected vs. disconnected social graphs, i.e., cooperative vs. competing power structures.] 

