http://www.nytimes.com/2007/06/03/business/yourmoney/03google.html?pagewanted=2&sq=pagerank&st=nyt&scp=1

This article from the New York Times discusses Google’s ongoing mission to improve its search engine. Specifically, the company aims to better satisfy its users and ultimately decrease the number of people who leave the site not having found what they were looking for. In order to close this “gap between often (finding what you want) and always,” Google engineers are looking to improve its “ranking algorithm” by implementing a solution they have dubbed QDF (”Query Deserves Freshness”).

There are several problems Google has faced during this “tweaking” process:

- The sheer scale of web pages and users the site must constantly deal with

(This relates to the “problem of abundance” discussed in class)

- Fraudulent websites filled with ads, pornography, or financial scams

(This relates to the game theory principle aspect of web search discussed in class- since the world reacts to what Google does, people can take advantage of this and write pages designed to score highly)

- Figuring out exactly what the user is searching for (ie: “apples” usually means the user is searching for fruit, while “apple” means the Mac computer)

(This relates to the Intent of the Searcher problem discussed in class - it is often not clear from a 1-word query what the searcher is looking for)

- “Freshness” - how many recently constructed/changed pages should be included in the results?

(We discussed in class that web pages change rapidly)

While all of the problems mentioned above have posed significant challenges, the problem of freshness has proven to be particularly troublesome. Would it be better to provide the most up-to-date information or to display pages that have proven to be more reliable over time? Until recently, Google has preferred the latter. The company, however, is now trying to fix this problem so the issue is not so black and white. QDF is “a mathematical model that tries to determine when users want new information and when they don’t.” Although the exact mechanism behind QDF has yet to be completed, Google engineers believe the solution lies in determining whether or not a topic is “hot.” To be more specific, if numerous web sites are all dealing extensively with a particular topic simultaneously, QDF reasons that users are going to want the latest information on this subject.

The latter half of the article then goes on to describe the Google search engine’s method of ranking pages and how the firm’s engineers are working to improve search quality in other aspects as well. Currently, Google uses a system of “signals” and “classifiers.” It ranks the pages with a system of more than 200 types of information, or “signals.” Pagerank, the system of ranking discussed in class, is only one of these signals. The collected signals then proceed into “classifiers,” formulas that attempt to infer useful information about the search in order to send the user to the most relevant, helpful web sites. While developing this elaborate system, Google also had to develop a system to account for user typos and ambiguous search terms.

Google clearly has a seemingly never-ending amount of work on its hands as it continues its mission of creating the most efficient, helpful search engine. As the Internet constantly expands and changes, Google must continue to adapt and develop solutions to the problems that accompany this growth. New difficulties, in addition to those mentioned above, will inevitably arise, and the search engine will most likely have to become increasingly complex. In addition, Google must not only face this task of constantly updating and revising its search engine, but it must also do so in the presence of competitors such as Yahoo! and Microsoft. If Google does manage to implement its QDF solution, among others, that finally closes the “gap between often and always,” it will most likely remain a mystery, as secrecy is needed to protect the coveted solution from competitors and fraudulent Web designers. For Google to reach this point, however, it seems that it has an indefinite amount of “tweaking” yet to do.

