There are many games that have some element of trading in them, where one must interact with the other players (be they computers or humans) to get what one needs. One game that highlights many of the elements of trading is a popular board game called “Settlers of Catan”. This game has won many awards, such as the German Game of the Year (1995) and the US Board Game of the Year (1996).

I came across this article by Shannon Appelcline regarding trading games, and in particular how in her opinion to make trading work in games. She claims that in order for trading to work the “limited resources must have different values to different people.” This is what happens in Settlers of Catan.

For those who do not know how to play the game, a short breakdown of the game follows.

-         Players build settlements near resources (ore, wood, brick and wool)

-         Each resource is associated with a dice roll, and thus a probability that the particular resource will be available (eg. If the number 12 is associated with a wood resource, wood can only be obtained when 12 is rolled with a die)

-         Players can only gain resources when the number is rolled and they have a settlement connected to that particular resource

-         To obtain resources that one does not have, one can trade for it, either at a 4:1 ratio with the ‘bank’ or with other players (after some negotiation)

-         Resources are needed to build more settlements, roads and to upgrade to cities

(Of course, the game is more complicated than that, this is a simplistic overview.)

In Settlers, each player has access to different resources, and some of their resources can be obtained more often than others. Because of this, they may have an abundance of some resources or a deficiency or need for others. So each player places a different value on their resources. Because of this, players who desire one resources (eg. ore) can try to trade and see if any other player has an abundance of ores (or even just one extra) and is willing to trade.

In class, we have been discussing different styles of auction, one with an intermediary and one without, and this trading that we see here is non intermediated kind. Each player places a value on each resource and we see if an edge can be formed between players. However, we cannot simply match bid and ask prices of the players as in a game there are many other forces that come into play. If a player is close to winning the game, often the other players will refuse to trade with him, in order to blockade him from winning. Perhaps even if two players dislike each other, they may be unwilling to trade, or perhaps give worse rates.

Also, there is a cap on the ask prices, as if there are no players willing to part with the resources the bidding player wants, the bidding player can trade with the bank at a 4:1 ratio. So no player with a monopoly over a certain resource can fully exploit his power by increasing the ask price.

So it appears that perhaps trading is not really as simple as what we’ve learnt in class, that there are many influences that can thwart a successful trade or perhaps to prevent others from exploiting their power and dominating others.

In class and the second homework we studied how users responded to a simple transportation network given certain costs for different segments. We saw that given a certain network, the nash equilibrium is not necessarily socially optimal (the joint strategy is not a social welfare maximizer). This fact is one problem facing urban planners as they attempt to create the most efficient road network for all users. This issue is addressed in a thesis by Tom Bellemans, Traffic Control on Motorways . Several solutions are proposed, however a system of dynamically restricting access to certain routes is the focus. The paper proposes traffic lights be installed at onramps to allow the ramp to be closed in certain high traffic conditions on the highway. This can of course help reduce the overall number of users that can take a certain path, but can also mitigate traffic jams by limiting access to the extent that the traffic jam does not back up to block the corresponding off-ramp. The paper presents a model that minimizes highway conjestion, on-ramp queue length and queue time. It shows that effective ‘on-ramp metering’ can reduce congestion and increase traffic flow. The paper models several situations including lane closure due to an accident or road work.

Such a control system takes the approach of forcing users into a joint strategy that is a social welfare maximizer. Another approach discussed is a variable-cost metering system used on roadways in Singapore. This system adjust the toll that is charged for a given route based on the time of day and traffic condition.

Another problem that appears in reality is that users do not necessarily know the instantaneous cost of a given route, and will choose a route that is not a best response to the current network conditions, collectively deviating from the Nash Equilibrium. This is most evident in rush hour traffic. Without instantaneous knowledge of the traffic conditions ahead, a user may easily become locked into a traffic jam when taking an alternate route would have been much faster. In an attempt to address this issue, a number of municipalities have implemented real time traffic information that is available to users of major highways or busy traffic routes. A short article published by the European Research Consortium for Informatics and Mathematics,
Dynamic Route Control for Motorway Networks, describes current implementations and discusses areas for further research. Below is an example cited in the article of an implementation in Amsterdam (See caption)

Similar systems exist elsewhere. In New York highway signs typically alert users of current delays ahead or even planned future delays eg. construction. I-70 in Colorado provides estimated ‘travel times’ to approaching cities although alternate routes are not suggested. In Amsterdam, an online traffic map shows current congestion levels and is accessible by cell phone.

