| Description |
Suppose we want to design an auction for selling items to a set of customers. Such an auction will take the valuations of the customers as input, and specify the allocation of the items and the payments. A crucial aspect of this setting is the strategic behaviors of the customers: Each customer is a self-interested agent, and she is willing to manipulate the scheme by misreporting her valuation if that results in an outcome that is more favorable to her. The auction has to be robust to such manipulations. We say an auction is truthful if no customer has an incentive to misreport. The objective is to come up with a truthful auction that either generates large revenue, or maximizes the total utility of all the participants.
Auction Theory has a rich literature in Economics. However, it is difficult to characterize the optimal auction in many settings. This consideration, coupled with the advent of internet advertising where the search engines generate huge amount of revenue by auctioning online ad-slots, has motivated the Computer Science community to revisit Auction Theory from an algorithmic perspective. Here, we want to design approximately optimal auctions whose outcomes can be computed in polynomial time. I will present some recent results that fall under the purview of this general research agenda.
|