In our introduction to game theory we learned about the famous Prisoners’ Dilemma, in which two prisoners given the option to confess or not confess their crime, will always both confess, despite the Pareto Efficient outcome of both not confessing. This is because their dominant strategy is to confess as it will always provide them with a greater payoff.

This dilemma is seen in the real world in many situations. For companies choosing levels of advertising in a business in which the market is saturated, each company will spend a great deal of money advertising and split the profits in the same way that they would if neither company spent money on advertisements. However both companies will advertise, because like the prisoners, it is in their best interest to do so. No matter what the other company does, they are always better off advertising.

Recent concerns of climate change have created a political Prisoners’ Dilemma, in the form of governments taking action against climate change, or not taking action. Countries will benefit if climate change is prevented whether or not they help to stop it. A government can persuade other countries to take action, while doing nothing, and will reap the benefits. This free-rider problem creates a Prisoners’ Dilemma, in which countries tell each other how important it is to fight climate change, and curb emissions, but subsequently do nothing about it.

However, on the issue of climate change, it is a game that is played more then once. When we look at the Iterated Prisoners’ Dilemma, in which the Prisoners’ Dilemma is played as a repeated game, the results can change. Each time the prisoners can confess or not confess. But now there is a trigger strategy, or punishment strategy, by which if a prisoner confesses in one round, the other prisoner threatens to confess every round after. So each time the game is played after a confession, the result is that both prisoners confess in each subsequent game. If prisoners play this type of dynamic game, in which they play the game an infinite number of times or with some probability of the game ending each round, it is possible to achieve the Pareto optimal outcome of both prisoners not confessing. There is some critical discount factor by which if they discount their future payoffs, the sum of their discounted payoffs of not confessing is greater than then payoff of confessing in the first round, and then confessing each round forever after. If there is some probability of the game ending each period, the Pareto optimal outcome is also possible, as long as that probability is small enough for the expected payoff from not confessing each round with the probability of not playing again exceeds the expected payoff of confessing in the first round and each round after.

In his paper, “How to Save the Planet: Be Nice, Retaliatory, Forgiving & Clear”, Michael Liebreich applies the Iterated Prisoners’ Dilemma theory to the dilemma of countries’ lack of action against climate change. He explains that on the first round, all countries will not take action “on the grounds that others will solve it.” But when the players know they will play multiple times, they will begin to cooperate. They have an incentive to cooperate so as not to be punished by other countries in the subsequent rounds for their lack of action.

He cites Robert Axelrod’s “Evolution of Cooperation” (1985), a study that found “if you play a Prisoner’s Dilemma game, not once, but repeatedly, then what you are likely to see emerging is cooperative, rather than mutually destructive, behavior.” Axelrod created a computer program called, “Tit-for-Tat,” which “started each round by cooperating with its opponent, and then simply mirrored its opponent’s last move.” Axelrod found that the successful strategies that emerged involved being nice, retaliation, and forgiveness.

Liebreich describes the four strategies in detail:

· Be Nice. Start by cooperating, and never be the first to defect. Otherwise you have no chance of getting into the zone where you both cooperate repeatedly and rack up the best outcome over time.

· Be Retaliatory. If the other player defects, inflict a cost on him or her which is at least as severe – otherwise you open yourself to exploitation.

· Be Forgiving. If your opponent mends his ways after defecting, restore cooperation as quickly as possible, so that you can both get back to scoring highly on each round.

· Be Clear. Since there is no way to beat the Nice, Retaliatory and Forgiving strategy, if your opponent knows you are following it, there is no incentive for him or her to seek advantage – it will only destroy his or her score as well as yours.

Liebreich explains that because international climate change negotiations are much like an Iterated Prisoners’ Dilemma game, the game can provide insight for how countries should act to engender cooperation. He argues how and why “the US needs to start being Nice, Europe needs to learn to Retaliate, and the developing world needs to Forgive. All players bar Europe need to improve the Clarity with which they communicate their strategies.”