www.sfgate.com/cgi-bin/article.cgi?f=/c/a/2008/03/05/BAGFVDQ1S.DTL  In 2005, Thomas Schelling won the Nobel Prize in Economics for, in the words of the Nobel committee, “having enhanced our understanding of conflict and cooperation through game-theory analysis.” Schelling is attributed to having helped the United States avoid nuclear warfare with the Soviets during the Cold War, and, once again, his strategies may be needed to spare the US from potential nuclear war, except this time, with Iran.  Current relations between the United States and Iran are in a most tumultuous state. Recently in the media, there have been many analysis of how the US can better use game theory to ease the growing tensions with Iran and prevent war between the two countries. As we have covered in class, game- theory is the way in which actors are influenced to make choices in game scenarios. Each choice made by the actors directly affects the decisions made by other actors in the scenario. To apply this explanation to the conflict between the United States and Iran, there have been statements made by the US, either through policy or verbal address that have led to subsequent reactions by Iran. In this article regarding weapons conflicts between the US and Iran, the theories of renowned economist and diplomatic analyst, Thomas Schelling, offer insight on how President Bush can utilize game theory to ameliorate tensions between the two countries. The discussion of these theories took place at UC Berkeley where Schelling and other esteemed experts shared their views on the current US- Iran conflict.  The best outcome for both sides is clearly a peaceful one, however, the current US strategy may not be promoting this conclusion.  Currently, the strategy of the US has been to threaten Iran with attack if their pursuit of nuclear weapons continues. The security dilemma between the two countries exists in a heightened state due to the extremely destructive power of nuclear weapons. In hopes to deter Iran from continuing steps toward nuclear production, President Bush has recently been implying that the US will use necessary force in order to destroy Iran’s nuclear capabilities. To contradict this aggressive US strategy, Schelling argues that US threats only increase Iran’s desire for nuclear capabilities. The public threats made by the US may seem like a reasonable strategy due to their objective of keeping Iran a non-nuclear state, however, this aggressive is only dominant when the threats act as a deterrent. In Schelling’s analysis, it seems that US threats act not to deter Iran’s nuclear interests, but quite conversely, encourage them. This fits with one of Schelling’s most acclaimed theories, that extreme threats or policies can backfire.Therefor, according to Schelling, with a more diplomatic approach, the US could not only facilitate a more effective means to ending the conflict, but also peacefully ease Iran’s desire to become a nuclear power. www.sfgate.com/cgi-bin/article.cgi?f=/c/a/2008/03/05/BAGFVDQ1S.DTL 

This was only briefly mentioned in class in the first lecture, but one property of a dynamic network is the death of nodes. Bruce Schneier comments on an internet-specific form of nodal death called “link rot.” Link rot is, quite simply, the disappearance of information linked to on the internet.

There are two general problems with node death. The first is, of course, the disappearance of the information contained by the node. The second is the disappearance of the connection through that node.

The problem is solved in both cases, unsurprisingly, by redundancy. The disappearance of connections through a node is solved by having a great number of connections going through different nodes between the starting node and ending node. For instance, a page on a link sharing sites such as del.icio.us could be considered at local gatekeeper. If a user’s page were to disappear, then the use wouldn’t know how to find nodes linked through that site, since that node provided a connection to other nodes. These nodes may be local gatekeepers, shortening the path between you and other information. However, the internet is extremely connected, so longer paths to finding those “lost” nodes most likely exist. You can imagine a situation, however, where a node is a gatekeeper. There, the loss of the node would break the network into two smaller components.

The problem of the disappearance of the informational content of a node, however, is more troublesome. For instance, I once linked to a story on Yahoo! on my blog, only to come back and find that the link was dead less than a month later. I found a similar version on another site, but not an identical article.

The internet is responding to this in some fashion. The Way Back Machine was one of the first solutions to this problem- it provides an archive of the internet. Nowadays, Google does a similar thing with Google cache. Sure, the website for the prostitution ring Governor Spitzer was patronizing may no longer be operating, but Google’s cache is still up. Of course, this is not a perfect solution. The cache information will eventually disappear, too, and Google sadly does not store pictures.

Recently, the world economy has been having large problems in the credit markets. The sub-prime mortgage crisis in the US real estate market has had grave repercussions in the banking systems in many banking markets. It has affected almost all of the major players in the market including Credit Agricole, HSBC, UBS, Merrill Lynch, and Citigroup. These conditions in the market have made banks much less willing to lend to each other.

The problem is not that the banks lack the money to lend, but rather that they don’t have enough confidence in each other’s assets. BBC Economics Editor Evan Davis says that the situation that we face now is a “crisis of confidence.” This mostly means that there is a general lack of it in the market. Given that credit and banking relies almost exclusively on trust, it is not surprising that this has caused great problems.

In order to fight this problem, many central banks, including the US Federal Reserve and the European Central Bank, are planning to inject billions of dollars into money markets. They are planning to make these funds available in the form of auctions. However, these auctions are being run in a slightly different way than usual. They are making the funds available, in this case $200 billion from the Fed and $15 billion from the ECB, in the form of 28 day auctions instead of the usual overnight auctions.

This gives the banks more time to deal with the issues and bid on the assets. It is not clear exactly what auction style is being implemented. This is also a different kind of auction to many of the ones we talked about in class in that the objects being bid on – the financial assets – are ordained with an intrinsic monetary value. The difference is the amount of risk that the bidding parties associate with them. This is an example of how auctions can be used to give a large number of assets to the specific parties who need them most.

So we all know about non-cooperative game theory: it’s every man for himself. But, cooperative game theory has some interesting applications. The difference between the two is that cooperative game theory has groups or coalitions that enforce players to cooperate. Every possible coalition that can be formed gives a payoff to the players who form the coalition. Usually, a restriction is put in place: by adding more people to a possible coalition, you cannot decrease the payoff (though you may decrease they payoff per person). The first concept for CGT that was similar to the Nash Equilibrium for NCGT was the idea of a stable set. A stable set is a set that satisfies two properties:

1) There cannot be a coalition in the set that dominates another coalition

2) Every coalition outside the set is dominated by some coalition inside the set

Unfortunately, these do not always exist, nor are they unique. Thus, other similar concepts have been developed, such as the core, shapley value, or the kernel of a game.

It seems like cooperative games would develop in many social situations where we wouldn’t necessarily expect a game to exist. Forming project teams seems to be a situation where different coalitions would give different values. Different team members might work well together, so payoffs would not be boring.

When we think about airline routes, it is immediately apparent how they form networks. It is clear how concepts from social networks such as triadic closure apply. For example, consider Eastern Airlines in the early 1960s. It adopted the novel idea of hourly shuttle service between New York’s LaGuardia Airport with Boston’s Logan and Washington’s Ronald Reagan Airports in 1961 where passengers would simply show up at the airport to purchase their ticket. With the convenience of hourly service and skyrocketing passenger traffic, there were essentially two very strong edges tied into La Guardia Airport. It was only natural that within one year, in 1962, triadic closure took effect with the Washington to Boston shuttle route added to ease the stress off LaGuardia since direct shuttle service was now available between Logan and Ronald Reagan and connections through New York were no longer necessary. In fact, this is a case of strong triadic closure in New York’s perspective since it had strong links from the strong demand to both Washington and Boston. The new route was beneficial to the expansion of the business and also contributed to the reduction of congestion at La Guardia Airport.

However, a less obvious observation is that network exchange theory concepts are involved as well in the perspective of the cities. Consider the cancellation of flight service from Ithaca to Pittsburgh. Notice that in 2003, Ithaca was struggling with its flight service because of isolation issues. Small cities have this problem because they only have a limited number of feasible edges to link with. For example, it is infeasible to have direct service from Ithaca to London Heathrow due to low demand. Also, low passenger traffic precludes large aircraft from servicing small cities which limit the range of possible destination cities. Thus, Ithaca only has a small number of possible edge links to hub cities. Although there is nothing being officially exchanged, it is clear that the hub cities have the power over the smaller ones because they have centrality and the power to exclude as advantages. Also, the concept of satiation allows them to pick the most profitable routes to maintain service to. Thus, small cities tend to be at a disadvantage because a single route cancellation can wreak havoc. In the case of US Airways, an annual loss of $60,000 in 2003 caused the cancellation of Pittsburgh service and even left the future of Ithaca Airport in doubt with only two destinations left in 2003. Similarly, numerous other regional airports faced similar concerns in 2003. Clearly, the effect at Pittsburgh was less dramatic because numerous other airlines still provide service to many destinations. The city can choose other cities to “trade” with by adding flight service there.

Notice that strong triadic closure played a role in route and business expansion with Eastern Airlines’s shuttle service. However, this cannot apply to small airports. This is because the low passenger traffic precludes any edge to Ithaca from being a strong one. In fact, no mainline jets even service regional airports such as Ithaca. Thus, it won’t be part of any possible triadic closure which makes it very difficult to expand. Besides, who would connect at Ithaca Airport? Lastly, in 2003, with New York and Philadelphia as the only destinations left, those two cities essentially served as gatekeepers to Ithaca which ties in with the network exchange theory since they were essentially given extensive power. They dictated all the possible connections Ithaca flyers could make. However, their power has been reduced today because of Northwest’s service to Detroit which has reduced their power to exclude since passengers have additional options now. Nonetheless, to conclude, it is quite difficult to sustain business at small airports. This article may be from 2003 but small airports across the country face these issues to this day. Currently, Ithaca Airport is not in bad shape since it is not being excluded as severely as in 2003 but exclusion and the lack of power is always a problem for small cities in the game of building airline routes and schedules.

Source: http://query.nytimes.com/gst/fullpage.html?res=9D01E0DC143FF930A2575BC0A9629C8B63&sec=&spon=&pagewanted=all

