Notes

Outline

SMALL W   RLDS: Raph Koster Creative Director Sony Online Entertainment Austin

What we’re going to cover Graph theory What are scale-free networks and why care? Social networks What is the structure of social networks? Game theory How do people in social networks interact? Pareto’s Law How does skill affect networks? Conclusions and recommendations Concrete advice. Bibliography Many many pages long!

GRAPH THE   RY

How do we get there from here? The Seven Bridges problem: can you walk the whole city but cross every bridge only once?

There is a path! Well, sort of. Leonhard Euler creates graph theory and proves that you can’t cross each bridge only once.

Mapping the Internet Paul Baran designed the preliminary network forms for the Internet. But it actually looks very different.

The Internet, 2001

The Internet, 2002

Random graph theory Paul Erdös and Alfred Rényi developed random graph theory.

Random graph theory If you take a set of nodes, like say people, and link them randomly…

Random graph theory …you end up with a complex graph where anyone can reach anyone.

Random graph theory As k increases (avg links per node) islands become rarer.

Six degrees of separation gets famous! The first appearance of “six degrees” (except he said 5) is in Hungarian writer Frigyes Karinthy’s story “Láncszemek.” The next was Stanley Milgram’s experiment in 1967, which found that the distance was actually 5.5. The term came from John Guare’s play from 1991 (and subsequent movie).

Strong ties Mark Granovetter did the early research on weak ties. In “The Strength of Weak Ties,” 1973, he found that strong ties tend to form triangles. Your two best friends likely know each other well.

Strong ties Mark Granovetter did the early research on weak ties. In “The Strength of Weak Ties,” 1973, he found that strong ties tend to form triangles. Your two best friends likely know each other well.

Weak ties vs. Strong ties In 1974 Granovetter’s “Getting a Job” found that you get most jobs from weak ties, not strong ones, because weak ties inhabit other clusters and therefore have different information.

Clustering Watts and Strogatz introduced the “clustering coefficient”. It is the percentage of your cluster who are friends of each other. In a star network, the coefficient is low...

Clustering In a tight cluster where everyone knows each other, it’s 1.

Weak ties are more important Why Granovetter was right: weak ties bridge clusters. In the models proposed by Erdös, there are no clusters.

The power of hubs In a small world network, six degrees of separation exists because of hubs. Hubs are relatively rare, but they bridge multiple clusters.

The power of hubs Network analysis clearly shows the hubs of the terrorist cells responsible for the Sept. 11th attacks. One to a plane, with Mohamed Atta the likely ringleader.

The diameter of the network Albert-László Barabási, Réka Albert and Hawoong Jeong of U Notre Dame found a formula for degrees of separation.  The Web itself has 19 degrees of separation. A small diameter doesn’t mean it’s easy to find the right path to a given node.

Weak ties The best weak ties network on the Net is the IMDB and the Six Degrees of Kevin Bacon game.  Christopher Lee is #1 because he works in many genres. He bridges many clusters.

Insularity Note that a high k doesn’t mean that you are highly clustered. The highest k actors in IMDB are porn stars who all work with each other. They are an insular community.

The Erdös Number The math community uses the Erdös number to track proximity. Clustering is a sign of a highly evolved collaborative network. How advanced is the game industry?

Google Google searches by number of links to a site, hence its accuracy. It’s a “hub finder” device. This means that much of the web is effectively invisible.

SOCIAL NETW   RKS

Channel capacity Caring deeply maxes out at 12-15 people. Psychology calls this the “sympathy group.” This sort of thing is called “channel capacity” in psych.

Human channel capacity Robin Dunbar, British anthropologist, says that social channel capacity is correlated to the size of the neocortex, and arrives at a figure for humans of 147.8. The average # of members in hunter-gatherer tribes is 148.4. Functional fighting units are often scaled to be around 150 soldiers in size.

Channel capacity in online games Sure, enough, guild sizes show a “knee” at ~150.*

Guild distribution histogram A histogram shows it more clearly…

Guild distribution Pareto graph Using a Pareto distribution of the histogram, we can see that 60 seems an optimal size, and guilds over 150 are very rare.

Network resilience Scale-free networks are resistant to random node failures. As in, random node failures CANNOT destroy a scale-free network. Shlomo Havlin, Reuven Choen, Keren Erez, and Daniel ben-Abraham showed that to kill a scale-free network, it must have a power law exponent of less than 3. All significant scale-free networks found thus far have better than 3 for the exponent, and are therefore practically indestructible.

Destroying a scale-free network Hub attacks, as shown by Duncan Calloway of Cornell, with Mark Newman, Strogatz, and Watts, can kill a scale-free network in no time. However, it requires simultaneous removal (so that links do not have time to reattach elsewhere). The problem then becomes cascading failure. Cascades are not instant, Duncan Watts showed. There is a tipping point there as well. The initial failure may result in a catastrophe many times its size, a very long time later.

The Unknowable Map Steve Lawrence and Lee Giles of NEC Research Institute showed that the Web is too big to know. Search engines can only map a fraction, because from any given page, you can only reach 24% of the Web via linking.

A map of scale-free networks

A map of scale-free networks

“…because links are zero-sum games” This is a feature of all scale-free networks made of directed, non-reciprocal links, according to Sergey Dorogovstev, Jose Mendes, and A. N. Samukhin. Watts points out that friendships themselves are not symmetric; usually there is a superior/subordinate relationship. An acquaintance of lesser prominence is quicker to claim someone as a friend than someone of high status.

Homogeneity Cass Sustein, a U Chicago law professor, showed that linking tends to be homogeneous. Only 15% of political sites link to opposing political viewpoints, whereas 60% link to like-minded sites.

Segregation Schelling has shown via A-life simulations that a peaceful, heterogeneous community will segregate itself.

Segregation And this is with agents that LIKE mixed environments.

Segregation All he did was set it up so that neighbors would swap places to find two like neighbors.

Segregation Even if a given node only wanted ONE neighbor like itself, he still got segregation.

Genocide In mixed environments of simulated “racial tension” using a similar model to the above…

Genocide Epstein showed that genocide is inevitable.

Genocide A proportion of cops can stop the genocide, but you will still get “reservations.”

Genocide Even adding cops doesn’t help; it just delays the inevitable.

Confessions of an Arch-Wizard* *Written by Michael Lawrie, aka Lorry, for MIST back in 1991.

Preventing genocide Hammond has shown that unpredictable policing, high-profile, high penalty sweeps are a bigger deterrent to misbehavior than consistency.

Infecting a scale-free network In normal epidemiological research, there is a “threshold” value of penetration that a virus must cross in order to become epidemic. Some ideas are “sticky” and others aren’t. The principal reason something is sticky is because it fits into someone’s life. Research on Sesame Street versus Blue’s Clues found that narrative is “sticky.” Stories retain attention better.

But there is no threshold… In scale-free networks, there is no threshold for virii to cross, according to Pastor-Satorras and Vespignani, in Aug 2000. This is because of the hubs. You don’t need to know exactly who the hubs are—Zoltán Dezsö showed that ANY preferential treatment restores the threshold for infection. So if you’ve got something to sell, sell to those likely to be hubs.

Mavens “Mavens” are experts on areas of knowledge. The key researcher on Mavens is Linda Price of U. Nebraska. We see the future of the market in the reaction of the early, hardcore adopters. Persuade the early adopter and you get a huge market.

AIDS Gaetan Dugas, a French Canadian flight attendant, was Patient Zero of the AIDS epidemic. He had an estimated 2500 sexual partners.

Adoption curves Bruce Ryan and Neal Gross did famous diffusion studies on the adoption of a new breed of corn in the ’40s. They broke the categories into

MMO adoption We can see a characteristic adoption curve, which is also reflected in the MMO industry…

MMO adoption We just don’t know how far along the curve we are.

GAME THE   RY

Manipulation We are more likely to agree with something if we are nodding when we hear it. Very subtle cues change our minds on things. Much of this depends on physical characteristics. William Condon found “synchrony” in physical movement among people talking.

The Psychology of Persuasion Robert Cialdini identified six strong persuasive characteristics in humans: We like people who give us gifts We hate changing our minds We imitate those like us We’re suckers for those we like We trust apparent authority We overvalue rare things

Broken Windows “Broken Windows” theory: criminologists James Q. Wilson and George Kelling show that minor misbehavior triggers bigger misbehavior. New York City reduced crime by cracking down on graffitti and subway fare-beaters. This demonstrates the importance of the overall environment.

Stanford Prison Experiment The Stanford Prison Experiment, done by Zimbardo et al. in 1971, showed that people become their roles and indeed act quite atypically.

The Fundamental Attribution Error The Hartshorne and May experiments on cheating show that honesty is not in fact inherent. It’s situational. In psychology, this is called the Fundamental Attribution Error. Humans always overestimate character and underestimate circumstances.

Peer pressure You follow the trendsetters. Look at our cultural zeitgeist. People are shaped by their peer group, not by authority figures.

And then you get Game Theory John Nash showed that with bargaining, all competitors can come out ahead even in zero sum games. But our zero sum games do not have bargaining.