Although it provides a good framework for the Kyoto Protocol, the Iterated Prisoners’ Dilemma is not a perfect fit for the climate negotiations. Some flaws of the analogy are pointed out in an article in the Economist, “Playing Games With the Planet”. The article explains that in the real world, there are more then two players and governments can communicate and form alliances, complicating the dynamics of the game. Also, governments are not always consistent or rational in their actions. For example, most observers “assume that America’s policy on global warming will change in 2008, along with its president. And most countries’ willingness to act is presumably linked to the severity of global warming’s ill effects.” So the worse the climate gets, the more likely everyone will play.

Taking the media by storm is news of an online group named Anonymous and its efforts to debilitate the Church of Scientology. For those who haven’t been following the back-and-forth between Anonymous and the CoS, the former is a mysterious “hacker” group which – three weeks ago – posted this YouTube video threatening the destruction of the CoS. While the CoS trumpets Scientology as a legitimate religion, many consider it a “cult” and have accused it of brainwashing, crushing dissent, and infiltrating governments. The ongoing brouhaha is cause enough for excitement—but it’s even more fascinating to view Anonymous and the CoS as warring sets battling for control over communication, information, and social networks.

This article details some of the ways in which tech-savvy Anonymous has attacked the CoS. By executing denial-of-service attacks on the church’s website, clogging its phones with prank calls, and looping black faxes through its machines, Anonymous managed to temporarily hinder the CoS’s communication network. What’s more, Anonymous and sympathizers have taken advantage of online, information networks. They’ve done their share of Google bombing (linking the word “Scientology” to ridiculous or negative terms in search engine results), and they’ve voted anti-Scientology articles to prominence on sites like Digg.

Nevertheless, the CoS isn’t completely clueless when it comes to manipulating information networks. As the graph below from http://www.operatingthetan.com/google/ shows, the CoS has long taken advantage of Google’s PageRank system to link among its own domains and boost pro-Scientology sites in search results.

Not to be discounted are both groups’ efforts to influence people through social networks. The CoS counts Tom Cruise among its faithful and maintains a celebrity center for its more glamorous adherents. By wielding celebrity influence, the CoS probably hopes to benefit from affiliation closure and the power of Gladwell’s Connectors; however, as ninjaspleen pointed out in this post, the influence of such Connectors may be grossly overestimated. People may even resent blatant manipulation by popular nodes (as evidenced by backlash against Tom Cruise’s behavior in recent interviews).

For its part, Anonymous takes the completely opposite approach. During its worldwide protests of the CoS on February 10^th, most protestors wore masks, scarves, and sunglasses. Their message is clear enough: countless indiscriminate nodes united in a cause are powerful too. Anonymous’s YouTube video even states, “We are legion.”

So far, Anonymous appears to be ahead in the media fight. As both groups continue to manipulate networks to spread their own ideas in their own way, it will be interesting to see which tactics win out.

Prior to my attending Cornell I worked as a real estate broker in Washington state. So, during the lecture on strong triadic closure I kept thinking about how the idea of one individual (node) with a strong relationship to two other people (edges) will then almost automatically create at least a weak relationship between these other people, who may have otherwise never met. This concept is a great model for referrals that members of the Real Estate industry (Real Estate Agents/Brokers, Mortgage Loan Originators, Home Inspectors, Title Reps., Contractors, and R.E. Attorneys) receive from past clients that they have built strong relationships with. Other than a few old school hard sales specialists (You can think of them as used car salesmen) any member of this industry will tell you that referrals are how they stay in business.

With the development and mainstreaming of the internet many members of the Real Estate industry (especially real estate agents) have found it more difficult to make a living because they are no longer the center of all information. In the past real estate agents were the sole available source of information on property information and so people were forced to seek out agents and make all the effort in developing relationships. In today’s world consumers have into the millions of sources for this same information via the internet. This expansion of availability to information and the real estate agents reactionary activity of trying to hoard information has led to the weakening of the agents importance.

