SCS Special Seminar

  • Gates Hillman Centers
  • ASA Conference Room 6115
  • Professor of Computer Sciences
  • Computer Sciences Department
  • University of Wisconsin - Madison

How to price an app, and other algorithmic problems in the design of modern electronic marketplaces

Algorithms form the backbone of new electronic marketplaces such as online advertising, online retail, the cloud market, and the rideshare industry, and play an increasingly important role in our lives. Designing good algorithms for these settings requires a combination of computational and economic insights: these new marketplaces exhibit rich combinatorial structure, a previously unseen scale of microtransactions, and the need for rapid real-time decision making; and, economics provides the behavior models that determine how people or businesses strategize and interact in these systems. In this talk I will describe the theory underlying algorithm design for such strategic settings, a.k.a. mechanism design.

The first part of the talk will discuss revenue maximization, a notoriously challenging objective in mechanism design. I will describe simple mechanisms that provide good approximations to the optimal revenue under fairly general assumptions. The second part of the talk addresses maximization of social welfare or economic efficiency, another classical objective within economics. While this objective is well-understood in "one-shot" settings, I will discuss "online" settings where users interact with the mechanism one at a time like buyers arriving over time in a store. Throughout the talk, I will also touch upon approaches for incorporating more realistic design constraints: realistic behavior models; learning in the context of mechanism design; and economic approaches to algorithmic fairness.

Shuchi Chawla is a Professor of Computer Sciences at the University of Wisconsin-Madison. She holds a B.Tech. in Computer Science from the Indian Institute of Technology, Delhi and a Ph.D. in Computer Science from Carnegie Mellon University. Shuchi’s research interests include approximation algorithms, online algorithms, algorithmic game theory and mechanism design, and economic approaches to algorithmic fairness. Shuchi is the recipient of an NSF Career award, a Sloan Foundation fellowship, UW-Madison's Carolyn Rosner Award in Teaching, and Chancellor's Teaching Innovation Award. She currently serves on the editorial boards of the ACM Transactions on Algorithms and the ACM Transactions on Economics and Computation, and recently served as PC chair for the SODA'20 conference. Shuchi is an elected member of the ACM SIGACT executive committee and currently serves as chair of the SIGACT Committee for the Advancement of Theoretical Computer Science.

Faculty Host: Anupam Gupta

Zoom participation enabled. See announcement for registration details.

For More Information, Please Contact: