The scientific program of WINE 2015 will include four invited talks. The confirmed speakers are:
- Michal Feldman, Tel-Aviv University, Israel
- Paul Goldberg, University of Oxford, UK
- Ramesh Johari, Stanford University, USA
- Paul Milgrom, Stanford University, USA
See below for more information.
Invited talk by Michal Feldman
Speaker: Michal Feldman, Tel-Aviv University, Israel
Abstract: In algorithmic mechanism design, we would like desired economic properties to cause no (or modest) additional loss in social welfare beyond the loss already incurred due to computational constraints. In this talk we review two recent results showing black-box reductions from welfare approximation algorithms to mechanisms that preserve desired economic properties. In particular: (1) we give a poly-time dominant strategy incentive compatible mechanism for Bayesian submodular (and more generally, fractionally subadditive) combinatorial auctions that approximates the social welfare within a constant factor. (2) we give a poly-time mechanism for arbitrary (known) valuation functions that, given a black-box access to a social welfare algorithm, provides a conflict free outcome that preserves at least half of its welfare. Both mechanisms are based on posted prices.
Based on joint work with Nick Gravin and Brendan Lucier.
Short Bio: Michal Feldman is an Associate Professor at the Blavatnik School of Computer Science at Tel Aviv University and a visiting researcher at Microsoft research Herzliya. She received her Ph.D. from the University of California at Berkeley in 2005, and in 2007 she completed a postdoctoral term at the Hebrew University as a Lady Davis fellow. During 2007-2013 she was a faculty member in the School of Business Administration and the Center for the study of rationality at the Hebrew University. Prof. Feldman’s research focuses on the intersection of computer science, game theory and microeconomics. She serves on the editorial board of JCSS, ACM TEAC and Networks, and recently served as the PC chair of the ACM Conference on Economics and Computation (EC). She is the recipient of the Alon Fellowship for outstanding young researchers, and various grants, including ERC (European Research Council), Marie Curie International Outgoing Fellowship, ISF, and Google. During 2011-2013, she was a visiting scholar at Harvard University and Microsoft Research New England. She is a member of the Global Young Academy and the Israeli Young Academy, and the vice chair of ACM Special Interest Group on Electronic Commerce (SIGEcom).
Invited talk by Paul Goldberg
Speaker: Paul Goldberg, University of Oxford, UK
Abstract: Nash equilibrium computation is complete for the complexity class PPAD, even for two-player normal-form games. Should we understand this to mean that the computational challenge is genuinely hard? In this talk, I explain PPAD, what PPAD-completeness means for equilibrium computation, and possible ways to escape the worst-case hardness. Following the PPAD-completeness results, attention turned to the complexity of computing approximate Nash equilibria. In an approximate equilibrium, the usual "no incentive to deviate" requirement is replaced with "bounded incentive to deviate", where a parameter epsilon denotes a limit on any player's incentive to deviate. I review some of the progress that was made, and reasons to hope for a polynomial-time approximation scheme. I also discuss recent work suggesting that a quasi-polynomial time algorithm is the best thing we can hope to achieve.
Short Bio: Prof. Paul Goldberg obtained his PhD at the University of Edinburgh in 1993 (supervised by Mark Jerrum) in the general area of algorithmic learning theory. He spent three years at Sandia National Labs (USA) working mainly on algorithmic problems arising from biology, and before coming to Oxford, held permanent academic positions at the universities of Warwick and Liverpool. At Liverpool, he was founding head of the Economics and Computation (EcCo) Research Group.
The general theme of Prof. Goldberg's research is the analysis of algorithms, and mathematically proven performance guarantees. Since 2002, he has worked mainly in algorithmic game theory, which addresses algorithmic challenges arising in economic theory, and for example, the design of auctions having good welfare properties. His paper "The complexity of computing a Nash equilibrium" (co-authored with Papadimitriou and Daskalakis) received the 2008 Game Theory and Computer Science Prize. More recently he is exploring the connections with machine learning (for example, revealed preferences theory). He is a member of the Oxford Man Institute for Quantitative Finance, with an interest in their work on data analytics.
Invited talk by Ramesh Johari
Speaker: Ramesh Johari, Stanford University, USA
Abstract: Since the advent of the first online marketplaces nearly two decades ago, commerce in nearly every sector of the industry is being transformed: transportation (Lyft, Uber), lodging (Airbnb), delivery (Instacart, Postmates), labor markets (Amazon Mechanical Turk, LinkedIn, Taskrabbit, Upwork), etc. In this talk, we will survey challenges and opportunities that arise in the design of these markets, with an emphasis on how operational and algorithmic challenges interlace with incentives to dictate market outcomes.
Based on joint work with Nick Arnosti, Sid Banerjee, Yash Kanoria, and Carlos Riquelme.
Short Bio: Ramesh Johari is an Associate Professor at Stanford University, with a full-time appointment in the Department of Management Science and Engineering (MS&E), and courtesy appointments in the Departments of Computer Science (CS) and Electrical Engineering (EE). He co-directs the Social Algorithms Lab (SOAL). He is a member of the Operations Research group in MS&E, the Information Systems Laboratory in EE, the Institute for Computational and Mathematical Engineering, the steering committee of the Stanford Cyber Initiative, and the Stanford Smart Grid Group. He received an A.B. in Mathematics from Harvard (1998), a Certificate of Advanced Study in Mathematics from Cambridge (1999), and a Ph.D. in Electrical Engineering and Computer Science from MIT (2004). He is an associate editor in Management Science (in the Stochastic Models and Simulation area) and in Operations Research (in the Information, Games and Networks area). In 2012-2013, Ramesh was on leave at oDesk (now Upwork), first as a Consulting Scientist, then as Director of Data Products and Research; he continues to serve as a technical advisor to Upwork.
Invited talk by Paul Milgrom
Speaker: Paul Milgrom, Stanford University, USA
Abstract: We model an online display advertising environment in which "performance" advertisers can measure the value of individual impressions, whereas "brand" advertisers cannot. If advertiser values for ad opportunities are positively correlated, second-price auctions for impressions can be very inefficient. Bayesian-optimal auctions are complex, introduce incentives for false-name bidding, and disproportionately allocate low-quality impressions to brand advertisers. We introduce "modified second bid" auctions as the unique auctions that overcome these disadvantages. When advertiser match values are drawn independently from heavy tailed distributions, a modified second bid auction captures at least 94.8% of the first-best expected value. In that setting and similar ones, the benefits of switching from an ordinary second-price auction to the modified second bid auction may be large, and the cost of defending against shill bidding and adverse selection may be low.
Short Bio: Paul Milgrom is the Shirley R. and Leonard W. Ely Professor in the School of Humanities and Sciences and professor of economics at Stanford University. He is a member of the US National Academy of Sciences, a Fellow of the American Academy of Arts and Sciences, and winner of the 2008 Nemmers Prize and the 2013 BBVA Foundation Frontiers of Knowledge prize. According to Google Scholar, Paul’s research works have more than 68,000 citations covering multiple of fields in economics. A leader in radio spectrum policy and auction theory and applications, Milgrom is currently advising the FCC on the design and implementation of its 2016 "incentive auction," which will buy TV broadcast licenses and sell wireless broadband licenses.