Today we stand at a crossroad for the real estate agent, we will either see the death of this century old profession due to their insistence in taking part in information hoarding activities or the rebirth and resurgence of their roll. Due to the vast size of agents social contacts they can play the role of “great gate keepers” interconnecting multiple social networks by freely distributing information of not only a real estate nature. They can be again the “go to guy,” for information on job openings, area demographics, contractor ratings, and other service providers. How can they do all this you ask? Buy developing online social networks were they can build relationships faster in with more people. It seems as though some have moved in this direction with growth of RE social networking sites like Active Rain. But, to this point these opportunities have been under utilized. It will take more than having a blog site or internet business card agents call their websites.

 http://home.uchicago.edu/~syverson/realestate.pdf

I’d like to point out five very exciting articles / links that people should definitely check out:

1. Finance / Investing: Researchers from Harvard Business School have found that portfolio managers do better when they invest on firms they have personal connections with (went to college / grad school with). In fact returns on ‘connected’ investments were better by huge magnitudes, upwards of 4-8%. You can find the paper here, and there’s an interesting discussion + video here.
2. Entrepreneurship: Researchers from Harvard Business School found “… that an individual is more likely to become an entrepreneur if his or her co-workers have been entrepreneurs before”. A good case for homophily or its converse effect. See the paper here.
3. ‘Socializing’ Search: One of the great early advantages of Google’s search technology was Pagerank. It considered hyperlinks as votes for popularity, and thus created a massive ranking of web pages that didn’t rely on page content. Now people want to use social network information (the kind that we see in Facebook) to augment web search technology: Pages your friends like might be pages you like yourself. Check out the MIT Technology Review article here.
4. Internet Structure and Robustness: For Dubai and many other places, the internet shut down on January 30th, 2008. Who to blame? A ship cut through a critical fiber optic cable. The resulting blackout was, not surprisingly, devastating for the area. Oddly, the internet was originally designed for robustness against failure (ala nuclear threat from soviet russia). See the news article here. People could discuss how this relates with bottlenecks, betweenness, and policy issues such as net neutrality.
5. Palantir and Combating Terrorism: jerseygirl15 points out the networked nature of terrorist cells. One might also argue that analyzing network structure (say within the telecommunications network — phone calls) could reveal information about who might be a national security risk. Ethical and legal issues are definitely well noted.. And of course, the government is definitely interested in such analysis. One company that creates such software is Palantir Technologies, a startup based in Palo Alto. You can check out their website here. There’s not too much there in ways of product description, but this points towards a clear industry being built around analyzing graph data.

Here is some more detailed information + abstracts:

The Small World of Investing: Board Connections and Mutual Fund Returns

http://www.hbs.edu/research/pdf/08-055.pdf

We find that portfolio managers place larger bets on firms they are connected to through their network, and

perform significantly better on these holdings relative to their non-connected holdings. A replicating

portfolio of connected stocks outperforms a replicating portfolio of non-connected stocks by up to

8.4% per year.

Peer Effects and Entrepreneurship

http://www.hbs.edu/research/pdf/08-051.pdf

We find that an individual is more likely to become an entrepreneur if his or her co-workers

have been entrepreneurs before, or if the co-workers’ careers involved frequent

movement between firms. Peer influences appear to be substitutes for direct experience:

the effects are strongest for those without exposure to entrepreneurship in their family of

origin, and for those who have engaged in little inter-firm mobility themselves.

Social Search

http://www.technologyreview.com/Infotech/20138/

When the user enters a search query, results related to, produced by, or tagged by members of her social network are given priority. Lower down are results from people implicitly connected to the user, such as those relating to friends of friends, or people who attended the same college as the user […] each user gets a different set of results from a given query, and a set quite different from those delivered by Google.

Analyzing the Internet Collapse

http://www.technologyreview.com/Infotech/20152/

Multiple fiber cuts to undersea cables show the fragility of the Internet at its choke points.

Interesting, because the internet was designed originally for robustness; seemingly not the case anymore

In poker, there rarely are any pure strategies; almost all equilibriums are composed of mixed strategies. The question that must be asked is: how do you strategically play a hand with so little information? If poker was a game of perfect information, it would be very bland. For instance, if you knew exactly what cards would be dealt, and more importantly, what every other player was holding, nobody would ever play a hand. There are several solutions to dealing with the imperfect information. The first and most obvious answer is bet when you have a good hand and fold when you don’t. However, even bad hands sometimes can strike it big if the right cards come on the board. Likewise, the best hands can get occasionally busted by a lucky opponent. This leaves you with the idea of the odds of winning a hand (which the best poker players can calculate quickly in their heads). But knowing the odds still does not give you an idea of how to play the hand. That answer comes in two parts: psychology and game theory.

The psychology part is pretty simple: if you can read your opponent’s body language to better gauge what hand he is holding, whether he is strong or weak, or whether he is scared or confident, you will have more of an idea how to strategically play the hand. For instance, if he seems scared, you may try bluffing him out of the hand. Vice versa, if he seems confident, he may be trying to bluff you out of the hand. So while being able to “read” your opponent is perhaps the most important aspect of poker strategy, it is not the only way to make decisions.

Game theory has several advantages in poker. Say, for instance, your strategy consists of this: bet when you have a straight or better, and fold when you have three of a kind or worse. Once your opponent discovers this, he will fold whenever you bet, and bet whenever you don’t in order to force you to fold. However, say that one out of ten times you were going to fold, you bet instead. Your opponent would most likely fold every time until he realized you changed your strategy. By mixing up your play, you are actually increasing your odds of winning the hand. Game theory would suggest that if your odds of winning a hand are exactly 50%, your optimal strategy would be to play exactly the same way: fold half of the time and bet half of the time. This way, not only will you give yourself a chance to win with the odds, but also a chance to win by mixing up your opponent and having him play improper strategy. The same reasoning applies if you are a 90% favorite or even a 1% underdog. If you are able to perfectly vary your behavior according to your stated odds, game theory is actually your optimal strategy, especially against experts who would be able to figure you out otherwise.

It may be hard to believe, but the moral of the story is that even if you are an overwhelming favorite, you are not best off by playing a pure strategy. Jason Swanson, a math expert examines a simplified version of poker and after much in-depth analysis, mathematically reaches the same conclusion: “You cannot win with the optimal strategy.” By playing a mixed strategy in which you randomize your situations to play in and your situations to fold, you will be able to maximize your expected payout and become a winner in the long run.

http://swansonsite.com/W/instructional/game_theory.pdf

            As we have begun discussing in lecture, networks can be viewed as the positive and negative relations between various individuals or groups. What happens when everyone in a network teams up against another group and forms a mass plan of destruction? You get a network of terrorists. The most studied terrorist network is that of 9/11, where there were nineteen hijackers who were all somehow connected to one another and who all had the same goal of mass homicide. Valdis E. Krebs worked on deciphering this intricate network and describes his findings in “Uncloaking Terrorist Networks”. Within this journal, Krebs expresses the significant role that this network played in finalizing the highly structured plan of the plane crashes. However, when attempting to uncover a terrorist network, numerous problems arise including: the lack of completeness (there are often missing nodes which investigators will never uncover), ambiguous borders (who is or is not considered part of the network), and the constant movement and revolution within these networks.  Nevertheless, Krebs was able to construct a fairly detailed representation of the network. His discoveries were quite astonishing. Within the network, the average distance between two hijackers was 4.75 (which is rather high). However, certain shortcuts and secret meetings which occurred in Las Vegas before the attacks decreased this length to 2.79. This information relays an important aspect of terrorist networks. Commonly, these networks have a spaced out operational network, a larger administrative network, and distinct leaders. By having a more spread out network, Bin Laden ensured a sense of security inside the network. In order to make sure that the plans got carried out despite these sparse connections, there was an administrative network creating shorter paths between the hijackers. The hijackers trusted each other because they all had past relationships from their training camp in Afghanistan (however, these past associations remained rather suppressed, ensuring that the network stayed dormant).This sense of trust and administration enabled the terrorists’ plans to be successful.

               As these networks develop, a primary leader typically arises. In this case, Mohammed Atta (note the green square in the center of the image) arose as the leader, having twenty-two connections to other nodes. Atta became the gatekeeper or bridge, controlling where and to whom information traveled. His central position and proximity to others gave him access to outside information. This enforces the notion of the ‘strength of weak ties,’ where the most valuable information can be exchanged by people from otherwise unconnected social networks. Atta was provided with this tremendous power, but even if he was removed from the network, there were numerous other people with connections who would be able new to arise as new leaders. This is quite significant in a terrorist network; in order to disturb the entire network, multiple highly connected targets must be simultaneously eliminated before new leaders arise. This provides terrorist networks with the strong ability to resist attacks.

              Thus, it is clear that there are numerous facets contributing to a clandestine network. While in typical networks, strong ties are quite prominent, in a terrorist network, the strong ties are rarely activated, and therefore, appear rather weak. This enables the network to remain hidden and difficult to detect. The hijackers made few connections outside their network, maintaining the secrecy of the group. While one cluster did center around the pilots, and therefore, it became more susceptible to disruption, the overall network was rather successful in creating discrete ties with numerous layers in order to ensure that the final plan would be able to be completed.