It is clear that there are a number of possible ways to improve traffic flow on highways and roads. Simply providing drivers with up to date information about the current ‘cost’ of a segment enables them to enter in a joint strategy that is a Nash Equilibirum for the actual state of the network, as opposed to that for an incorrectly assumed network state. Traffic flow can be improved beyond the ‘natural’ N.E. either by introducing monetary costs to segments that offset their travel time costs (making the N.E. a social welfare maximizer) or by forcibly restricting traffic in a strategic way as to ensure a socially optimal traffic flow (regardless of N.E.).

 There are many categories of social software, a crucial part of Web 2.0.  Websites such as Flickr and YouTube are in the media category, while Facebook and MySpace are in the networking category.  These areas dominate the mainstream press when compared to the social bookmarking category.

 Despite the relatively low mainstream press exposure, many tech-savvy users follow the growth of social bookmarking sites as newcomers enter the competition and debates over network controls rage.  Of particular interest to me are the social news sites, such as Digg, Newsvine, Reddit, and Netscape.  These sites consist of communities of users who find and post links to news articles and other resources.  Users are then given a chance to vote on the quality of the submission, with the most popular links (as defined by various algorithms that can include factors such as lifespan and weighted user voting) making it to the front page.

 As these sites mature, the community questions the methods employed to control the network.  Users typically question how the ranking algorithms work, how often and easily the system is gamed, whether there is or should be any editorial power, and the extent of power of top submitters.  Recently, Digg was criticized for supposed rule by a “select few,” that led to cronyism and censorship, along with accusations of gaming the ranking system.  Muhammad Saleem responds to these criticisms and the prediction of Digg’s downfall in Another Mistaken Blogger Incorrectly Predicts The Downfall of Digg.

Digg’s ranking algorithm employs logic partially based on the popularity of the submitting user and the users who vote for the submitted link (a form of a reputation system).  It should be no surprise then that certain users rose to the top of Digg’s network.  However, as Saleem asserts, this is a positive effect, not an example of “rule by the elite.”  These users earned the top spots by the approval of previous links by the community - it makes sense to value this rating from the community and reward the user with credibility.  Even though this makes it more difficult for new users to get their links on the front page, it does not make it impossible and it does lead to better quality.  As Saleem states,

“The top Diggers on Digg are ranked at the top for a reason. You get to the top by consistently submitting excellent content that is generally loved by the community and so Dugg to the front-page.”

Another issue brought to light is the possibility that some Diggers use advanced notification systems to make sure their links get “dugg” quickly by prominent members.  This is an example of an attempt to game the system.  Although Saleem points out that the top 30 submitters do not employ such a system, he acknowledges that others might.  This is a common challenge among any website with user-submitted content - money and fame can be made from placing a prominent link on a popular website, so Digg and its rivals must constantly evaluate gaming tactics.  Much like Google, Yahoo!, and Microsoft defend against search result spammers who game their systems, Digg will continue to evolve its ranking algorithms to defend against gaming.

Saleem concludes with a strong statement of support for Digg - his belief that Digg will stick around for quite awhile.  As long as the community continues to thrive on their collective researching power and the Digg owners continue to protect against widespread ranking gaming, I agree that Digg will live on as a great news resource.

In his New York Times article “Can Network Theory Thwart Terrorists?”, author Patrick Radden Keefe discusses the recent applications of network theory by the CIA and other organizations in order to stop terrorists. Keefe discusses an early network created by Valdis Krebs in which Krebs used shared addresses, telephone numbers, and frequent flier miles to link the 9/11 terrorists. Krebs found that all of the 19 terrorists were tied to one another by just a few links, with a greater amount of links connecting the leader, Mohamed Atta, with the other 18 terrorists. In fact, prior to Krebs’ network, the Army had created an advanced network that sought to map Al Qaeda members and may have succeeded in finding the same disproportionate amount of linkages to Atta, which could have suggested that he was involved in preparation for a future terrorist act.

The decision by the federal government to track data connected to these terrorists raises a complicated question: to what extent should the federal government be allowed to monitor the private data of US citizens? Keefe suggests that this new type of “wire-tapping” – based on linkages in complex networks – bears little resemblance to old-fashioned wiretapping. Whereas old-fashioned wiretapping involved listening in on actual conversation or reading the text of e-mails, the new type of networked wire-tapping is much less invasive; instead of reading the text of an e-mail or listening in on a phone call, computers now track only the sender and recipient of a phone call or message.