The Prisoner’s Dilemma In the Prisoner’s Dilemma, 2 guys are held for a crime, with no communication between them. Each is asked to rat out the other.If both rat out, they both get the worst punishment. If neither does, they get the least punishment. Given the lack of information, the rational thing to do is to rat the other out, which results in the maximum punishment for both.

Tit for Tat The optimal behavior is Tit for Tat, which calls for a history of iteration that the players are aware of (developed by Rapoport). 1.Be nice. (never be the first to defect) 2.Be retaliatory (defect if the opponent did last time) 3.Forgive! (if the opponent stops, you stop) 4.Be transparent (opponent can tell how you will behave) This works if the # of rounds is unknown, eg, there is an expectation of future interaction, as shown by Axelrod in 1984.

For once, human nature pays off… A team at Emory recently showed that reciprocal altruism appears to be hardwired into the pleasure centers in our brains. They also showed that knowing when the game ended undermined the altruism. They also showed that it only applies if you HUMANIZE the opponent.

EverQuest plane raids Looking at EQ plane raids: as the number of players competing for the exact same resource rose, complex rules of social standing and precedence started arising spontaneously.  The phenomenon of plane raids in EQ being "reserved" by guilds that are the size of your average mud's playerbase, for example. This is a direct, literal application of Nash’s work.

Human nature = anthropology Jared Diamond in Guns, Germs, and Steel breaks down social complexity into tiers based on population size.

Human nature = anthropology Jared Diamond in Guns, Germs, and Steel breaks down social complexity into tiers based on population size.

What drives cooperation? It’s not literal population that matters. It's economic participation. Social structures emerge when all those people are trying to draw from the same resource well (literally trying to extract more calories from the same amount of land).

Inconstancy Online games have a problem with inconstancy; players aren't economic participants 24/7. When logged off, they don’t consume resources or contribute to the economy. This probably retards social development.

Caloric extraction = earning XP? In GoP games at least, the thing that players work together to increase the efficiency of is the process of extracting more XP per hour. Camping is a direct analogue to agriculture! We used to hunter-gather the mobs, now we farm them... even the term "farming" has crept up in common usage), etc etc.

Reputation & the Lemon Problem The work of Toshio Yamagishi of Hokkaido U tackles the “Lemon Problem.” The seller of a used car knows more than the buyer. A lemon goes for $10k, and a good car for $20k. They compromise on $15k through bargaining.  But good sellers will therefore stay out of the market (and only deal with those who trust them) because they want the price they deserve. The result is that the open market only has bad cars for sale.

Fixing online reputation In the real world, reputation helps resolve this. In online, the ability to change your identity negates it. Tracking negative reputation starts out good, then crumbles over time In open systems, the most advantageous strategy is Tit for Tat, e.g. a positive feedback after the fact rep system. Tracking positive reputation starts out bad but builds over time to be almost as good as a closed system

PARET   ‘S LAW

Pareto’s Law Vilfredo Pareto, Italian economist, found power laws everywhere. 80% of Italian land was owned by 20% of the population. 80% of money is held by 20% of the people. 80% of links point to 15% of websites, for example.

Where does fun flow? Picture a zero-sum game…

The Rich Get Richer Nodes have fitness. The rules for link addition developed by Barabási et al show that the phenomenon is basically “the rich get richer.” In Model A, Erdös graphs, links attach randomly. But in Model B, they prefer to attach to nodes with links already

City sizes The curve has been invariant since 1900’s census.

Game sales NPD tracked sales for the 1st half of 2002. The curve is also invariant.

Subscription market Can we predict new game sizes?

Let’s talk physics… Physics shows that when power law distributions arise in molecules, we get “phase transitions.” There is a tipping point where chaos transitions to order.  Kenneth Wilson won the 1982 Nobel Prize in Physics for showing this.

Stagnation Luis Amaral, Gene Stanley, Antonio Scala, and Mark Barthélémy show that if nodes don’t get new links after a certain age, the network will cap the hub size. And José Mendes and Sergey Dorogotsev showed that age can affect a node’s fitness (odds of acquiring a new link). This also affects hub creation.

Fitness distribution But fitness distribution also follows a power law. The odds of attaching to a node obey a formula that depends on the number of links the node already has, and how fit it is at acquiring new ones.

Bose-Einstein condensation Networks remain balanced between chaos and order as long as preferential attachment and growth are present. But remove growth and what you get is a term from physics: Bose-Einstein condensation. Also known as “monopolies.” In other words, in some networks, it is possible for the fittest nodes to grab ALL the links.