Below is an image of the network created by Valdis Krebs (notice the more dense network around the pilots):

For more information on terrorist networks, one can read the New York Times Magazine article entitled,  “Can Network Theory Thwart Terrorists” or visit John Robb’s (author of Brave New War) weblog  on “The Optimal Size of a Terrorist Network.”

In The Tipping Point by Malcolm Gladwell, the idea that there are certain people can be the central point of the “outbreak” (if you would call it that) of trends. These so-called “influentials” make it so that companies need not spend money on advertising to popularize their product(s), granted that these “influentials” use the product(s) as well. Basically, “Reach those rare, all-powerful folks, and you’ll reach everyone else through them” (FC).

However, not everyone takes what Gladwell writes to be entirely true, especially one Duncan Watts, a network-theory scientist, who has run several computer simulations testing the idea of “influentials”. Watts found, however, that in most cases, it was not highly-connected people who was at the center of a outburst, but rather, an “average Joe.” Even upon changing the number of connections making the expected “influential” 10 times more connected than before (thus making him 40x more connected than an “average Joe”). This increase still did result in the expected “influential” being (indeed) more influential than the “average Joe”. The answer lay not in the number of connections, but rather the strength of them. According to Watts: “If society is ready to embrace a trend, almost anyone can start one–and if it isn’t, then almost no one can.”

I thought this was an interesting article given “The Tipping Point” is a required reading, and also because it brings into play some of the ideas we’ve talked about in class. That is, that the weights on a link between nodes (be it positive, negative, strong, weak or anything inbetween) are just as important as the connections themselves. Of course, I am a little confused as to why someone with MANY links wouldn’t have very strong links as well. However, I suppose it could make sense that a very connected person would be too busy to take the time to influence ALL the people they’re connected with, thus making the links effectively weaker. An “average Joe” person may have relatively few links, but these could be seen as a few close friends, probably, who take to heart what this “Joe” says and are thus more easily influenced by the trend he has picked up on.

I did think it odd, however, that the article stated that “the problem with viral marketing is that the disease metaphor is misleading”. Basically that, “influentials” aren’t as Gladwell thought they’d be (according to Watts) being trends are not as like epidemics as we might think. I find that this rejection of the epidemic-comparison is not necessary as there are people who are more susceptible to catching a virus or bacteria more than others and vice-versa. As long as people are diverse in both their biological history and their ideological ones, there doesn’t need to be a rejection of the idea of trends as a disease.

FC: Fast Company.com Is the Tipping Point Toast?, by Clive Thompson

Another article about pretty much the same thing:

Tipped over: social influence “tipping point” theory debunked, by Julian Sanchez