How Do They Track Us?

Expanding on Professor Easley’s lecture discussing keyword-based Web advertising, Louise Story of the NY Times authored a blog post entitled “How Do They Track You? Let Us Count the Ways” as a supplement to her article “To Aim Ads, Web is Keeping Closer Eye on What You Click” [which was posted by wjg62].

Ms. Story worked with the research firm comScore to measure how much data Web companies can collect from users.

By looking at the data large media companies can collect from Web visitors, one might be able to predict which company will lead in online advertising. ComScore counted five different types of “data collection events” for large media companies. There is a conversation between the user’s computer and the server of the company whenever one of these data collection events occurs, four of which occur on the websites the companies run: pages displayed, search queries entered, videos played and advertising displayed. The fifth data collection event deals with ads on any page on the Web that are placed by advertising networks owned by the media companies, like Google’s AdSense network. These ad networks allow the companies to note the website you are on when they serve you an ad.

For each data collection event, the company might receive information on the page the user was at, the users IP address, and if applicable, the content of the ad. In one month of the study, the largest media companies had the potential to gather data from 400 billion events (Yahoo), 100 billion events (Time Warner AOL), 91 billion events (Google) and 51 billion events (Microsoft). Story’s blog post includes data from the comScore study in graph form, showing that each media company has the power to collect data on users in many different ways.

What does this mean for web users? Many people may consider all of this possible data collection to be invasive and frightening. Several NYTimes users commented on Ms. Story’s blog post with their thoughts on data collection by Web companies, including many expressing discontent. However, it is relevant to consider that not all of the data is retained by the companies that have access to it and much of it is not traceable to individual users. Ms. Story highlights positively that we as consumers receive free services and content via the Web by being shown ads. Another positive way to consider data collection is that we “pay” for our free email and free Web content by letting the companies collect data about us. Ms. Story suggests the possibility that if for example, Yahoo and Microsoft were to merge into one company with combined data on users, consumers might get more or better free services in exchange. It will be interesting to see if more studies on data collection can include the aspects left out of the comScore / NYTimes results and if the data proves useful and beneficial to both companies and consumers.

In January of 2005, Nicholas Negroponte announced his idea to create an inexpensive laptop for children. Originally billed as the “$100 Laptop”, the device would provide a tool for poor and underserved children to tap into the educational opportunities presented by technology. His vision has since grown into a nonprofit organization, One Laptop per Child, sponsored by companies such as AMD, Google, and Red Hat. Now called the XO-1 and priced at about $188 USD, the first mass-produced laptops started rolling off the assembly line in November 2007.

In line with OLPC’s stated goal of providing a child-friendly laptop, the user interface is strikingly minimalistic. For example, only one “Activity” (roughly corresponding to an application) can be viewed at a time, and the typical hierarchical file system is hidden by an abstract “Journal” that records both files manipulated and Activities used.

However, the most interesting aspect of the interface is the way it integrates the network. When the laptop is powered on, the user is presented with a screen that shows icons representing the local computer and which Activities are being used. “Zooming out” once via a button on the keyboard shows the user’s friends who are currently connected through the built-in wireless network; zooming out twice shows everybody currently connected, including friends, with users who are all participating in the same Activity clustered together. Mousing over each neighbor’s icon shows what he is currently doing, and small Activity icons next to the neighbor icons allow the user to join the Activity with a single click. Since the intent of the laptop is to encourage collaboration and sharing, almost every Activity on the computer is sharable over the network.

For example, you might want to share a program you created with one of the bundled programming languages. Pressing a Share button on the keyboard makes the program visible next to your icon on your friends’ laptops. They can then click on the icon to download and use or edit the program themselves. Conversely, your friend might ask you for help with a document he’s writing, and you can simply click on his icon to view the document and offer your advice.

The social networking ramifications of this are significant. The computer’s default interface is essentially a visualization of the network the user belongs to. Although the interface does not make visible the edges between friends, it does highlight those people explicitly marked friends, and it shows which Activities they are using and with whom. Furthermore, all the people shown in the network are geographically close, so one can easily imagine that friendships on the network will reflect or lead to friendships in reality.

