# 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.)