I thought that I would supplement the game theory portion of this class with some ideas that I learned in Econ 367. In this class, we have had a brief introduction to game theory. We have covered Nash equilibria in pure and mixed strategies in various games, such as the Prisoner’s Dilemma, Battle of the Sexes, and even in professional soccer. However, in each of these cases, we only considered the game being played once – the players choose their strategies, receive their payoffs, and then they walk away. What if the players play the game over a series of rounds? How would the players’ actions in the current round affect their actions in the next round? For instance, in the Prisoner’s Dilemma, would playing the game repeatedly somehow change the Nash equilibrium from (Don’t confess, Don’t confess) to something more socially optimal?

To answer this question, we need to make a distinction between finitely repeated games and infinitely repeated games. If a one-shot game is played for a finite number of rounds, then it turns out that the result in each round is the same as the result in the one-shot version. In other words, if two players play the Prisoner’s Dilemma for exactly N rounds, and they both know what N is, then they will each play (Don’t confess, Don’t confess). You may have hoped that the fact that the game is repeated allows one player to punish another in the next round for not playing Don’t confess. If this were the case, then the players would play (Don’t confess, Don’t confess) in each round, which would be socially optimal. To see why this plan breaks down, we use a technique called backwards induction. Consider round N. There are no future rounds, and so if player A plays Confess, then player B cannot punish him in the next round. Therefore, A will play Confess, since it is a best response. Knowing this, B will also play Confess in round N. Since each player knows that the other one will play Confess in round N, they will each play Confess in round N-1 as well. We continue backwards until we reach round 1, and we see that the players will have decided to play (Confess, Confess) in each round.

However, if the game is instead infinitely repeated, then the results can change drastically. Suppose that both players play a Trigger strategy, which means that each player will start off playing Don’t confess. If at any point he sees that the result of a previous game was not (Don’t confess, Don’t confess), then he will play Confess forever after. Otherwise, he continues to play Don’t confess. The joint strategy (Trigger, Trigger) then constitutes a Nash equilibrium. If both players cooperate and play Don’t confess each round, then they will each get a stream of high payoffs. If one of them deviates, then he will get a high payoff in that round, (since he plays Confess while the other player plays Don’t confess) but will get a low payoff in every round afterwards. The threat of punishment is quite severe – trying to cheat now will hurt you tremendously forever into the future. Therefore, if a game is played infinitely, then the players can achieve a socially optimal outcome.*

In the context of networks and graphs, it may be worth asking if the concept of infinitely repeated games can be applied to road networks. After all, a highway system, if formulated as a game, does not seem like it would be one-shot, since people travel on a fairly regular basis. One way to formulate an analogy could be as follows. We should all choose routes so that the total travel time for everyone is minimized. If you selfishly choose a route that decreases your travel time at the expense of others, then some other people will move over to the route that you have chosen, thus punishing you by increasing your travel time. Note that like in the infinitely repeated Prisoner’s Dilemma, this requires that the players be willing to suffer while punishing someone else. Realistically, I would not expect such a situation to arise. People punishing other people for violating social norms certainly does happen, although I would expect people on a highway to just honk their horns and shake their fists.

http://www.cs.cornell.edu/timr/papers/routing_full.ps

Here is a link to a paper about routing networks and selfish behavior, which was co-written by Prof. Eva Tardos. I have only written some of my own thoughts and speculation as to how infinitely repeated games could be applied to what we learned in class, and the paper is just extra reading for those who are interested and don’t mind some more mathematical material.

*Note: If one of the players does not value his future payoffs at all, then he will not be deterred from deviating and playing Confess.