But in a world in which most Americans are separated by only six links (verified by network theorist Stanley Milgram), this program has led to an overwhelming amount of “false positives.” In response, intelligence agencies have begun to develop algorithms for determining the “role structure” within a network, searching for differences in the strength of ties among members and attempting to determine a logical hierarchy within a network. While this process is still in its infancy, it represents a powerful method of tracking terrorist groups whose elusive nature has thus far stymied other efforts.

The entire foundation of the internet is based on the concept to share information. The development of social networks on the internet has gone through some changes since the creation of the internet, and these changes are what this course has inspired me to think about as of late.

I will share a bit of personal online social network history. Towards the end of the year 2000, at the young age of 13, AOL provided me with the internet connection necessary to proceed to spend hours of my time on the internet, occupying the house phone line for hours. Not only did this irriate my parents, but I cut off one social communication method for another. Yes, the first network related experiences I had were on Napster chat rooms and subsequently, I found my way on to IRC (Internet Relay Chat) on Dalnet servers. The first chat room I joined on there was the #finalfantasy room. And when I think of the people I met on there in the year 2000/2001 and compare it with the people in my life now (I do not go on IRC anymore.) I have to say that I have been able to maintain friendships with 8 people I met on IRC, on the #finalfantasy chat room in 2000/2001. I do mean true friendships, I mean, friendships as valid and as strong as my best friend growing up. In fact, through the years, and moving to other social communication methods (AIM, of course.) I can say that I have met all 8 people in real life. I talk to them on a daily basis as I talk to other people in my life who may not live in Ithaca. If someone would have told me in 2001 that the people you are talking to on a chat room, that you have never talked to outside of that environment with its constraints that I would still be friends, not only “good” friends with those people, would have sounded impossible to me. This all ties in to how people define strength in bonds. In my particular case, when I was younger and more skeptical about online formation of relationships. I measured the strength of a “virtual” relationship with one I had in “real” life. How do you classify the strength of online formed bonds?

The point that I wanted to make was in regards to the fact, that I think that if I were to go to an IRC channel now, I doubt I would put the time an energy of forming a bond of substance. I think after the creation of the Facebook and other more visually social networks, that the point isn’t to form deep bonds, but more to just on the surface meet people who you will barely know, or to maintain relationships with people you already knew offline. I cannot say that in recent years, I have maintained a friendship with someone I only met online. Do you think we are moving away from that concept? Or is that of my own personal preference. I would say in some ways it’s due to the set up of online social networks now. I think all the added effects are to the detriment of forming strength in bonds.

In a paper by Katelyn McKenna and John A. Bargh found here they discuss the various ways that online relationships effect offline life, and online life. Here is what they say about online groups, such as e-mail list serves, forums, etc. :
“These virtual groups can be fertile territory for the formation of friendships and even close relationships because of the shared interests and values of the members (see McKenna et al. 2002)—perceptions of similarity and shared beliefs (in addition to the shared strong topical interests) are known to contribute to attraction between individuals (Byrne 1971). “

The statement “contribute to attraction”, but of what sort? Of what strength? I suppose all we can generalize is that it develops. I believe that there must be an increased way to define the strength of a bond. This additional information is what I feel would be the most useful and necessary out of most of the network mapping. Although, strength varies from field to field.

Back to my point, I am curious to know what others in the class feel about defining strength of bonds and about their personal experiences in online relationship (friendships/romantic/any type) forming. Do you feel the ability to form something meaningful has become almost impossible due to the the formation of modern social networks (My Space, The Facebook.)?

http://www.cnn.com/2007/TECH/internet/02/14/heartbreak.diamonds/index.html

The attached article discusses a new auction site that connects people who want to buy or sell engagement rings. This is a relatively new market because the sellers all broke up before marriage and are looking to sell their ‘heartbreak diamonds’.

This auction site came into existence because the creator found that upon his break up the jeweler would buy back his diamond ring for only 32% of what he had paid for it. This is very similar to the situation discussed in class in which a seller has access to only one trader and buyer, expect in this case the trader and buyer are the same entitiy. As such, the trader can offer a low price which the seller is inclined to accept.

The creator of the auction site became unhappy with this situation and teamed up with a New York City jeweler to reach out to others that had similar experiences. By creating his auction site, he eliminated the monopoly situation that he and others like him faced. Now people who wanted to sell their ‘heartbreak’ diamonds would have easy access to at least two traders – the jewelers and the auction site. While the auction site does not strictly act as a trader by buying first from the seller and then peddling the ring to the buyer, it still acts like a trader by being an intermediary that offers the sellers an extra choice, thus ending the monopoly that the original jeweler had.