A monopoly Graph of OS market share

Online game popularity Is there any point to the shooter market?

Commoditization Pennock, Flake, Lawrence, Glover, and Giles at NEC have a formula that predicts the attachment of new links to a scale-free network accurately. The amount of rich-get-richer that occurs varies per e-commerce category.

Commoditization The degree of commoditization of the goods/services sold is what drives stasis:

Talent Fitness of nodes for link acquisition also follows a power law distribution. We can call this “talent” if we like.

Tiger Woods Total scores in 1st 22 championships, 81 under par. Jack Nicklaus, 40 over.  In 11 majors, Tiger won 7. In other words, 2 times out of 3, Tiger got the trophy, and the rest of the time, the rest of the field squabbled over it. As Nicklaus said, “He’s playing a game I am not familiar with.”

Babe Ruth In 1921 Babe Ruth by himself hit more home runs than ½ the teams in the league.

Wayne Greztky In 1981-82, Wayne Gretzky scored twice as many points as the 2nd highest scorer in hockey.

Michael Jordan Jordan’s average points per game is 31. The runner up was 25.

Secretariat Secretariat won the Belmont Stakes by 31 lengths.

Bobby Fischer Bobby Fischer in the 1971 elims at the World Chess Championships, in a game where 80% of tournament games are draws. He beat 2 guys 6 games in a row each. He had 20 straight victories vs the best players on the planet.

TinkerBoy The #1 playerkiller in UO had 14,000 murders, versus a measly 2000 for the runner-up.

Welcome to the condensate Assuming there PARITY of fitness, persistence, and freedom of choice to create preferential attachments, Bose-Einstein condensation will start to occur in all systems where there is no possibility of competitive innovation.

Implications for skill-based games This has been observed in persistent team-based games, where the realm, faction, or side with the most victories is switched to by members of the losing side. This is why online-skill based games kick most people’s ass and they don’t play. Fortunately for our market space, EA, despite selling 1 in 4 games sold, does not have a lock on innovation. J

CONCLUSI   NS

Conclusions Online worlds are susceptible to social network analysis.

New markets Seek out the mavens. They provide the word of mouth. If you do not make them happy, NOBODY will be happy. Stated another way: you can’t get to the mass market unless you go THROUGH the hardcore. The hardcore guys hang out on Waterthread, Player2Player, UnknownPlayer, and Usenet. Get to know them. Plan to sell to them.

How do we hook newbies to hubs? It’s HARD to find the hubs, as a new player. You need to hook them up as quickly as possible. Weak ties are best. We should be encouraging acquaintances, not bosom friendships. Matchmakers are a good idea. Multiple guild membership is also a good idea. Ticklers for acquaintances are also a good idea. Ready-made groups are mostly a waste of time.

Are you vulnerable? You could probably kill off another game by persuading all its guild leaders to switch to your game simultaneously. Offer ‘em free accounts. Conversely, don’t expose who your hubs are to competitors.  Certain types of ladders are dangerous things to display publicly! You want them to stick with your game. It makes good business sense to offer incentives to hubs.

Critical mass Be sure you have critical mass, because otherwise, your game will never die, and you may be stuck with something unprofitable. And if you do shut that down, tit for tat behavior means those people will snub you.

Predicting the market We can probably predict the sizes of online games by asking, “bigger than X but smaller than Y” I also like to do a Google search and just compare the number of hits for upcoming games.

The death of online? If too many games stop growing, the size of the largest games in the network will be capped. The more similar the experiences and services that are provided by the games, the more likely we are to end up with monopolization of the category. And also with a lack of growth in the genre’s audience.

Skill based games If your game is zero-sum skill based, that will cap audience size right there. Skill based games on the Internet will never be huge, even with leagues. You must find some way to overturn the rich get richer scenario in all games with some form of accumulation. There must be not just drains, but occasional catastrophic behaviors that topple the 20% at the top of Pareto’s curve, so that others get a chance.

Treadmills In other words, treadmills are not only good, but necessary. What’s more, the more different treadmills the better. Get parity in one area even if you cannot have parity in all of them. Provide “powergamer” style recognition to as many arenas of the game as possible.

Customer relations aka manipulation We don’t have physical cues online. So get the best goddamn writer you can find; they are the public face. Make sure it’s a politician, someone versed in the art of persuasion. Always present a human face, not a corporate one. You want someone that people see as similar to themselves.

Broken windows If you create a setting where cheating is possible, everyone will do it. (Duh). Crack down on tacky names, petty crimes, etc, before you crack down on big cheats. Never publicize behaviors you don’t want repeated. Always publicize behaviors you want imitated.

Playerkilling Given an aggressive group, kick them out of your game. Otherwise, they will dominate via genocide. Police inconsistently and with high profile. Occasionally banning an entire guild, etc. Stick to the rules, of course. But do “raids” on the bad guys.

Reputation systems Make sure that players have a reasonable expectation of future interaction. This means persistence of identity and limited mobility. Use a positive feedback rep system, not a negative one.

Social structures Your guild structure had better support 150 comfortably. You need interdependence, so that groups do notably better than soloers. You want economic participation 24/7 as much as possible. Let players play while offline, make them pay in game currency while offline.

Reaching your audience The only way to fully map your game’s community is to get feedback from 100% of them. Expect to miss people. Start up SIGs for the different communities you want to reach. Try to notice all the “islands.” We DO need to lick the “story problem” in online games.

Homogeneity There’s a natural tendency to homogeneity that works against weak ties. Encourage systems that cross “cultural” boundaries. Don’t be disturbed to see groups segregate themselves. Provide them with alternate means of self-identification so they can join more than one community at once. Don’t let your microcommunities get too big.

In the end… The single biggest thing you can do to improve your online game community is to increase the bandwidth of s  cial interacti  n.

THE RES   URCES

Bibliography Barabási, Albert-László. Linked: The New Science of Networks. Perseus, 2002. Baron, Jonathan. “Glory and Shame: Powerful Psychology in Multiplayer Online Games.” GDC 1999 Conference Proceedings. Also at http://www.gamasutra.com/features/19991110/Baron_01.htm Buchanan, Mark. Nexus: Small Worlds and the Groundbreaking Science of Networks. W. W. Norton, 2002. Buchanan, Mark. Ubiquity: The Science of History… or Why the World is Simpler Than We Think. Crown, 2000.

More bibliography Cialdini, Robert B. Influence: The Psychology of Persuasion. Quill, 1984. Diamond, Jared. Guns, Germs, and Steel. W. W. Norton, 1997. Diamond, Jared. The Rise and Fall of the Third Chimpanzee. Vintage, 1992. Fritzke, Bernd, et al. “Growing Self-Organizing Networks.” http://www.ki.inf.tu-dresden.de/~fritzke/research/incremental.html Garton, Laura, et al. “Studying Online Social Networks.” Journal of Computer-Mediated Communication, June 1997.

Even more bibliography Gladwell, Malcolm. The Tipping Point. Little, Brown, 2000. Hafner, Katie, and Lyon, Matthew. Where Wizards Stay Up Late: The Origins of the Internet. Simon & Schuster, 1996. Kim, Amy Jo. Community Building on the Web. Peachpit press, 2000. Krauthammer, Charles. “The Greatness Gap.” Time Magazine, July 1, 2002. Krebs, Valdis. “Social Network Analysis of the 9-11 Terrorist Network.” 2002. McElvaine, Robert S. Eve’s Seed: Biology, the Sexes, and the Course of History. McGraw-Hill, 2001.

Yeah, still more… Munger, Charlie. “The Psychology of Human Misjudgement.” Speech at Harvard University, June 1995. Pennock, David M., et al, “Winners don't take all: Characterizing the competition for links on the web”, Proceedings of the National Academy of Sciences USA, Vol. 99, Issue 8, 5207-5211, April 16, 2002. Powazek, Derek M. Design for Community. New Riders, 2002. Rauch, Jonathan. “Seeing Around Corners.” The Atlantic, April 2002. Sellers, Mike. “Creating Effective Groups and Group Roles in MMP Games.” Gamasutra, Sept. 2002.

Honest, last page of bibliography Stewart, Thomas A. “Office Behavior: Why Can't We All Just Get Along?” Business 2.0, July 30, 2002. Watts, Duncan J. Small Worlds: The Dynamics of Networks between Order and Randomness. Princeton University Press, 1999. Wilson, James Q. “Thinking About Crime.” The Atlantic, September 1983. Yamagishi, Toshio. “Improving the Lemons Market with a Reputation System: An Experimental Study of Internet Auctioning.” Hokkaido University, May 2002. Zimbardo, Phil, et al. “The Stanford Prison Experiment.” http://www.prisonexp.org.

Special thanks Special thanks to Will Wright, Patricia Pizer, and MUD-Dev members Jeff Cole, Dave Rickey, and Paul Schwanz for clarifying my thoughts on this. To Michael Lawrie for permission to quote from “Confessions of an Arch-Wizard.” And to Kristen Koster for being a sounding board and visual design help. Raph’s Website: http://www.legendmud.org/raph/gaming