As any employer who gives his employees medical benefits can tell you, the price for prescription drugs can increased astronomically over the last 20 years. The number of filled prescriptions grew at an alarming rate; going form 13m prescriptions filled in 2002 to 22m filled in 2004 (What goes into the costs of Prescription Drugs?, Phrma org. PDF June 2005). Most Americans cannot afford to pay for the increasing number of prescription drugs they need as they get older, so medical insurance agencies foot the ever increasing bill. And since insurance costs go up, most people can only afford insurance through their employer. While for a long time American companies were able to easily afford a medical coverage plan, the increasing prices of the last decade dramatically hurt the bottom line of many corporations both large and small. The famous example is General Motors. Whose generous medical plans won decades earlier by the unions, now cost the company so much money that GM spends more money on health benefits for retirees than it does on steel for its cars (http://www.sfgate.com/cgi-bin/article.cgi?f=/c/a/2005/06/08/BUGKAD4U481.DTL). In short, the increasing cost of prescription drug prices is stifling business and leaving more and more Americans every year without health insurance.
So how does this problem relate to the topics discussed in Econ 204? In class we have looked at how networks grow from just a few nodes to hundreds more depending on the nature of the network. What we have not seen so far is how a network “unwires” itself. How a network loses nodes and grows ever smaller. It seems to be a paradox that as the healthcare industry is growing in terms of dollars spent, it is shrinking with the increasing number of American businesses canceling their health insurance policy. Ties between the medical insurance companies (sellers) and the everyday American companies (buyers) are breaking. Some ties are so strong from cooperation over the years that they cannot break, such as GM from their health insurer, unless restructuring is done. This unwiring of the network continues everyday, but recently some employers are trying a new tact on how to lower their medical expenses.
In a recent New York Times article, some employers are now giving free prescription drugs to employees (http://www.nytimes.com/2007/02/21/business/21free.html?hp=&pagewanted=all). They are doing this for two reasons. First is that employers know that if employees take their medicine like they are supposed to, most major and very expensive long-term complications can be avoided; saving the company a lot of money. The second reason is that employers are hoping to strengthen the ties between employees and their doctors. The companies know that this stronger tie will cause people to go to their doctor more often so that future problems can be detected early and avoided. If successful, this new method of combating high medical prices for companies will re-wire Americans to the medical network with stronger links between patients and their doctors, increasing the overall welfare of the American populace.

http://www.siliconvalleywatcher.com/mt/archives/2006/10/cisco_telepresc.php

Cisco has recently started to move away from their main business of routers and switches and more into facilitating the building of human networks. One of their newest technologies is Teleprescence. This is a $300,000 system that comes with three 65in high definition TVs. What this allows is next generation video conferencing. The fault with the current generation of video conference is the low resolution that does not make it appropriate for important meetings. Cisco claims that 60% of all communication is body language which is lost in regular video conferencing.

This causes many of the upper managers in global companies to spend a good portion of their time catching their next flight instead of doing work at the company. This puts them in a spot of less power in the social network of the company, when they should have more power. In addition if the manager is responsible for groups in India and England, and the US, and splits his time flying between the different groups, he now has less power in all three social networks. This new tool allows him to spend more time with the different groups, and have more follow up meetings with clients all over the world, so putting him in a spot of greater power in client networks as well.

A good example of what this would be the T from class. Let’s say that we have 5 nodes at the top and 2 on the vertical. We’ll called the A,B,C,D,E,F,G. Node C is the manager, however he does not have power in this relationship. Lets say that nodes A,B are in the US, DE are in India, and FG are in England. When he visits the US he only meets with B, D in India, and F in England, because he doesn’t have time to meet the other nodes. This put him in a position of little power, and nodes B,D,F of weak power. However, now with Teleprescence he has more time to meet with nodes A,E,G, giving him greater power.

A group of researchers have developed a system to make accurate predictions on the network performance between two arbitrary computers on the Internet. In the paper (Google HTML version), they define iPlane, a system that, in addition to doing simple tests on round-trip latency and throughput, accounts for the actual network topology. Such a system has many possible uses for P2P networks and distributed services. For example, the Coral Content Distribution Network could use this data to make sure that each client trying to use the service gets routed to the node that gives the best connection. One of the people involved with the paper, Tomas Isdal, wrote his master’s thesis on the use of the iPlane system to enhance the performance of BitTorrent. Normally, a BitTorrent tracker will only return a random subset of the peers it knows about when queried by a peer. The modified version returned a list of peers that was half chosen at random and half peers thought to provide the best throughput by the iPlane system. This resulted in a dramatic increase in performance: the time it took for 80% of the peers to complete their downloads was reduced by about 20-25%.

This system relates to the graph theory we have covered in class because it involves identifying clustering in a (very large) graph of interconnected routers and clients/servers. Such knowledge could be very useful on a network like Cornell’s because of the incredible amount of intra-campus bandwidth available compared to the connections to outside campus. If Cornell was running a Coral node, and many people on campus were trying to acquire a file using the Coral network, they would all be directed to the one located on campus, which would fetch the file only once from the greater internet and then serve it to all the computers on campus that had requested it.

BitTorrent itself also constitutes a kind of trading network. The rules are less rigid, but the algorithms used to choose who to upload to depend heavily on who is most willing to upload to the peer. In essence, while nodes are not restricted nearly as much in the number of nodes they can trade with and “freebies” are occasionally given out, nodes will consistently choose to trade with the node that gives them the best deal: in this case, the fastest download.

Most people who use any of the mainstream search engines have at one point or another probably come across a search that returns rather strange, often comedic results. Examples of these are searches such as ‘miserable failure’ which, for quite some time, returned as the top result, a link to the white house biography of George W. Bush, and ‘french military victories’ which returns as it’s top result a fake google page that asks whether you might have been searching for ‘friench military defeats’. In days gone by, when web search was a simple matter of returning the pages containing the most instances of a given word, acheiving results like this took a far different approach than it does today.
The concept of a Google Bomb is relevant to our study of netowrks because most mainstream search engines currently base results on an analysis of the link structure of the web. The idea behind this stems from the thought that a web page, call it ‘A’, is a good result for some query, say ‘b’, if a lot of other web pages link to ‘A’ with a link named ‘b’. Intuitively this makes sense because this way a web page is essentially peer-reviewed by other web pages and is only a good result if other web-pages (people who write pages) consider it a good page.
Google Bombing is a practice that exploits this fact to alter search results. Basically, to make a Google Bomb i.e. to cause a search for’a’ to return page ‘B’, one must simply add links from a lot of other pages to ‘B’ with the link name being ‘a’. This way, when Search engines run their ranking algorithms, they will think that ‘B’ is a good page to display as a result for ‘a’.
While generally this is not a major issue and most major search companies have chosen to do essentially nothing to combat Google Bombs, they are interesting in that they demonstrate how search engines actually rely on the graph structure of the Web to generate results.
See this article for more specifics on Google Bombs. Here is Google’s explanation of their PageRank Algorithm. Google also recently somewhat restructured their search algorithm in order to diffuse many Google Bombs that other search engines still have trouble with. See this blog post from Google for more information.

http://arstechnica.com/news.ars/post/20060119-6016.html

In the past few years the world saw the advent of numerous sites devoted solely to promote social networks. Among them, the facebook phenomenon has helped this category of websites to propel from simple, frivolous websites for friends to keep in contact with one another, to means for advertisement and for companies, colleges and future employers to learn more about an individual. The latter usage for facebook can bring about dire consequences for college students looking for internships and jobs. The students seem to “dig their own grave” when they put unprofessional, obscene and offensive pictures and/or comments on their own facebook profiles, which may facilitate consequences from rescindment of a job offer to legal repercussions.

In class we talked about the strength of weak ties in social networks. The invention of social networking sites allows us to keep in contact with those we may never talk to again. The sites themselves have emerged to become something analogous to connectors and mavens and they effectively propel and catalyst the dissemination of information. When one joins such a site, he/she is instantly connected to hundreds of thousands of other users who visit the site, and in facebook’s case, most notably alumni and school mates.

This is where the problem surfaces. Social networking sites gives the users “the illusion that they are merely interacting with friends, when in reality much of their behavior is viewable by any interested party”. This becomes especially dangerous for job hunting students. In a recent survey in 2005, “three quarters of (recruiters) use online search engines to check up on applicants”. One large feature of facebook is on default, it allows individuals from the same network to access profiles of other members of the network. An alumni of the individual is then able to use their own .edu account to register a facebook account, and access what previously thought as private information regarding the individual. Let us now think about the idea of triadic closure. If the network was regarded as a very big node, connected to all members of the network. According to triadic closure, the two members then have an edge connected between the two, which seems to be the fundamental idea of facebook.

Upon further analysis, more signs of triadic closure exists in facebook. The settings that allow friends of friends to access your personal profile also abides to the theory of triadic closure. When three two random nodes have strong bonds with another node, it is likely that these two nodes will develop a weak bond. In addition, according to Kossinets and Watts, two nodes who share mutual acquaintances are more likely to establish an edge between themselves, hence effectively further complicating the social network. It is not hard to imagine then, the enormity of the social network embedded into facebook.

The aforementioned property further exacerbates the problem of online privacy. Without necessary consideration of the consequences a simple setting in facebook might bring, one may be unknowingly giving up his/her online privacy.

http://www.variety.com/article/VR1117959179.html?categoryid=2450&cs=1

The article “Technology hasn’t killed the collective viewing just yet” by Susanne Ault is about the social network Second Life (http://secondlife.com). Second Life is a free online community program created by Linden Lab that currently has 4.2 million registered users. In October of 2005, they had 600,000 members. This social network differs from the likes of myspace.com and facebook.com in that it is an interactive avatar based community. Instead of viewing website URL’s, users of Second Life load up the program and then gather together, almost like other computer games (i.e. – War Craft) While the user is interacting live with other live users, the difference between this game and others is there is no violence or chaos. In this three-dimensional virtual world, people interact with each other. They could trade goods and services, or even watch movies. The user just walks around and decides what they want to do, just like in real life. The question most have, is Second Life a fad or will it be around for a long time? Too find out, I signed up for Second Life almost a month ago and tested this metaverse. From my experience I feel that Second Life does have all the tools to succeed in the long run.

While some might be skeptical of this online universe, there is so much happening, that you could be logged on for 24 hours and only travel through roughly twenty percent of the network. Users can interact with other users and buy and sell items with Linden dollars, which translates into real money. So while this program might be viewed as a game, there is a lot of money to be made in this social three-dimensional network. As a user I can buy land and advertise anything I want. While there might not be enough users to warrant paying for advertising space, media companies beg to differ. Showtime bought acres of land so fans of the show “L World” could come together to talk and view clips of the show. Brands currently found in Second Life include Aidas, Reebok, and American Apparel. Other media companies are buying “land” to market their properties. CBS recently announced an investment of $7mm in Electric Sheep, a company that builds worlds in Second Life. All of these examples indicate that Second Life is not a passing fad, but here to stay.

http://www.nytimes.com/2007/03/02/business/02inside.1.html?_r=1&oref=slogin

http://www.time.com/time/nation/article/0,8599,1595967,00.html

In the first week of March, the Securities and Exchange Commission (SEC)
accused 14 people of taking part in a huge inside trading ring, allegedly
making illicit profits totaling $15 million. The 14 defendants supposedly
used information stolen from UBS Securities LLC and Morgan Stanley & Co.,
Inc. Both links are about the same ordeal, but there are some points that
are not overlapping between the articles, and so reading both will offer a
fairly clear picture.

The second link explains that the initial investigation began in response
to suspicious high-volume trading prior to the acquisition of Catellas
Development.  The investigation led to Eric Franklin, who has worked at
several hedge funds in the past few years.  The first link, however,
mentions that Franklin was actually tipped off by Mitchel S. Guttenberg,
an executive director in the stock research department of UBS. The trading
scheme had begun in 2001, when Guttenberg had gotten a hold of private
information about upcoming upgrades and downgrades of stocks. But the
information did not stay between only those two men. They each tipped off
other people, and a complex network of insider traders formed. But
eventually it all came to an end, thanks to the idea of networks.

As I’ve said before, there are two links covering the same story, but they
each have good points. Namely, both incorporate the idea of social
networks. In the first link, there is a description of the spread of
information between networks of tippees. This brings to mind Revere’s word
of mouth that the British were coming.  In the second article, there is
not much of a mention of the network of tippees, but it does mention
another network of people that are not at the moment accused of insider
trading. This network consists of “family members, friends, college
roommates and other social acquaintances.” The SEC plans to investigate
individuals within this network to extract more information.

The power of networks can be seen in such an example of an insider trading
bust. It is possible to imagine that Guttenberg and Franklin could have
gotten away with insider trading, if they were the only two involved.
However, by tipping others, and thus creating a larger, traceable network,
they were eventually busted. As for the network of individuals having
connections to the actual, formally accused defendants, this network can
be used to gather more information (and evidence) against the accused.
Even though Guttenberg and Franklin had “used disposable cellphones and
secret codes to try and cover up their activities,” it was evidently of no
avail. They should have worried more about the large network of tippes
that they were creating. As a moral, it can be seen that if you are going
to commit a crime, there’s a higher chance of getting caught if more
people are involved. Large networks can mean big trouble here.

Some of the links in this post are very cool graphs. Definitely worth checking out!

Summary: Given a graph, finding an important node can sometimes be very intuitive. For example, finding a ‘bridge’ between two separate social groups might be very obvious if the graph is drawn properly. However, converting a set of node-node pairs (edges) into an image is not always intuitive. Here are some links to algorithms, applications, and other useful sites related to drawing graphs.

Visualizing graphs is useful. Patterns in data might be very hard to see until a graph is constructed. Take for example the drastic changes in e-mail correspondent structure at Enron before their collapse. Professor Kathleen Carley, at Carnegie Mellon, analyzed the network activity there: “what you see is that prior to the investigation there is this surge in activity among the people at the top of the corporate ladder.” But, she continues “as soon as the investigation starts, they stop communicating with each other and start communicating with lawyers.” (NY Times, May 21st, 2005) Of course, as we have seen in class, powerful nodes, hubs, and bridges can be found easily if presented in a well organized graph. This is why a growing interest in the field of information visualization [wiki] [@MIT] surrounds the conversion of interesting data into a representative image.

Analysis of the enron e-mail network reveals an anomaly

Indeed, a single graph can be drawn in many different ways [wiki: graph drawing]. Often graph drawing is very intuitive: for example, the nodes can be drawn along the perimeter of a circle, and lines can be drawn between nodes on a edge. However, sometimes a graph should be drawn where no lines cross each other; this is called a planar graph (ex). Other graphs should be drawn to keep ’similar’ nodes as close as possible. Even more complex graph layouts may try to minimize the length of certain edges (when laid out as an image), or simulate edges as physical springs connected to each other [force based layout]. Clearly different layouts are good for different purposes, and some such as the planar graph are impossible to achieve at times. An increasing number applications now exist to draw static (non-changing) graphs as an image (ex: aisee).

Increasingly, non-static graphs are also becoming subjects of interest. A static graph might be a ’snapshot’ of the facebook network at any one time, but often we are also interested in how such a network develops over time: is there triadic closure? if so, how long/frequently does triadic closure occur? are there probabilistic models for how a network might grow? etc. One popular programming package has aimed at visualizing dynamic data is called Processing [link] (ex: State of The Union Addresses, salary vs. performance of U.S. baseball teams). Non-static data, combined with an interactive interface, has certainly grown more and more popular.

Most of the graphs online right now are still static images representing static data, but hopefully that will change soon. In addition to the MIT research linked earlier, Carnegie Mellon has recently began a program in ‘Information Visualization’ which is currently being taught by visiting professor Ben Fry.

[For more graphs of interest, expand this article… ]

edit: oh and this is cool too: Bipartite graphs between CEO’s and the corporations they’ve worked at. http://www.theyrule.net/

Read the rest of this entry »

Natasha Collins graduated Cornell in 2005. She was accepted to Yale medical school and planned to attend after spending time in Qatar to teach chemistry to college students, but was diagnosed with leukemia during the summer of 2006. Natasha has been bravely fighting the disease ever since with the support of her friends and loving family. Unfortunately, she now needs a bone marrow transplant to save her life.

Finding a compatible bone marrow donor requires a complex match of at least six different genes. About 30% of people who require a bone marrow transplant find a matching donor within their own family, because tissue types are inherited. The rest must be checked against a national bone marrow donor registry. About 90% of patients who find a match on the registry are of the same race as their potential donor.

For a person of Northern European descent in the United States, the chance of finding a suitable match is estimated to be at least 70%. However, for people of African or Caribbean heritage, the chance of a match could be less than 30%. For people like Natasha, who is a leukemia patient of mixed black and white heritage, the chances of finding a match may be even lower. A likely match may also be of mixed ethnicity, and such people are significantly underrepresented on the national donor list.

After no marrow donor has been found in the immediate family, a potential donor is likely to be a total stranger. However, as Milgram showed in his letter experiments, almost every person in the United States is connected with every other by a relatively small number of social links. Natasha and her family have enlisted the help of online social networking to increase her chances of finding a suitable donor match. Recently, Natasha’s brother Teddy created a group called Become a Hero on Facebook to encourage friends to register as marrow donors.

If we consider Granovetter’s theory on the “Strength of Weak Ties,” this strategy inherently makes sense. A person like Natasha, who attended a large, multicultural university like Cornell, would likely form her strongest friendships from her freshman living experience, classes, and activities. Many - or more likely, most - of her closest friends would not be of similar ethnic heritage, especially since she belongs to a statistically small minority. However, she may have a larger number of acquaintances with similar ethnic backgrounds that she met through friends, clubs and organizations. Furthermore, these acquaintances are likely to know an even larger number of other people with similar heritage. It might be possible to find a potential donor by following a few weak links in this network of acquaintances of mixed black/white ethnicity.

Natasha’s best chance of finding a donor match may be to tap this network using word-of-mouth and the power of online social networking tools. By spreading information and encouraging people to register as marrow donors, she can bridge the ethnic gap that hurts her chances of finding a donor on the national registry.

For more information, visit Natasha’s marrow donor page or the National Marrow Donor Program.