In fact, the auction site actually acts as a shared focus for all the prospective sellers and buyers. The success of the site is due to the many edges it has connecting to these sellers and buyers. These are relatively strong connections because the site has a system to verify the integrity of the traded rings through its own jeweler, enabling the trust of those who buy and sell through the site.

Besides its applications to human behavior, game theory can also aid in explaining biological phenomenon, such as the evolution of viruses.

A research paper from American Scientist Online argues that cheating is a dominant strategy in viruses evolving in a laboratory setting.  The results from the experiment are consistent with the evolutionary version of the prisoner’s dilemma, which suggests that “cheaters should take over the population – selfishness turns out to be the evolutionary stable strategy.”

 To test the prisoner’s dilemma, scientists recruited bacteria-infecting viruses as players. The viruses came in two types, an ordinary virus that could replicate on its own and a defective form, which replicated much faster because of its shortened genome but needed to usurp enzymes from the ordinary virus to do so. The scientists divided the viruses into two groups and allowed them to evolve for 250 generations. In one group, viruses infected bacteria individually (single-infection). In the other group, two or three viruses infected a bacterium simultaneously (co-infection). 

The results showed that under co-infection, the viruses grew much faster than under single-infections, pointing to the possibility that “evolution under co-infection had selected for cheater viruses.” 

 The scientists then mixed these “cheater” viruses with an ancestral population (thawed from the freezer) that exhibited a cooperation strategy. As the evolutionary prisoner’s dilemma predicted, the cheaters had a huge fitness advantage in the beginning but began to lose their fitness as their frequency increased. The cheaters also were well on their way to displacing the cooperators after five generations.

Of course, the prisoner’s dilemma presented here differs in many aspects from the one discussed in class. In this case, the two players do not have the same strategies available to them – the ordinary viruses cannot cheat. The game here is much more complex, involving numerous iterations and with payoffs that depend on the relative frequency of the two players. However, the similarity between the two versions – and the interesting observation – is that in both cases, cheating prevails, leading to an overall decline in payoffs.

Finally, the authors make a very interesting point, which is that game theory and Darwin reach very different conclusions about the evolved population. Under game theory, the overall fitness of the population decreases, while Darwin argues that evolution should make the overall population more fit.

The Network Unbound

As many know, the “old” web was once a novelty because of its ability to transfer information that allowed users to change and enhance their interaction with their own computers. As our technological industry continues to pick up speed, we are now entering the proclaimed “Web 2.0″ era, one where the internet will serve as a much more vast tool by directly linking people together in various ways to enhance their own interactions. While many realize internet sites such as Facebook, MySpace, Flickr, and Wikipedia have infiltrated the lives of people across the globe, the underlying importance of their power may go unnoticed. Besides the obvious social mapping and mass-information processing these sites are capable of, they are also a more visual, and much more accessable, form for viewing and influencing the actual dynamics that circulate in the lower, less visible, levels of any network.

In Boyd’s analysis, networks such as MySpace and Flickr are amplifying and speeding up what the hippest kids on the street always did: incubate trends, nurture subcultures, and remix styles…Rather than exhaust yourself producing what you think the kids might want, you sit back and let them show off for one another.

In other words, investors are not purchasing these networking sites and tools solely for their hit counts and advertising revenue. While they currently are some of the highest visited sites, the revenue calculated to be generated from ad space is trumped by the potential to sell/use the information the sites record. With an established user database, researchers and companies have a large, broad representation of many different human groups and classes. Not only can they effortlessly gather data about any cross-section which they desire, they can also implement a product or idea of their own into the network and hope it catches on with the right online “Connectors, Mavens, and Salesmen,” just like how a trend is proposed to propogate in The Tipping Point.

“User-generated content on the Internet will dramatically increase…. We don’t think this is a coolness issue. We believe people want to live their lives online.”

Relating back to class and lecture, Web 2.0’s implementation will allow all facets and dynamics of different networks to be updated and represented almost immediately via the capabilities of the internet and modern computers. Because information sharing is a one way street on internet networks, traversing networks will never have been easier. Instead of a node only being able to ask one other node for information, and then waiting for a reply back to them, nodes will now be able to search for information from multiple nodes at once, and get instantaneous responses. Such quickness and efficiency will allow nodes that are separated by many middlemen and “between” nodes in a network transfer information with much more ease and reliabilty, and the more visual, online representation of the network will accel the process of forming a direct edge between the once very distant set of nodes. The rapidity with which information can be accessed and shared could severly alter the dynamics of a network in a few days, whereas the natural series of events would have taken a few months to change the network.

