Keynote Speakers
Invited talk by Shuchi Chawla
Shuchi Chawla, University of Wisconsin-Madison, USA
Title: Buy-Many Mechanisms Are Not Much Better Than Item Pricing
Multi-item revenue-optimal mechanisms can be very complex offering an unbounded number of randomized bundles or lotteries to the buyer. Such complexity is thought to be necessary as the revenue gaps between randomized and deterministic mechanisms, or deterministic and simple mechanisms are huge even for additive valuations. We show that such complexity and large gaps can only arise in situations where buyers' actions are severely restricted. These are situations where the mechanism sells a bundle of items at a higher price than the sum of the prices of the constituent items and buyers wanting to purchase such a bundle must pay this premium as they are not allowed to purchase the constituents separately. Our main result is that if the buyer is allowed to purchase as many (randomized) bundles as he pleases, the revenue of any multi-item mechanism is at most $O(\log n)$ times the revenue achievable by item pricing, where $n$ is the number of items. This holds in the most general setting possible, with an arbitrarily correlated distribution of buyer types and arbitrary valuations. We also show that this result is tight in a very strong sense. Any family of mechanisms of subexponential description complexity cannot achieve better than logarithmic approximation even against the best deterministic mechanism and even for additive valuations. In contrast, item pricing that has linear description complexity matches this bound against randomized mechanisms. This talk is based on joint work with Yifeng Teng and Christos Tzamos.
Short bio:
Shuchi Chawla received a B.Tech. in Computer Science from the Indian Institute of Technology, Delhi and a Ph.D. in Computer Science from Carnegie Mellon University. After postdocs at Stanford University and Microsoft Research Silicon Valley, she joined the University of Wisconsin-Madison, where she is now Professor of Computer Sciences. Shuchi’s research interests include the design and analysis of approximation algorithms, online algorithms, algorithmic game theory and mechanism design, and combinatorial and stochastic optimization. Shuchi is the recipient of an NSF Career award, a Sloan Foundation fellowship, and UW-Madison's Carolyn Rosner Award for Excellence in Teaching. She currently serves on the editorial boards of the ACM Transactions on Algorithms, and the ACM Transactions on Economics and Computation. She 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.
Invited talk by Michael I. Jordan
Michael I. Jordan, University of California, Berkeley, USA
Title: Towards a Blend of Machine Learning and Microeconomics
Statistical decisions are often given meaning in the context of other decisions, particularly when there are scarce resources to be shared. Managing such sharing is one of the classical goals of microeconomics, and it is given new relevance in the modern setting of large, human-focused datasets, in data-analytic contexts such as classifiers and recommendation systems. I'll discuss several recent projects that aim to explore this interface: (1) exploration-exploitation tradeoffs for bandits that compete over a scarce resource, (2) gradient-based algorithms that find Nash equilibria, and only Nash equilibria; (3) notions of local optimality in nonconvex-nonconcave minimax optimization, and how such notions relate to stochastic gradient methods; and (4) economic perspectives on online control of false-discovery rates.
Short bio:
Michael I. Jordan is the Pehong Chen Distinguished Professor in the
Department of Electrical Engineering and Computer Science and the
Department of Statistics at the University of California, Berkeley.
His research interests bridge the computational, statistical, cognitive
and biological sciences. Prof. Jordan is a member of the National Academy
of Sciences and a member of the National Academy of Engineering.
He has been named a Neyman Lecturer and a Medallion Lecturer by the
Institute of Mathematical Statistics, and he has given a Plenary Lecture
at the International Congress of Mathematicians. He received the IEEE
John von Neumann Medal in 2020, the IJCAI Research Excellence Award in
2016, the David E. Rumelhart Prize in 2015, and the ACM/AAAI Allen Newell
Award in 2009.
Invited talk by Tuomas Sandholm
Tuomas Sandholm, Carnegie Mellon University, USA
Title: Superhuman AI for Multiplayer Poker
In recent years there have been great strides in AI, with games often serving as challenge problems, benchmarks, and milestones for progress. Poker has served for decades as such a challenge problem. Past successes in such benchmarks, including poker, have been limited to two-player games. However, poker in particular is traditionally played with more than two players. Multiplayer games present fundamental additional issues beyond those in two-player games, and multiplayer poker is a recognized AI milestone. In this paper we present Pluribus, an AI that we show is stronger than top human professionals in six-player no-limit Texas hold’em poker, the most popular form of poker played by humans. To our knowledge, this is the first superhuman AI for a multiplayer game. It is based on our new techniques such as depth-limited lookahead for imperfect-information games and equilibrium-finding algorithms that are significantly more scalable than prior approaches. This is joint work with my PhD student Noam Brown.
Short bio: Tuomas is Angel Jordan Professor of Computer Science at CMU and Co-Director of CMU AI. He holds appointments in the Computer Science Department, Machine Learning Department, Ph.D. Program in Algorithms, Combinatorics, and Optimization (ACO), and CMU/UPitt Joint Ph.D. Program in Computational Biology. He is the Founder and Director of the Electronic Marketplaces Laboratory. In parallel with his academic career, he was Founder, Chairman, and CTO/Chief Scientist of CombineNet, Inc. from 1997 until its acquisition in 2010. During this period the company commercialized over 800 of the world's largest-scale combinatorial multi-attribute sourcing auctions with $60 billion in volume and over $6 billion in generated savings. His CMU algorithms run the UNOS national kidney exchange, which includes 173 transplant centers, that is, 73% of the transplant centers in the US. Since the founding of the exchange in 2010, his algorithms make the life-and-death kidney exchange decisions autonomously for those centers together each week. He is Founder and CEO of Optimized Markets, which is bringing a new optimization-powered paradigm to advertising campaign sales, scheduling, and pricing—in linear and nonlinear TV, Internet display, video and audio streaming, mobile, game, radio, and cross-media advertising. He is Founder and CEO of Strategic Machine, which is fielding his game-solving techniques to business, recreational gaming, and finance applications. He is Founder and CEO of Strategy Robot, which is fielding his game-solving techniques to defense applications. Among his honors are the Minsky Medal, Computers and Thought Award, inaugural ACM Autonomous Agents Research Award, Allen Newell Award for Research Excellence, Edelman Laureateship, Sloan Fellowship, Carnegie Science Center Award for Excellence, and NSF Career Award. He is Fellow of the ACM, AAAI, and INFORMS. He holds an honorary doctorate from the University of Zurich.
