Tuesday May 10th, 2016. Singapore.
- 08.30-09.00: Registration
- 09.00-9.15: Opening / Welcome
- 9.15 – 10:30: Session Chair: John P. Dickerson
- Rohit Vaish and Neeldhara Misra – On the Parameterized Complexity of Manipulating Pairwise Voting Rules
- Aaron Koolyk, Omer Lev and Jeffrey S. Rosenschein – Convergence and Quality of Iterative Voting Under Non-Scoring Rules
- Yoram Bachrach, Omer Lev, Yoad Lewenberg and Yair Zick – Misrepresentation in District Voting
- 10:30 – 11:00: Coffee Break
- 11:00 – 11:20: 1 Paper
- Dominik Peters and Edith Elkind – Preferences Single-Peaked on Nice Trees
- 11:25 – 12:30: Invited Talk by Tuomas Sandholm
- Public Choice and Revenue-Maximizing Combinatorial Auctions: New Results and Automated Mechanism DesignDesigning revenue-maximizing combinatorial auctions (CAs) is an important elusive problem, unsolved even for two bidders and two items. Rather than attempting to characterize the optimal CA, there has been research into automated mechanism design, where the most scalable techniques involve conducting the design of a high-revenue CA computationally via a search over a parameterized class of strategyproof, individually-rational CAs [Likhodedov & Sandholm, AAAI-04, -05; Sandholm & Likhodedov, Operations Research 2015]. We will discuss a hierarchy of such auctions: affine maximizer auctions, virtual valuations CAs, lambda-auctions, and mixed bundling auctions with and without reserve prices. It is assumed that the design algorithm has access to random samples from the distribution over the bidders’ valuations. We [Balcan, Sandholm & Vitercik 2016] present the first theory that ties together the revenue of the mechanism on the sample and the revenue of the mechanism on the real distribution. The proof techniques involve Rademacher complexity, pseudo-dimension, and new structural insights.
The second part of the talk studies efficiency and budget balance in mechanism design in the quasi-linear domain [Nath & Sandholm 2016]. Green and Laffont [1979] proved that one cannot generically achieve both. We consider strategyproof budget-balanced mechanisms that are approximately efficient. For deterministic mechanisms, we show that a strategyproof and budget-balanced mechanism must have a sink agent whose valuation function is ignored in selecting an alternative, and she is given the payments made by the other agents. We assume the valuations of the agents are drawn from a bounded open interval. This result strengthens Green and Laffont’s impossibility by showing that even in a restricted domain of valuations, there does not exist a mechanism that is strategyproof, budget balanced, and takes every agent’s valuation into consideration—a corollary of which is that it cannot be efficient. Using this result, we find a tight lower bound on the inefficiencies of strategyproof, budget-balanced mechanisms in this domain. The bound shows that the inefficiency asymptotically disappears
when the number of agents is large—a result close in spirit to Green and Laffont [1979, Theorem 9.4]. However, our results provide worst-case bounds and the best possible rate of convergence. Next, we consider minimizing any convex combination of inefficiency and budget imbalance. We show that no deterministic mechanism can do asymptotically better than minimizing inefficiency alone. Finally, we investigate randomized mechanisms and provide improved lower bounds on expected inefficiency. We give a tight lower bound for an interesting class of strategyproof, budget-balanced, randomized mechanisms. Finally, we use automated mechanism design to provide a lower bound on the minimum achievable inefficiency of any randomized mechanism.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 27 years of experience building optimization-powered electronic marketplaces, 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. Dr. Sandholm’s algorithms also run the UNOS kidney exchange, which includes 66% of the transplant centers in the US. He is Founder and CEO of Optimized Markets, Inc., a startup that is bringing a new paradigm to advertising campaign sales and scheduling – in TV (linear and non-linear), Internet display, radio, mobile, game, and cross-media advertising. He also 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 better monetization. He has served as consultant, advisor, or board member for Yahoo!, Google, Chicago Board Options Exchange, swap.com, Granata Decision Systems, and others. He has developed the leading algorithms for several general classes of game. The team that he leads is the reigning two-time world champion in computer Heads-Up No-Limit Texas Hold’em. 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.
- Public Choice and Revenue-Maximizing Combinatorial Auctions: New Results and Automated Mechanism DesignDesigning revenue-maximizing combinatorial auctions (CAs) is an important elusive problem, unsolved even for two bidders and two items. Rather than attempting to characterize the optimal CA, there has been research into automated mechanism design, where the most scalable techniques involve conducting the design of a high-revenue CA computationally via a search over a parameterized class of strategyproof, individually-rational CAs [Likhodedov & Sandholm, AAAI-04, -05; Sandholm & Likhodedov, Operations Research 2015]. We will discuss a hierarchy of such auctions: affine maximizer auctions, virtual valuations CAs, lambda-auctions, and mixed bundling auctions with and without reserve prices. It is assumed that the design algorithm has access to random samples from the distribution over the bidders’ valuations. We [Balcan, Sandholm & Vitercik 2016] present the first theory that ties together the revenue of the mechanism on the sample and the revenue of the mechanism on the real distribution. The proof techniques involve Rademacher complexity, pseudo-dimension, and new structural insights.
- 12:30 – 14:00: Lunch
- 14:00 – 15:30: Session Chair: Omer Lev
- Haris Aziz, Jiashu Chen, Aris Filos-Ratsikas, Simon Mackenzie and Nicholas Mattei – Egalitarianism of Random Assignment Mechanisms
- Hadi Hosseini, Kate Larson and Robin Cohen – An Empirical Comparison of One-Sided Matching Mechanisms
- George Christodoulou, Aris Filos-Ratsikas, Søren Stiil Frederiksen, Paul Goldberg, Jie Zhang and Jinshan Zhang – Social Welfare in One-Sided Matching Mechanisms
- Rupert Freeman, Seyed Majid Zahedi and Vincent Conitzer – Fair Social Choice in Dynamic Settings
- 15:30 – 16:00: Coffee Break
- 16:00 – 17:15: Session Chair: Nicholas Mattei
- Mathijs De Weerdt, Enrico Gerding and Sebastian Stein – Minimising the Rank Aggregation Error
- Baharak Rastegari, Paul Goldberg and David Manlove – Preference elicitation in matching markets via interviews: A study of offline benchmarks
- John P. Dickerson, Aleksandr M. Kazachkov, Ariel D. Procaccia and Tuomas Sandholm – Small Representations of Big Kidney Exchange Graphs