Personal tools
You are here: Home Events Kousha Etessami

Kousha Etessami

Auctions, Mechanism Design, Market Equilibria, and Algorithms

I will try to give a brief feel for the active research area that has emerged at the intersection of the topics mentioned in the title. I will do so by focusing on just one specific restricted setting: multi-item auctions with indivisible goods and unit-demand bidders (possibly with budget limits). We will see how algorithms for computing Market equilibria come into play.

To pique your interest, consider these questions: How does Google sell the advertisement slots on your search page? You may have already heard that they use a "generalized second price" (GSP) auction mechanism. But why do they do so? Is there any "better" way to conduct these auctions?
(And what does "better" actually mean?)

Auction theory is a beautiful and highly developed part of economic theory and game theory, with a long history and with several Nobel prizes to its credit. In recent years, there has been increasing interaction between research in algorithms theory and auction theory/mechanism design, under the broader title of "algorithmic game theory".

This increased interaction is happening for several reasons. Firstly, more and more of the world's economic transactions are taking place online, often in a (semi-)automated fashion, and often enough via auctions. In such settings, efficient algorithms take on added importance, because for example large electronic auctions are being conducted repeatedly, and they need to be cleared very quickly. Secondly, this interaction is also taking place at a more fundamental theoretical level, because in some important auction settings, like "combinatorial auctions", some of the solutions prescribed by traditional auction theory would actually entail solving theoretically intractable computational problems (NP-hard, etc.). So the theory needs to be adjusted if it wants to take computational complexity into consideration.

To give a brief feel for these research topics, I will focus on just one well-studied setting: multi-item auctions with indivisible goods in the unit-demand setting (and budget limits). Google's GSP advertisement auctions can be (roughly speaking) viewed as a particular subcase of such auctions. (But I will not discuss the intricacies of this subcase.)

Document Actions