Speaker: Prof. Tuomas Sandholm Carnegie Mellon University(CMU)
Time: 2017-11-07 16:30-2017-11-07 17:15
Venue: FIT 1-312
Abstract:
We study the design of pricing mechanisms and auctions when the mechanism designer does not know the distribution of buyers' values. Instead the mechanism designer receives a set of samples from this distribution and his goal is to use the sample to design a pricing mechanism or auction with high expected profit. We provide generalization guarantees which bound the difference between average profit on the sample and expected profit over the distribution. These bounds are directly proportional to the intrinsic complexity of the mechanism class the designer is optimizing over. We present a single, overarching theorem that uses empirical Rademacher complexity to measure the intrinsic complexity of a variety of widely-studied single- and multi-item auction classes, including affine maximizer auctions, mixed-bundling auctions, and second-price item auctions. Despite the extensive applicability of our main theorem, we match and improve over the best-known generalization guarantees for many auction classes. This all-encompassing theorem also applies to multi- and single-item pricing mechanisms in both multi- and single-unit settings, such as linear and non-linear pricing mechanisms. Finally, our central theorem allows us to easily derive generalization guarantees for every class in several finely grained hierarchies of auction and pricing mechanism classes. We demonstrate how to determine the precise level in a hierarchy with the optimal tradeoff between profit and generalization using structural profit maximization. The mechanism classes we study are significantly different from well-understood function classes typically found in machine learning, so bounding their complexity requires a sharp understanding of the interplay between mechanism parameters and buyer valuations.
Short Bio:
Tuomas Sandholm is Professor at Carnegie Mellon University in the Computer Science Department, with affiliate professor 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. He is the Founder and Director of the Electronic Marketplaces Laboratory. He has published over 450 papers. He has built optimization-powered electronic marketplaces since 1989, and has fielded several of his systems. 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 generalized combinatorial multi-attribute auctions, with over $60 billion in total spend and over $6 billion in generated savings.
He is Founder and CEO of Optimized Markets, Inc., which is bringing a new paradigm to advertising campaign sales and scheduling - in TV (linear and digital), Internet display, mobile, game, radio, and cross-media advertising.
His algorithms run the UNOS kidney exchange, which includes 66% of the transplant centers in the US.
He has developed the leading algorithms for several general classes of game. The team that he leads is the current two-time world champion in computer Heads-Up No-Limit Texas Hold’em poker, and Libratus became the first and only AI to beat top humans at that game. 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, military, auctions, political campaigns, and medical treatment planning.
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, 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 many honors are the NSF Career Award, inaugural ACM Autonomous Agents Research Award, Sloan Fellowship, Carnegie Science Center Award for Excellence, Edelman Laureateship, and Computers and Thought Award. He is Fellow of the ACM, AAAI, and INFORMS. He holds an honorary doctorate from the University of Zurich.
