May 29, 2009

Market oriented programming

Apart from CS , the other subject I like the most is Economics . Why economics ? The interesting aspect of economics is, we convert each and every problem into problem of 2 variables namely supply and demand . Thus the complexity of analyzing more variables is reduced to that of 2. I liked the simplicity of this kind of analysis.

Basic principles of economics can be applied to any subject that deals with analyzing the interaction between limited set of resources and players. Economics' analysis explains why certain behavior is happening and how it ought to have happened etc. If the behavior is not what it ought to have been then we change the rules to bring it back to intended one.

Examples of where economics have been applied ( from Wiki ), Economic analysis is applied throughout society, in business, finance and government, but also in crime, education, the family, health, law, politics, religion, social institutions, war, and science.

When I was doing my masters I had given talk on Market Oriented Programming. I am sharing the slides. In this talk I had taken few examples where economic analysis had been applied to computer science problems. As I said earlier, economic analysis is best suited for analyzing Resource allocation problems. We face this problem quite often in computer science. For example,

1. How to allocate the storage space to users. (You can say fixed, but is it really good ?. There are many who are not using any allocated spaces and others who always wants more space. How to draw the line here ?)
2. Load balancing
3. Adsense. Perhaps this is the best example of how the theory of economics can be applied to a CS problem.
4. Facebook is planning a feature where you will buy some credits and give that credits to friends notifications and posts. More on it http://news.cnet.com/8301-17852_3-10212452-71.html

Adsense.

I haven't explained about it in my slides. But I wanted to give overview of it. The problem for Google is ( Here we are taking Google as an example and its true with any other search engine), what kind of Ads it has to show on a page ?. What ever Google do should satisfy three entities, 1. User, 2. Advertiser and 3. Google themselves. So, it has to achieve the following objectives.
  1. It should show relevant Ads to user. If it is not showing relevant ads then users find it less interesting and nobody look at them and it leads to Ad Blindness. Eventually users won't follow ads.
  2. It should satisfy the advertiser. Advertiser should get as many users as possible to their site through the Ads. This is possible only when it's Ad is shown at right place and at right time. For this, each advertiser bids for certain ad terms (Its like describing what Ad they are going to show ) and pays amount to Google based on users visiting the advertisers page. (i.e how many users actually clicked the Ad) Potentially there will be many advertisers, to maximize their chance of showing the ad they have to bid more.
  3. Google should maximize its revenue from above transactions.

How Google achieved these objectives ?
  • 1 and 2 are of related and assumed Google did its best to show relevant Ads. :)
  • 3. Google should maximize its revenue from advertisers. This is done by introducing competition among advertisers. Google uses a variant of vickrey auction (In vickrey auction, highest bidder wins, but the price paid by him is the second-highest bid). Since there will be few Ad places Google should find a way to choose few from these advertisers. ( For example, if you search in google, in your right hand side at the most google shows 8 Ads. So here we have only 8 Ad places or slots )

Whatever mechanism Google chooses,it should not have any side effects. For example, lets assume that Google chooses the advertisers based on the bid amount. What is the problem with this approach ?. Lets see whether it achieves our objectives.
  1. Users should get relevant Ads: This objective may or may not be achieved and it depends on honesty of advertisers. For example, when a user is searching for BMW cars, he should not get advertisements about Ferrari, Toyota cars. This is possible if Ferrari and Toyota bids for BMW keyword. So advertisers may lie and Google should consider it. Second reason why advertisers can lie is, remember they pay only on number of clicks, so advertisers may bid for many irrelevant terms for high price. They do this to increase the brand awareness. Since they are bidding high, their Ads will always show up and users will not click these Ads because these are irrelevant Ads and eventually advertisers will not pay money to Google. The Advantage advertisers get is they show their Ads on lot of pages by paying little money. If Google is not showing relevant Ads, as discussed, it will increase the Ad revenue.
  2. Advertisers should get users to their page: Again this may or may not be achieved for the same above reasons.
  3. Google should maximize its revenue: At the first glance it appears that google got maximum revenue but its not true. Since it may not be showing relevant Ads, it increases the Ad Blindness and looses its revenue. It may be good for short term and definitely not good for long term. Yahoo used the above approach for long time and eBay exploited it. (I got this info from Prabhakar Raghavan's Talk)
Actually Google uses combination of Quality score and Bid amount. Quality score is again combination of CTR (Click through ratio and it is ratio of number of clicks of Ad to number of times they showed the ad), Relevance and Landing page quality. See below YouTube video to know more about Google Ad auction. By using Quality score google eliminates the above problems and still making lot of money :) .

In economics Mechanism design is the study of designing rules of a game or system to achieve a specific outcome, even though each agent may be self-interested. These systems are formally analyzed using Game theory.


References.

Introduction to the Google Ad Auction ( http://www.youtube.com/watch?v=K7l0a2PVhPQ )
http://adsense.blogspot.com/
Example of how bittorrent client uses mechanism design to improve file sharing. http://torrentfreak.com/bittorrent-to-be-pimped-by-nobel-prize-071019/
http://en.wikipedia.org/wiki/Economics
http://en.wikipedia.org/wiki/Resource_Allocation
http://en.wikipedia.org/wiki/Supply_%26_Demand
http://en.wikipedia.org/wiki/Ad_blindness
http://en.wikipedia.org/wiki/Vickrey_auction
http://en.wikipedia.org/wiki/Mechanism_design
http://en.wikipedia.org/wiki/Game_theory
http://plato.stanford.edu/entries/game-theory/

Slides

1 comment: