Workshop on the Intersection of Machine Learning and Mechanism Design (MDML'2019)

Monday May 13, 2019 14:00-17:30 at TheWebConference, San Francisco, CA.

The workshop aims to bring together researchers and practitioners from two research domains - mechanism design and machine learning - whose fields interact billions of times per day in practice but that are still, for the most part, keeping separate in the academic arena. The workshop will focus on motivating, promoting and disseminating interdisciplinary research combining these fields.


The workshop will tackle topics at the intersection between the two fields, including the increasing use of data and ML in designing mechanisms in broad contexts (e.g., mechanisms based on sampled data or the use of ML techniques in designing new mechanisms) as well as the potential use of mechanism design techniques in ML (e.g., learning in a strategic setting).

One area of focus will be repeated online auctions, where machine learning is an essential component of mechanism design from both the buyers’ and sellers’ points of view.

Program:


    • 2:00pm Chairs – welcome remarks


    • 2:05pm Invited talk: Prof. Tim Roughgarden, Columbia University
              • "The Surprising Power of Reserve Prices"
              • Reserve prices play an important role in the theory and practice of revenue-maximizing auctions. We discuss their use in deployed systems, the mathematical justifications provided by classical optimal auction theory, and recent developments in algorithmic game theory and machine learning that bring this theory closer to practice.


    • 2:35pm Contributed talk: Yash Kanoria, Columbia University and Hamid Nazerzadeh, University of Southern California
              • "Dynamic Reserve Price Repeated Auctions: Learning from Bids"
              • A large fraction of online advertisements are sold via repeated second-price auctions. In these auctions, the reserve price is the main tool for the auctioneer to boost revenues. In this work, we investigate the following question: how can the auctioneer optimize the reserve prices by learning from the previous bids, while accounting for the long-term incentives and strategic behavior of the bidders? To this end, we consider a seller who repeatedly sells ex ante identical items via a second-price auction. Buyers’ valuations for each item are drawn i.i.d. from a distribution F that is unknown to the seller. We find that if the seller attempts to dynamically update a common reserve price based on the bidding history, this creates an incentive for buyers to shade their bids, which can hurt revenue. When there is more than one buyer, incentive compatibility can be restored by using personalized reserve prices, where the personal reserve price for each buyer is set using the historical bids of other buyers. Such a mechanism asymptotically achieves the expected revenue obtained under the static Myerson optimal auction for F . Further, if valuation distributions differ across bidders, the loss relative to the Myerson benchmark is only quadratic in the size of such differences. We also extend our results to a contextual setting where the valuations of the buyers changes depending on the observed features of the items. When up-front fees are permitted, we show how the seller can determine such payments based on the bids of others to obtain an approximately incentive compatible-mechanism that extracts nearly all the surplus.


    • 3:00pm Invited talk: David Pennock, Microsoft Research
              • Smarter Markets: Bringing Intelligence into the Exchange"
              • Billions of dollars in financial securities exchange hands every day in independent continuous double auctions. Although the auctions are automated, fast, open 24-7, and have worldwide scope and massive scale, the underlying auction rules have not changed much for over 100 years. Advertisement auctions, on the other hand, have rapidly evolved, incorporating optimization and machine learning directly into their allocation rules. The downside is a less-transparent auction, but the upsides for efficiency and expressiveness are tremendous. The trend toward smarter markets will expand into finance and well beyond, pervading how markets are designed. I will discuss markets that optimize and learn, using prediction markets and advertising markets as key examples.


    • 3:30pm --Coffee Break--


    • 4:00pm Invited talk: Suju Rajan and Noureddine El Karoui, Criteo
              • "Auction theory from the bidder standpoint"
              • Much of classical auction theory has been developed from the standpoint of the seller, trying to understand how to optimize auctions to maximize seller revenue for instance. This is still a source of very active current research. Billions of auctions are now run on the Internet everyday between the same sellers and bidders and this creates a need to better understand auctions from the bidders' perspective. In this talk we will present some recent results on this question, showing for instance that auctions that are reputed to be truthful are not truthful anymore when the seller optimizes the auction format based on bidders' past bids, provide explicit and simple to implement shading strategies that improve bidders' utility (on and off equilibrium) and are robust to various forms of estimation error and mechanism changes. We will also discuss various equilibrium questions. We take a mostly functional analytic point of view on these problems. If time permits, we will discuss ongoing work on a machine-learning-based perspective. Joint work with Thomas Nedelec, Marc Abeille, Clément Calauzènes, Benjamin Heymann and Vianney Perchet while doing research at Criteo.


    • 4:30pm Contributed talk: Thomas Nedelec, Noureddine El Karoui and Vianney Perchet, Criteo
              • "Learning to bid in revenue maximizing auctions"
              • We consider the problem of the optimization of bidding strategies in prior-dependent revenue-maximizing auctions, when the seller fixes the reserve prices based on the bid distributions. Our study is done in the setting where one bidder is strategic. Using a variational approach, we study the complexity of the original objective and we introduce a relaxation of the objective functional in order to use gradient descent methods. Our approach is simple, general and can be applied to various value distributions and revenue-maximizing mechanisms. The new strategies we derive yield massive uplifts compared to the traditional truthfully bidding strategy.


    • 4:55pm Invited talk: Prof. David Parkes, Harvard University
              • "Optimal Economic Design through Deep Learning"
              • 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 also overview applications to other problems of optimal economic design, and discuss the broader implications of this work. Joint work with Paul Duetting (London School of Economics), Zhe Feng (Harvard University), Noah Golowich (Harvard University), Harikrishna Narasimhan (Harvard -> Google), and Sai Srivatsa (Harvard University).


    • 5:25pm Chairs – closing remarks

Call for Papers


We invite submissions in the broad areas of intersection, both in auctions and online advertising; and in mechanism design in general. Work can be theoretical or empirical. Case studies from the industry are welcomed. As typical for a workshop, submissions can include original work, work submitted to or published elsewhere, and early work with promising results. Feel free to contact the organizers (see email below) to discuss whether a submission is in scope.

Important Dates:

  • Submission deadline: January 25, 2019
  • Acceptance notification: February 22nd, 2019
  • Camera-ready version due: March 6rd, 2019

Submissions of either short or long papers to be made via EasyChair. Please follow the formatting guidelines of the main CFP. The camera-ready copy for the proceedings will be in a two-page, extended abstract format.


Organization

Organizers:

  • Ronny Lempel (Outbrain)
  • Aranyak Mehta (Google Research)

Please reach us at mdml2019@easychair.org.


Program Committee:

  • Michal Aharon, Oath
  • Omer Ben Porat, Technion
  • Ruggiero Cavallo, Oath
  • Olivier Chapelle, Google
  • Iftah Gamzu, Amazon
  • Yishay Mansour, Tel-Aviv University
  • Muthu Muthukrishnan, Amazon
  • Hamid Nazerzadeh, USC and Uber
  • Amir Ronen, SparkBeyond
  • Danny Rosenstein, Outbrain
  • Erik Sodomka, Facebook
  • Sergei Vassilvitskii, Google