2021 Responsible Machine Learning Summit: AI anD Social Good
Tuomas Sandholm, Angel Jordan University Professor of Computer Science, Carnegie Mellon University
Co-Director, CMU AI
Founder and Director, Electronic Marketplaces Laboratory
Founder, President, and CEO, Optimized Markets, Inc.
Founder, President, and CEO, Strategy Robot, Inc.
Founder, President, and CEO, Strategic Machine, Inc.
Sample Complexity of (Automated) Mechanism Design
Abstract: Automated mechanism design, introduced by Conitzer and Sandholm in UAI-02, changes mechanism design from a manual analytical endeavor to a computational search problem. This has many advantages and broad applicability. Typically in mechanism design it is assumed that the designer has a prior over the agents’ preferences. This is often unrealistic, especially in multi-dimensional settings. For example, in a combinatorial auction, the prior for just a single bidder would have a number of support points that is doubly exponential in the number of items. To address this, Sandholm and Likhodedov introduced the idea of mechanism design with just samples from the prior. This raises the question: how many samples are sufficient to ensure that a mechanism that performs well on the samples also performs well on the full, unknown prior? I will discuss structure shared by a myriad of pricing, auction, and lottery mechanisms that allows us to prove strong sample complexity bounds: for any set of agents’ preferences, the objective is a piecewise linear function of the mechanism's parameters. We prove new bounds for mechanism classes not previously studied in the sample-based mechanism design literature and match or improve over the best known guarantees for many classes. The functions we study are significantly different from well-understood functions in machine learning, so our analysis requires a sharp understanding of the interplay between mechanism parameters and agents’ preferences. We strengthen our main results with data-dependent bounds when the distribution over agents’ preferences is well-behaved. We investigate a fundamental tradeoff in sample-based mechanism design: complex mechanisms often have higher objective value than simple mechanisms, but more samples are required to ensure that empirical and expected objective are close. We provide techniques for optimizing this tradeoff. I will then present an even more general recent sample complexity theory, which we have used also for voting and redistribution mechanism design. I will then discuss how similar techniques can be used to estimate the approximate incentive compatibility of non-incentive-compatible mechanisms. Finally, I will discuss new work on learning within an instance, applied to combinatorial auctions and to revenue preservation in a shrinking multi-unit market.
The talk covers selected results from the following papers:
How Much Data is Sufficient to Learn High-Performing Algorithms?
STOC-21; version that includes voting and redistribution experiments at
https://arxiv.org/pdf/1908.02894.pdf
With M-F. Balcan, D. DeBlasio, T. Dick, C. Kingsford and E. Vitercik.
A General Theory of Sample Complexity for Multi-Item Profit Maximization
Abstract in EC-18; long version at https://arxiv.org/abs/1705.00243
With M-F. Balcan and E. Vitercik.
Estimating Approximate Incentive Compatibility
Abstract in EC-19; long version at https://arxiv.org/pdf/1902.09413.pdf
With M-F. Balcan and E. Vitercik.
Learning Within an Instance for Designing High-Revenue Combinatorial Auctions
IJCAI-21: https://www.ijcai.org/proceedings/2021/5
With M-F. Balcan and S. Prasad.
Preserving Revenue in a Shrinking Market
https://www.cs.cmu.edu/~sprasad2/papers/market_shrinkage.pdf
With M-F. Balcan and S. Prasad.
Efficient Algorithms for Learning Revenue-Maximizing Two-Part Tariffs
IJCAI-20: https://www.ijcai.org/Proceedings/2020/0047.pdf
With M-F. Balcan and S. Prasad.
Automated Design of Revenue-Maximizing Combinatorial Auctions
Operations Research 63(5), 1000-1025. (Subsumes and extends over a AAAI-05 paper and a AAAI-04 paper.) http://www.cs.cmu.edu/~sandholm/AMD%20for%20CAs.OR%20articles%20in%20advance.pdf
With A. Likhodedov.
Biosketch: Tuomas Sandholm is Angel Jordan University Professor of Computer Science at Carnegie Mellon University and a serial entrepreneur. His research focuses on the convergence of artificial intelligence, economics, and operations research. He is Co-Director of CMU AI. He is the Founder and Director of the Electronic Marketplaces Laboratory. He has published over 500 peer-reviewed papers and holds 25 patents. In addition to his main appointment in the Computer Science Department, he holds appointments in the Machine Learning Department, Ph.D. Program in Algorithms, Combinatorics, and Optimization (ACO), and CMU/UPitt Joint Ph.D. Program in Computational Biology.
In parallel with his academic career, he was Founder, Chairman, first CEO, 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 generalized combinatorial auctions, with over $60 billion in total spend and over $6 billion in generated savings.
Since 2010, his algorithms have been running the national kidney exchange for the United Network for Organ Sharing, where they autonomously make the kidney exchange transplant plan for 80% of U.S. transplant centers together each week. He also co-invented never-ending altruist-donor-initiated chains and his algorithms created the first such chain. Such chains have become the main modality of kidney exchange worldwide and have led to around 10,000 life-saving transplants. He invented liver lobe and multi-organ exchanges, and the first liver-kidney swap took place in 2019.
He is Founder and CEO of Optimized Markets, Inc., which is bringing a new optimization-powered expressive market paradigm to advertising campaign sales, pricing, allocation, and scheduling across media types.
He has developed the leading algorithms for many general classes of game with his students. The team that he leads is the multi-time world champion in computer heads-up no-limit Texas hold’em, which is the main benchmark and decades-open challenge problem for testing application-independent algorithms for solving imperfect-information games. Their AI Libratus became the first and only AI to beat top humans at that game. Then their AI Pluribus became the first and only AI to beat top humans at the multi-player game. That is the first superhuman milestone in any game beyond two-player zero-sum games. He is Founder and CEO of Strategic Machine, Inc., which provides solutions for strategic reasoning under imperfect information in a broad set of applications ranging from poker to other recreational games to business strategy, negotiation, strategic pricing, finance, cybersecurity, physical security, auctions, political campaigns, and medical treatment planning. He is Founder and CEO of Strategy Robot, Inc., which focuses on defense applications.
He served as the redesign consultant of Baidu’s sponsored search auctions and display advertising markets; within two years Baidu’s market cap increased 5x to $50 billion due to doubled monetization per user. He has served as consultant, advisor, or board member for Yahoo!, Google, Chicago Board Options Exchange, swap.com, Granata Decision Systems (now part of Google), Rare Crowds (now part of Media Math), and others.
He holds a Ph.D. and M.S. in computer science and a Dipl. Eng. (M.S. with B.S. included) with distinction in Industrial Engineering and Management Science. Among his honors are the Minsky Medal, John McCarthy Award, Engelmore Award, Computers and Thought Award, inaugural ACM Autonomous Agents Research Award, CMU’s Allen Newell Award for Research Excellence, Sloan Fellowship, NSF Career Award, Carnegie Science Center Award for Excellence, Edelman Laureateship, and Goldman Sachs’s 100 Most Intriguing Entrepreneurs. He is Fellow of the ACM, AAAI, and INFORMS. He holds an honorary doctorate from the University of Zurich.