Embedded Files
Format
Format
This will be a full-day workshop at the ACM Symposium on Theory of Computing (STOC) in Phoenix, Arizona. It will be held on Sunday, June 23rd, 2019. The workshop will accept walk-ins from other FCRC conferences.
The first half of the workshop will be a tutorial presented by Nina Balcan, Tuomas Sandholm, and Ellen Vitercik. The second half will feature invited talks from Vincent Conitzer, Nika Haghtalab, David Parkes, and Tim Roughgarden.
Abstract
Abstract
Mechanism design is a field of game theory with significant real-world impact, encompassing areas such as pricing and auction design. Mechanisms are used in sales settings ranging from large-scale internet marketplaces to the US government's radio spectrum reallocation efforts. A powerful and prominent approach in this field is automated mechanism design, which uses optimization and machine learning to design mechanisms based on data. This automated approach helps overcome challenges faced by traditional, manual approaches to mechanism design, which have been stuck for decades due to inherent computational complexity challenges: the revenue-maximizing mechanism is not known even for just two items for sale! This workshop is focused on the rapidly growing area of automated mechanism design for revenue maximization. This encompasses both the foundations of batch and online learning (including statistical guarantees and optimization procedures), as well as real-world success stories.
Schedule
Schedule
9 - 10:45 AM: Tutorial by Nina Balcan, Tuomas Sandholm, and Ellen Vitercik
10:45 - 11 AM: Coffee break
11 AM - 12:30 PM: Tutorial continued
12:30 - 2:20 PM: Lunch
2:20-2:50 PM: Invited talk by Vince Conitzer
Title: New Directions in Automated Mechanism Design
Abstract: I will discuss two lines of work. The first centers on a result by Cremer and McLean, which states that if there is even a little correlation among the bidders' valuations, then it is possible for the seller to design a mechanism that allocates efficiently and extracts the entire surplus as revenue! This seems too good to be true and the result is often ignored, but why? AMD, with some new extensions, can give insight into this. (Joint work with Michael Albert, Pino Lopomo, and Peter Stone.)
In the second line, I discuss AMD for settings where misreporting is limited or costly. Our work here is primarily inspired by machine learning applications where the data is provided by a strategic agent that prefers to be classified in a particular way. We consider in detail the case where an agent can strategically withhold some of its samples (or parts of its samples), but not modify them arbitrarily. For example, an entity bidding to host an event will submit only the most flattering footage of its site -- but usually cannot get away with submitting entirely fake footage. (Joint work with Hanrui Zhang, Yu Cheng, and Andrew Kephart.)
2:55-3:25 PM : Invited talk by Nika Haghtalab
Title: Online Auctions via Offline Auctions: Oracle-Efficient Online Learning and applications to Auction Design
Abstract: We consider the design of computationally efficient online learning algorithms in an adversarial setting in which the learner has access to an offline optimization oracle. We present an algorithm and provide structural properties under which this algorithm is oracle-efficient and achieves vanishing regret. These results make significant progress on an open problem raised by Hazan and Koren, who showed that oracle-efficient algorithms do not exist in general and asked whether one can identify properties under which oracle-efficient online learning may be possible.
We apply these results to the problem of online learning of auctions in adversarial settings, with the goal of achieving revenue that is almost as good as the optimal auction in hindsight. We show that many auction classes demonstrated the structural properties needed for our oracle-efficient no-regret algorithm to work. This gives oracle-efficient learning results for a number of auction classes, including 2nd price auctions with bidder-specific reserves, envy-free item pricing, and Myerson-like auctions.
3:30 - 3:45 PM: Coffee break
3:45 - 4:15 PM: Invited talk by David Parkes
Title: Optimal Auction Design through Deep Learning
Abstract: Designing an auction that maximizes expected revenue is a major open problem in economics. Despite significant effort, only the single-item case is fully understood. We ask whether the tools of deep learning can be used to make progress. We show that multi-layer neural networks can learn essentially optimal auction designs for the few problems that have been solved analytically, and can be used to design auctions for poorly understood problems, including settings with multiple items and budget constraints. I will discuss some of the future directions that come from learning theory, deep learning, and economics. This is joint work with Paul Duetting (London School of Economics), Zhe Feng (Harvard University), Harikrishna Narasimhan (Google), and Sai Srivatsa (Harvard University).
4:20 - 4:50 PM: Invited talk by Tim Roughgarden
Title: Application-Specific Algorithm Selection
Tutorial outline
Tutorial outline
Outline.pdfInvited speakers
Invited speakers
Vincent Conitzer is the Kimberly J. Jenkins University Professor of New Technologies and Professor of Computer Science, Professor of Economics, and Professor of Philosophy at Duke University. He received Ph.D. (2006) and M.S. (2003) degrees in Computer Science from Carnegie Mellon University, and an A.B. (2001) degree in Applied Mathematics from Harvard University. Conitzer works on artificial intelligence (AI). Much of his work has focused on AI and game theory, for example designing algorithms for the optimal strategic placement of defensive resources. More recently, he has started to work on AI and ethics: how should we determine the objectives that AI systems pursue, when these objectives have complex effects on various stakeholders?
Conitzer has received the Social Choice and Welfare Prize, a Presidential Early Career Award for Scientists and Engineers (PECASE), the IJCAI Computers and Thought Award, an NSF CAREER award, the inaugural Victor Lesser dissertation award, an honorable mention for the ACM dissertation award, and several awards for papers and service at the AAAI and AAMAS conferences. He has also been named a Guggenheim Fellow, a Kavli Fellow, a Bass Fellow, a Sloan Fellow, a AAAI Fellow, and one of AI's Ten to Watch. He has served as program and/or general chair of the AAAI, AAMAS, AIES, COMSOC, and EC conferences. Conitzer and Preston McAfee were the founding Editors-in-Chief of the ACM Transactions on Economics and Computation (TEAC).
Nika Haghtalab is a postdoctoral researcher at Microsoft Research, New England. In summer 2019, she will join the Department of Computer Science at Cornell University as an Assistant Professor. Her research is on the theoretical aspects of machine learning and algorithmic economics. She is especially interested in developing a theory for machine learning that accounts for its interactions with people and organizations, and the wide variety of social and economic limitations, aspiration, and behavior they demonstrate.
She recently received the Ph.D. degree from the Computer Science Department of Carnegie Mellon University, where she was co-advised by Avrim Blum and Ariel Procaccia. Her honors include the CMU School of Computer Science Dissertation award (2018), a Microsoft Research fellowship, a Facebook fellowship, an IBM fellowship, and a Siebel scholarship.
David Parkes leads research at the interface between economics and computer science, with a focus on multi-agent systems, artificial intelligence and machine learning. This is a vibrant field, encompassing questions about market design, dynamic pricing, preference elicitation, digital currency, reputation, and the increasing role that artificial intelligences will play in mediating transactions of all kinds.
Parkes founded the EconCS research group within the Paulson School, and is co-director of the Harvard University Data Science Initiative, and co-chair of the Harvard Business Analytics certificate program and the FAS Data Science Masters. Earlier, Parkes was Area Dean for Computer Science, 2013-2017. He served on the inaugural panel of the "Stanford 100 Year Study on Artificial Intelligence," co-organized the 2016 OSTP Workshop on "AI for Social Good," and served as chair of the ACM Special Interest Group on Electronic Commerce (2011-16). Since 2018, Parkes has served on the Computing Community Consortium (CCC) of the Computing Research Association.
Parkes is Fellow of the Association for the Advancement of Artificial Intelligence (AAAI), and recipient of the 2017 ACM/SIGAI Autonomous Agents Research Award, the NSF Career Award, the Alfred P. Sloan Fellowship, the Thouron Scholarship, and the Roslyn Abramson Award for Teaching. Parkes has degrees from the University of Oxford and the University of Pennsylvania, serves on several international scientific advisory boards, and is a technical advisor to a number of start-ups.
Tim Roughgarden is a Professor of Computer Science at Columbia University. Prior to joining Columbia, he spent 15 years on the computer science faculty at Stanford, following a PhD at Cornell and a postdoc at UC Berkeley. His research interests include the many connections between computer science and economics, as well as the design, analysis, applications, and limitations of algorithms. For his research, he has been awarded the ACM Grace Murray Hopper Award, the Presidential Early Career Award for Scientists and Engineers (PECASE), the Kalai Prize in Computer Science and Game Theory, the Social Choice and Welfare Prize, the Mathematical Programming Society's Tucker Prize, and the EATCS-SIGACT Gödel Prize. He was an invited speaker at the 2006 International Congress of Mathematicians, the Shapley Lecturer at the 2008 World Congress of the Game Theory Society, and a Guggenheim Fellow in 2017. His books include Twenty Lectures on Algorithmic Game Theory (2016) and the Algorithms Illuminated book series (2017-2019).
Organizers' bios
Organizers' bios
Maria-Florina Balcan is an Associate Professor in the School of Computer Science at Carnegie Mellon University. Her main research interests are machine learning, computational aspects in economics and game theory, and algorithms. Her honors include the CMU SCS Distinguished Dissertation Award, an NSF CAREER Award, a Microsoft Faculty Research Fellowship, a Sloan Research Fellowship, and several paper awards. She was a program committee co-chair for the Conference on Learning Theory in 2014 and for the International Conference on Machine Learning in 2016. She is currently board member of the International Machine Learning Society (since 2011), a Tutorial Chair for ICML 2019, a Workshop Chair for FOCS 2019, and the General Chair for ICML 2021.
Tuomas Sandholm is Angel Jordan Professor of Computer Science at Carnegie Mellon University. He is Founder and Director of the Electronic Marketplaces Laboratory. He has published over 500 papers. With his student Vince Conitzer, he initiated the study of automated mechanism design in 2001. 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, Strategic Machine, and Strategy Robot. Also, his algorithms run the UNOS kidney exchange, which includes 69% 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 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. 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, Newell Award for Research Excellence, Computers and Thought Award, and Marvin Minsky Medal. He is Fellow of the ACM, AAAI, and INFORMS. He holds an honorary doctorate from the University of Zurich.
Ellen Vitercik is a PhD student in computer science at Carnegie Mellon University (CMU). Her primary research interests are artificial intelligence, machine learning, theoretical computer science, and the interface between economics and computation. Among other honors, she is a recipient of the IBM PhD Fellowship, the Fellowship in Digital Health from CMU's Center for Machine Learning and Health, and the NSF Graduate Research Fellowship.
Google Sites
Report abuse