The result is a social networking tool that goes beyond anything the current generation offers. There is no layer between the computer’s interface and the tool—the interface is the tool. Social networking is built into and emphasized by the computer’s default interface. Video games and instant messaging services have long provided a means for groups of people to congregate on-line, communicating and interacting in real time, but they have always been limited in their scope of utility. More recently, websites such as Facebook and Google have taken strides in connecting computer users, allowing them to talk in real time, share documents and pictures, view and edit schedules, and so on. But these all suffer two significant flaws. First, the user must actively seek out the service. Facebook may be ubiquitous among college students and gaining ground elsewhere, but the vast majority of Internet users do not use it. Secondly, these services are not integrated smoothly with the rest of the computer’s interface. For example, to share photos on Facebook, you must navigate to your Photos page, find the Add Photos button, select your photos, annotate them, organize them, and then hope your friends will log on to Facebook and see them (granted, not an unlikely event). Although it doesn’t have all of the features of these services, the XO’s interface does what the others cannot in providing universal and simple connectivity.

See also:

Laptop With a Mission Widens Its Audience (NYT Blog post)

YouTube slideshow of XO’s user interface

Interestingly enough, Game Theory can be an appropriate tool when it comes to analyzing terrorism. It helps us to look at the strategic actions of governments and terrorists where their actions are mutually dependent.

Now to look at the various situations where Game Theory can be applied – The first obvious application that would come to mind is where you have the terrorist group as one player and the government as the other and the four outcomes can be a successful attack where the terrorists get what they want, a successful attack where the government does not give in to the demands, no attack or an attack that results in logistic failures. Another application could be a three player game in which the players could be two targeted countries and one terrorist group where each country would chose its deterrence expenditures and the terrorist group would chose one target nation considering the payoffs and the possibility of a successful attack in each case. A yet another application would be the case where the terrorists would know their true strength but the government would have to figure out the correct strength of the group based on their attacks, threats, demands etc. This is often the case as some terrorist organizations like to issue overblown, baseless threats, that they are not actually capable of executing, just to increase the pressure on their targets.

We could also have a case where the terrorists and the host country have an understanding and are accommodating each other. So this leaves the other countries with three options: retaliating against the host country and the terrorist group, accommodating the terrorist group or just doing nothing. Some game theorists have shown how the option of accommodating the terrorists dominates in this case. This leads to the Prisoner’s Dilemma where countries seek to accommodate the terrorists in which case they would have to break the trust of other countries who were helping them curtail terrorism in the first place.

As a matter of fact, game theory can even help enlighten the government officials about the effectiveness of their anti-terrorism policies. For example, let’s think of a game where the US and EU are the two players. They face a common threat by a third country/terrorist organization. Now if either of the country preempts the threat, both EU and US get 4 in benefits and the country preempting incurs 6 as the costs for preempting. This way, the payoffs of the country preempting would be -2 and that of one getting the free ride would be 4. But if both EU and US share the cost of preempting, they would each receive 2 as the net benefits. This again results in prisoner’s dilemma and both players end up not preempting.

Now consider the second case where the US preemption would give it a benefit of 8 (due to it being a favorite target for various terrorists) and the EU still gets a payoff of 4. The costs of preemption are still 6. If we calculate the payoffs in each case, we would see that US would have a dominant strategy to preempt and EU would have a dominant strategy to free ride, leading to a Nash Equilibrium. And this game representation pretty well characterizes the US position after the 9/11 attack.

For further reading. , please refer to: http://www-rcf.usc.edu/~tsandler/Terror_Games.pdf

Seven Social Networking Strategies for Smaller Businesses

Rusty Weston’s article illustrates 7 social networking strategies for small businesses. The seven are Prospecting on a Social Network, Sourcing talent on a social network, building widgets for social networking sites, encouraging employee use, not abuse, of social networking, building a custom social network for customers, building a custom social network for employees or suppliers, and building brand awareness on a social network.

Social Networking sites are the new target for small businesses, as they garner some of the greatest numbers of hits each day. It is important for small businesses to take advantage of these untapped sites with millions of customers at their disposal. By connecting to these sites, the companies are building bridges to networks of customers that, before, were unconnected. The site users could be thousands of miles away and have no other way of coming into contact with the company or its products, but the social networking site closes this gap.

The sites also allow companies to grow from within. By encouraging employees to use the social networking sites, companies can keep their employees happier, retain them longer, facilitate the exchange of information within the company, and as a result, increase innovation. Building social bridges between different divisions within a company is essential and will only speed the development of new ideas and innovations.