How many people have made friends from a common interest? Whether it is a common sports team, the same class schedule, or even neighbors, friendships form from close contact and common interest. But most recently, massive multiplayer online games have risen with a vastly increasing fan-base. It is becoming easier and easier to meet people you have never seen before. In some cases, meeting people online is easier than in real life because the social tension is not there; looks and body language play little part in the friendship link forming. In his article, Matt Slagle(http://www.usatoday.com/tech/gaming/2007-11-23-social-games-online_N.htm) of the USA Today, reports of a woman playing a game Kaneva(http://www.kaneva.com/?loc=interstitialskip) for the sole purpose to socialize. And this game is vastly dwarfed by other games such as World of Warcraft (which has millions of players playing at any one time), XBOX Live (various games such as Halo 3, Guitar Hero, etc), and the list goes on and on. Also, all of these games have the ability for someone to “friend” another player, creating a physically traceable network. The relevance of class topics (triadic closure and strength of ties) is definitely seen in online gaming networks. For example, if one person gets an invite to a party with more than one person (say in Halo 3) and he accepts, the property of strong triadic closure says that a weak tie will develop between this new initiate in the party, and the existing members (given that a strong connection will develop within the new member and the person who invited him). Not only does friendship come easily in gaming, but also competition within a network form. Rivalries between parties or groups can arise, just as rivalries in sports teams or cliques at school form. This increased competition and facilitated-friend-making only strengthen the video gaming networks increase in size. It’s probably not uncommon that in a decade or so, many young people will have almost as many friends on these networks as in their local friend networks. Also these gaming networks are able to be monitored and documented so that they could produce some insight into the topics covered in this class in the future.

Social networks are constantly in flux between balanced and unbalanced states. At the most basic level, a social network involves three individuals (or nodes) and the positive/negative relationships between them. The friend of my friend is my friend; the friend of my enemy is my enemy; the enemy of my enemy is my friend. These three clauses basically describe the balancing act that occurs within a triadic network. This being election year, the velocity at which this balancing of networks is occurring is at a fever pitch.

The specific example I’d like to talk about is the social triad of Ann Coulter, Senator John McCain, and Senator Hilary Clinton. We have a highly controversial conservative commentator, a candidate for the Republican nominee criticized by Coulter for not being conservative enough, and a female candidate for the Democratic nomination who is loved as much as she is hated. Although “enemy” might be too strong a word, all three individuals are connected by negative edges. This is not what would be considered a balanced network and some tinkering had to occur. As predicted by the idea of structural balance, one of the nodes “switched”. Ann Coulter announced that if McCain won the candidacy for the GOP, that she would bat for the other team and support Clinton.

The entire political process is this sort of balancing of triads. Candidates for their party’s nomination drop out and then back one of the remaining candidates, as Fred Thompson did for McCain. So what starts out as a playing field of several competing nodes and their supporters turns into two major components that end up fighting for the nomination of their party. Then the two components merge once the nominee is selected and competes with the other party’s nominee. Of course this is a very basic and abstract summarization of the political process, but it is interesting to see glimpses of our lectures within everyday life.

This morning I was having brunch with Paul Hyams, a few guests and some other students, a weekly event at Cornell. At one point during the conversation, Paul made a comment referencing the six degrees of separation, and I couldn’t help but interject in protest.

The 6 degrees of separation concept is probably the most prevalent ideas explicitly about networks in human (or at least English-speaking) consciousness.  It figures prominently in our first assigned reading from The Tipping Point, a national bestseller. It is also completely wrong.

This will most likely be covered in class, and is nicely covered by this blog post from last year’s class, so I won’t bother reiterating these arguments.

Still, this clearly demonstrates that popular culture does a terrible job of addressing networks. In this case, it overestimates the connectivity of the social networks. In neurobiology, it grossly underestimates it; claims that humans only use 10% of their brains have been thoroughly debunked, but people keep believing it. Snopes does a good job of addressing this one.

Of course, this speaks to how information is spread throughout networks. Information seems to spread based on how attractive an idea may be, without any consideration for its verifiability. What does that say about us, as nodes? Do we only pass on the titillating? The popularity of sites such as fark.com seems to say so.

For more information about the debunking of Milgram’s 6 degrees of separation, see the article on which this blog post is based. Or, see a former Info 204 student’s take on it from last year.

Read the rest of this entry »