Monday, April 05, 2010
11:00 AM
Computer Studies Bldg. Room 209
Ian Kash
Harvard University
Algorithmic Market Design: Currency Crashes, Spectrum Sales, and Lying Hospitals
Markets are a powerful tool for producing desirable outcomes in an engineered system. As computers allow us to build new and more complex markets, we need new theory and algorithms to understand, build, and improve them. In this talk I'll cover three examples of such markets, involving fake money, real money, and no money at all.

Scrip systems, where users pay for service with an artificial currency (scrip) created for the system, are an attractive solution to free riding and other problems in P2P and distributed systems. Despite the interest in building scrip systems, relatively little work has been done to help answer basic design questions. For example, how much money should there be in the system? What will happen if some of the users start giving away service or hoarding money? I'll show how a simple algorithm provides insight into these questions.

Until recently, if you wanted to start a business that requires using wireless spectrum, you would either have to pay tens of millions of dollars for an exclusive license or use one of the few congested frequencies that are available without a license (such as the one used by WiFi). Recently, people have begun investigating how auctions can be used to sell smaller amounts of spectrum. I'll present a new auction algorithm that takes advantage of the ability of devices to share spectrum to significantly improve both spectrum utilization and social welfare.

Eventually, patients with kidney disease need a new kidney. Luckily, we can live with only one kidney so donation is possible, so many patients are able to receive a new kidney from a family member or friend. However, not all donors and patients are compatible. A recent innovation is the idea of a kidney exchange, where two donors who are incompatible with their intended patients instead supply a kidney to the other's patient. Hospitals have begun to participate in programs to organize exchanges, but not all of them truthfully report all of their available patients. I'll introduce a new matching algorithm that removes the incentive for hospitals to lie.

Bio: Ian Kash is a postdoctoral fellow at the Center for Research on Computation and Society at Harvard University. He received his B.S. from Carnegie Mellon University and his Ph.D. from Cornell University. His thesis, "Robustness and Optimization of Scrip Systems," was advised by Eric Friedman and Joseph Halpern. His research interests include market design, (algorithmic) game theory, theoretical aspects of systems, and multi-agent learning.

Refreshments will be provided at 10:45 AM