I’ve recently given a general talk about Algorithmic Mechanism Design in which, as usual, one of my motivational slides was the Braess Paradox (if you are a reader of this blog and have not seen the Braess paradox yet — stop reading this post and read about it instead). I would say that the Braess Paradox has been the most influential single intellectual motivator of the whole field of Algorithmic Game Theory. Computer Scientists love it. Economists like it, but CS/Engineering types love it. Here are some thoughts about why we, computer scientists, were so rattled by it.
The Braess paradox provides a simple example where selfish individual behavior leads to results that are socially sub-optimal. An economist can hardly be blown off his feet. The revelation that individuals may act selfishly (or as they would say, rationally) is hardly a surprise for an economist — in fact that is the basis of his field. The fact that such selfish behaviors may have externalities and can result in a sub-optimal outcome is more interesting, but the tragedy of the commons, much studied and discussed, is certainly a more devastating demonstration of this. (Aside: it seems that many undergraduate curricula in economics are so focused on perfect market scenarios that the failure of these models is hardly discussed and you need to get a graduate degree to hear about the limitations of free markets.) However, for engineers we have two revelations here. The mere suggestion that even though we design a system in some “perfect” way, someone who has control over part of the system may reasonably change it is annoying and surprising. Yes, we engineers were thinking about “bad guys” (security), about “broken systems” (distributed computing) but the fact that “ok guys” may circumvent all our designs is an annoying revelation. While the initial reaction of an engineer would be “well, if they’re not following my deisgn, then I can’t guarantee anything“, the Braess paradox also shows that one can analyze the situation under selfish behavior — an unexpected but pleasant surprise. So while economists treat the Braess paradox as just a cute example as of itself, computer scientists immediately view it as a fictional model that stands for a whole new class of examples.
The second difference of a point of view between economists and computer scientists would be about what kind of solutions for this problem should we go after. It would be clear to an economist (continuing my aside from above: at least one with a graduate degree) that in this case some kind of regulation or taxation is needed. However, an engineer or computer scientist would require a much more specific and detailed answer: exactly how much taxation? How would it depend on the network structure? On the set of requests for routing? On the delay characteristics? Economists would also be interested in some form of these questions, but the degree of specificness which would satisfy an economist is much less than what would satisfy an engineer. I would say that most economists would not immediately feel that there are interesting open problems around Braess’s paradox. Engineers and Computer Scientists would feel otherwise: we want general algorithms that will work. An analysis that is satisfying for a whole class of future scenarios. Something that we can implement, analyze, and be confident that will work in the future.
Just by itself then, the Braess paradox offers computer scientists a new set of problems (selfishness), tools to address these problems (equilibrium analysis), and challenges (analysis and algorithms for general scenarios). The appeal is clear, and the main attraction of the seminal AGT paper that introduced the Braess paradox to Computer Scientists was suggesting that the challenges can be addressed: a general analysis, for a whole class of networks, requests, and delays, is possible.
Turing's Invisible Hand 
[…] This post was mentioned on Twitter by Cassidy Thompson, Mattia Monga. Mattia Monga said: Computer Scientists and Braess’s Paradox: I’ve recently given a general talk about Algorithmic Mechanism Design i… http://bit.ly/b0FjkD […]
Braess paradox is interesting in the sense that it shows the negative externalities of one selfish actions on the other permitted by additional choices.
One can even design more interesting 2 persons game, where one has negative externalities on oneself because of additional choices for oneself. I do not know of natural situation where this happens (besides the ancient stories like, burning the boat after crossing a river so that the army does not have a choice to return back).
Does anybody have a natural example in the sense of Braess paradox where one’s selfish actions hurts oneself.
It seems clear (and by now widely-appreciated) that economists’ work has left open some very interesting and worthwhile algorithmic/design problems for CS/engineering people to explore, of which this is a great example.
My question is: why did economists pass these opportunities up? Of course to a certain extent they were not trained and acculturated to recognize these as interesting and viable opportunities. But I’m more curious about the positive side: what other opportunities have economists seen that struck them as more interesting? And can we learn from their choices?
In general it would interesting to hear more ‘talk-back’ from the economics profession about their thoughts on AGT. (Probably this discussion is underway and I just don’t know where to listen in.) More specifically, it could be interesting to hear from economic theorists what, to them, is the most fascinating or important legacy of Braess’s paradox.
One place this Braess’s type paradox happens on the internet is Display advertising business (i.e., banner ads).
Dear Kamal, Can you elaborate on that?
Sure. On the internet there is a shortcutting bridge, such as adding annoyance to the ad or even behavioral ad-targetting. Let me take the latter. Behavioral targetting basically ads new bridges in the Braess paradox, and it is in everybody interest to walk on it. It depresses the ad-rates, so does adding annoyance. The situataion becomes non-pareto optimal, as the slow-down added to the internet due to display ads is worth less to the publisher than the cost of the time to the user it slows down (by one study which we conducted and published in a workshop, display advertisements value users time at 13 cents an hour).
Yes, you could say that it is not the time but the web-experience which matters. Sure, but since there is no unit for web-experience, time is a good proxy. As an example, one metric of how good or bad Google considered its new feature instant search could be the time from start searching to end searching.
I guess currently there is no way for publishers of display ads to use the “time” to optimize thier advertisements, and decline to take this bridge, since if other publishers take this bridge so does one specific publisher interest is to take the bridge. On the flip side even if other publishers do not take this bridge, it is in the interest of one specific publisher to take this bridge.
I certainly agree that advertising in general, and certainly Display advertising on the Internet is a clear example of the tragedy of the commons (more generally than Braess’s paradox). It is easy to imagine that if the quantity of ad-space on the web (or on TV) would be cut by a factor of two or three, neither advertisers nor publishers would loose anything (since rates and effectiveness would double or triple), while users would be much happier. I am not sure that this is the case specifically for the types of ads that you mention: “rich” display ads which are indeed especially annoying to the user, may well have a significant value to the advertiser due to their emotional reach, and behavioral targeting may have significant value to both advertisers ands user due to their precise targeting (assuming — a big assumption — that privacy is adequately handled.)
I think it hard but possible for a large company to shift the current equilibrium of display ad pricing. What we need is a fewer, but high quality ads, with higher price (reserved prices). High reserved prices and high quality ads form positive feedback loop, since only the advertisers with high quality ads/products could afford the high rates. Current this feedback loop is in negative cycle. Low prices, means more ads, means publishers accept lower quality ads, means even lower prices.
What is the cost of shifting from one undesirable equilibirum to another more desirable equilibrium? I think it could be very large, but I think at least three companies are in position to attempt to do that, the three companies, in my opinion, are Microsoft, Google, and Apple.
Kamal: I agree that it would be great to find a way to “shift the equilibrium” to the better. However, I can’t see that the big intermediaries that you mentioned (Microsoft, Google, and Apple) can do so: each of them acting alone will not have any effect (except for themselves loosing out in the market), and all of them collaborating (colluding, really) will be very plainly (and rightly) an illegal anti-competitive act. The same is true for big publishers, big advertisers, or big ad-agencies.
My hope would be that users insist on not using sites with “too much” or “too annoying” ads, and if enough people did that, then more publishers would more effectively regulate the amount of “ad pollution” on their web-site (as some of them do already). The same feedback mechanisms that led to the spiral of more-and-more and uglier-and-uglier ads, can work the other way too, given enough user-pressure. The sad state of TV advertising need not be the the type of equilibrium reached on the web.
Noam, I do not mean that Microsoft/Google/Apple simply start reducing the annoyance in the ads on the websites they control.
I meant one can design a mechanism, which one of these bug players could implement, so that it is in the interest of the website owners to take user annoyance in to account.
One can’t solve the Braess paradox by simply not driving on the free bridge. One can do so by introducing a new mechanism (e.g., by putting Toll in the free bridge).
One of these three big players could do so. It is quite possible that Apple might start doing it on its own iOS platform. But the mechanism design problem for Microsoft or Google would be much harder, if either wants to incentivize the web-publishers to take user externality in to account for display advertising. But solving a hard problem could potentially comes with big rewards too.
It is useful to mention also Aaronson’s “Braess’s Unparadox”: If you add an extra lane to a highway, one possible result will be to decrease congestion.
(See in this classic post: http://scottaaronson.com/blog/?p=285 )
Indeed sometimes Braess’s paradox is overplyed. Typically (especially if you don’t count the increase in additional cars) a new route will improve matters. Often we can design fairly good routing systems without taking into account the strategic (or selfish) behavior of individuals and even more often (but not always), when we try to take “selfish” behavior into account the situation is too complicated to say anything meaningful.
“when we try to take “selfish” behavior into account the situation is too complicated to say anything meaningful.”
Ahh, that’s the point I disagree with: there are whole areas in which you can say much that is meaningful about the outcome of selfish behavior, even in the “real world” and certainly in computer-mediated one.
Dear Noam, I said “more often” certainly not always. I agree that there are whole areas you can say meaningful things for selfish (or rational) agents, especially when you do not try to analyze an arbitrary situation but you design the situation for that purpose.
1.”The revelation that individuals may act selfishly (or as they would say, rationally) is hardly a surprise for an economist — in fact that is the basis of his field”.
Just to clarify that this identification agent=rational=selfish is only theoretical. The consideration by economists that agents are selfish is just a worst case assumption. There was much useless discussion in the past about as if this “selfish” assumption reflected a real agent. Real agents are heterogeneous: some selfish, some altruist, most oportunistic; some clever, some dumb, most…. The point is that if you can design your system (market) to perform as desired under this assumption, then it should perform as well under any mixture of heterogeneous agents.
2. “Aside: it seems that many undergraduate curricula in economics are so focused on perfect market scenarios that the failure of these models is hardly discussed and you need to get a graduate degree to hear about the limitations of free markets”.
Sad. As soon as you start to focus on real economic sectors, you find imperfection everywhere, except maybe in finantial markets, the most close to perfection. Industrial Organisation (odd name for the theory of imperfect markets) is clearly the area of economic theory most attached to reality. To be a good model of reality they need to consider circuits of entangled markets, where each gate is a different imperfect or perfect market, the circuit computing a set of prices along the value chain. Here AGM might have something to say. In any case i hope any researcher in this field gets the Nobel this year (i´ve read somewhere some, as Tirole, are candidate).
I think selfishness has some connotation to it. To me rationality means there is an objective function which agents try to optimize. That is rationality is a computational model of an agent.
I actually made a phrase, which is popularized by Christos to convey that rationality is basically an economics way of modeling computation.
If a turing machine can’t reach an equilibrium so can’t markets.
Thanks Kamal and Noam for the explanation on display advertising.
Here is a problem that I heard recently that I think is quite interesting. Is it possible, and if yes how, to lower the price of advertisement in internet sites like search sites? The difficulty is that the prices are determined by auctions. So even if you grant the winners cash awards they will simply make higher bids.
Advertisement, in general is an interesting element of modern economics. Are the huge amount of resources for advertisement reflect efficiency achieved by market’s forces or some sort of market failure?
auction is not the cause of high price of search advertisements. auction is just a price discovery mechanism. if the price of search ads should be a penny auction should only help discovering that price.
the search ads are pricey because they are very effective and efficient. the supply of such high quality advertising opportunitity is quite scarce.
also in my knowledge the general equilibrium theories do not cover advertising quite adequately. for an example, advertising does not fit the market model of arrow and debreu. so what fraction of gdp an economy should spend on advertising is not clear.
Regarding the second part, it would be indeed interesting to find a way to add advertizing to such a model of general equilibrium theory.
The question I referred to is this. Suppose, as a shoe manifecturer you want to reduce the price of shoes. Then you can simply do it. But suppose you want to reduce the price of advertisement that uou see by auction then it is not so clear how to do it. This may still apply to shoes if you dont sell them in stores but alsy via auctions.
As a shoe manufacturer, when you reduce the price of shoes below equilibrium, then some buyers who would like to buy your shoes at the price you set, would not be able to do so due to lack of supply.
So in case of shoes, the price is set first and the potential buyer comes later (at least in your setting).
In case of auction, potential buyers comes first and the price comes later. But the same phenonmenon could decrease the price below equilibrium level.
If you want to reduce the price of something in an auction below its equilibrium you can do the same thing. That is decide *not* to sell that something to a subset of bidders and hence ignore their bids. When you reduce the set of potential buyers, the equilbrium prices should come down. How to do it systematically could be hard, as in the case of the shoe example (which set of buyers to exclude depends upon another variable called position in the queue).
Reducing prices below equilibrium always means rationing using some other means. With shoes as with ads. You would want very good reasons to do that — I don’t see such in the case of ads.
In fact, my hope would be the opposite: increasing prices which is equivalent to reducing the quantity of ads, correcting the market imperfection of ad-pollution of the common space.
Braess Paradox is a good illustration of how easily our intuitions about collective interaction can be fooled.
Let me continue here the discussion with Kamal and Noam.
(The replies make the remarks thiner and thiner.) First on why you want to reduce the price. Suppose that there is one company that is very strong in the hat market but try to make also shoes while another somewhat smaller company that is very strong in the shoe market and is regarded as a threat to the hat company business. What the hat company try to do is to reduce the price of shoes (to the extent it will even lose from the shoe business) but driving the price of shoes down will decrease the profits of the shoe company and make it less of a threat.
It seems that this is possible. But when the two companies sell shoes by auctions it is not clear if this can be done and how. If you sell shoes at half price then they cost half, but if you make a rule that a bidder pays half the bid he will double the bid.
I do not see how to rule out certain bidders will be effective. Maybe you can sell not to the highest bidder but to a random bidder among the top 20% (at the highest price among bidders who did not make the lottery, say). But I am not sure this is effective either.
(PS to talk about “reducing below equilibrium” is a oversimplifications. There can be cases of many equilibria so you may want to jump to a different equilibrium.)
I agree equilibrium price is over simplification. But what you are trying to accomplish, i.e., sell cheaper, the auction is an orthogonal issue. Auction is just a price discovery mechanism.
Yeah, there could be multiple equilibrium if you take a complicated situation. For the purpose of explaining that auction is not an issue, I took a simplistic example. That is there is a single good, with monotonically decreasing demand as a function of price, and monotonically increasing supply as a function of price. Such a situation has an equilibrium price. Yeah, you can sell a shoes at a loss, but you have to sell as many shoes as demanded, otherwise people who are left out will buy your competitor’s shoes at potentially a higher price.
Now, suppose Microsoft undercuts search ads. It is quite easy. Microsoft could ignore the bids, and use some other formulation, such as relevance or reputation for allocating ads and hence provide the ads for free. But that does not decrease the ad prices for Google. Why? If Noam searches on Google, and has an intent to buy a camera, then if a camera seller wants to reach Noam, the camera seller has to offer to Google as much as the potential profit from Camera, or the second efficient means for reaching out to Noam (whichever is minimum). Usually the former is lower, as it is not usually easy to figure out when Noam wants to buy a camera.
So if Noam searches on Google, Bing can’t provide this supply (i.e., Noam’s intent) to the potetial ad buyer. This is the problem which prevents Bing from undercutting and not the auction itself. Even if Google sells Noam’s intent at a posted price, Bing can’t really affect this posted price by pricing its ads. (Bing has to attract Noam by offering incentives to Noam, such as a better or a different search experience, or other rewards but without attracting Noam there is not much Bing could do to interfere how much Google sells Noam intent to advertisers, whether or not the intent is sold by an auction).
Your explanation Kamal is appealing but for the general case I am not sure the auction issue is completely orthogonal.
Also, generally speaking it is not clear that auction is just a price discovery mechanism. For example, can auction be used as cartel forming mechanism?
Yes it could. You could auction to facilitate a cartel. But then there might be other ways to do so.
Hi Noam
For those who are interested in BRAESS PARADOX I might mention that there are some interesting papers of Daron Acemoglu (John Bates Clark Medal winner)
Eyal
Hi Noam
i resend:
For those who are interested in Braess Paradox I might mention the interesting papers of Daron Acemoglu (John Bates Clark Medal winner)
[…] scientists love paradoxes , especially ones rooted in brain-twisting logical contradictions […]