Anyone reading this blog post who is enrolled in this class or in any other large lecture has almost certainly experienced the phenomenon of students starting to pack up shortly before class is actually over. A few students will start packing up as soon as the professor (or the clock) intimates that the lecture will be ending soon, and in the following 15-20 seconds more and more students jump on the packing up bandwagon until the professor is forced to end class because pretty much everyone has packed up and is ready to leave.

I had never given this kind of event too much thought in the past as it seems to be a ubiquitous and organic part of the conclusion of a large lecture. However, in reading The Tipping Point and thinking about the “power of the few,” mentioned therein I realized that this could be easily modeled in social network type of situation. Below is a link to a small Java Applet I created using NetLogo that does just this.

When the simulation is run with the default settings, five students decide to start packing up for some reason or another. When their “neighbors” (i.e. the cells in the simulation to which the packers have edges) see that this is happening, they might decide to pack up as well. The likelihood of their deciding to pack is determined by their awareness of the situation and their susceptibility to peer pressure. Also, the more total students start to pack up, the more likely other students are to start packing up when they see their neighbors doing the same. This is meant to account for the sort of whole classroom rustling effect as the packing up stampede gains momentum.

Go to the model now!

For reference, the equation that underlies this model is:

A student will pack up when one of his or her neighbors packs up and: random(1,100) < Sensitivity % * Peer Pressure % * # of People Currently Packing Up

Since this is just meant to be a quick and dirty model of something I noticed, I won’t try to draw any conclusions from it. However, with many of the settings (play around with them!) a noticeable tipping point is reached once some critical mass of people start packing up, and soon after that everyone has packed. Hopefully this model will inspire people to think more about how commonplace social phenomena can be modeled using a (in this case, a very rough) sort of social network model.

The United Nations (UN) is an international organization whose purpose is to promote cooperation in aspects such as economic development, social issues, human rights, international law, and security. Founded at the end of World War II and with an original member base of 50 countries, it now encompasses 192 member states. The UN is divided into five principal bodies: the General Assembly (GA), the Economic and Social Council (ECOSOC), the International Court of Justice (ICJ), the Secretariat, and the Security Council (SC). The General Assembly is generally considered the most important of these, as it includes all representatives from each member state, all of whom get 1 vote.
 
The real power, however, is usually considered to be held at the Security Council, for any decisions taken by it must be carried out under the UN Charter, whereas the GA has no power to enforce them. Security Council members are divided into Permanent and Elected Members. Permanent Members include the People’s Republic of China, France, the Russian Federation, the UK and the USA. Elected members encompass more countries and are divided among the rest of the world. The key difference between these two groups of members (besides the fact that one has permanent membership) is that Permanent Members have veto power.
 
Whereas it takes a majority of 9 out of 15 votes to pass a SC resolution, it only takes 1 veto to block it. The power of the veto is therefore immeasurably strong, and more often than not is has been used as a political tool. A stark example of this is the sheer number of vetoes that have been invoked in the history of the Security Council. If we go to the graphical version, we can clearly notice how the number of vetoes peaked during the Cold War. It is therefore clear that there is a correlation between vetoes and the international relationships in the world, which are reflected in the Security Council.
 
Although slightly outdated, the article “The veto and how to use it” in BBC gives a brief overview of the history of the use of the veto. Just like the USSR used its veto numerous times to spite the US, that fact that of the UK’s 32 vetoes, 24 have been alongside the US is no accident given their particular close relationship. And the fact that a mere French threat to veto a resolution declaring war on Iraq led to a strain in American-French relationship is another example of just how powerful a veto is. In “The Hidden Veto“, Céline Nahory argues how this type of approach (a veiled threat of a veto) can halt and put a stop to many initiatives.
 
It is no wonder many people want a reform in the veto system, especially those who don’t possess it. Not that non-Permanent members don’t also have their own ways of getting around it (this is how the Republic of China was replaced with the People’s Republic of China).  And although our article is more concerned with the veto in the Security Council, just being part of the Security Council is important enough for many countries.
 
At the much grander international scale, we can see that both game theory and network theory are at play. What’s more, interactions in the Security Council are very much like interactions between individuals, with payoffs and rewards- that is, they’re a game. Although more complex than say the Prisoner’s Dilemma, study in this topic (the domain of say, political scientists) can yield useful information. It is my belief that with proper tools one can conduct research on the SC (it is where world issues are discussed and solutions are settled upon, after all) and come up with some interesting papers.
 
For more information on voting in the Security Council and to read resolutions, visit http://www.un.org/Depts/dhl/resguide/scvote.htm