Microsoft Research Blog

Microsoft Research Blog

The Microsoft Research blog provides in-depth views and perspectives from our researchers, scientists and engineers, plus information about noteworthy events and conferences, scholarships, and fellowships designed for academic and scientific communities.

Microsoft and intelligent markets at ACM EC’17

June 26, 2017 | By Microsoft blog editor

By David Pennock, Principal Researcher and Assistant Managing Director 

The 18th ACM Conference on Economics and Computation (EC’17) starts today at MIT in Cambridge, MA, featuring some of the latest research findings at the interdisciplinary boundary between economics and computer science. Microsoft researchers will have a significant presence at the conference, co-authoring many papers, serving in leadership roles, giving an invited talk, and receiving an award.

One theme at the conference is the design and analysis of new marketplaces. Online platforms and artificial intelligence technology are enabling better ways to match people with resources—buyers with sellers, students with schools, residents with housing, patients with organs, and more—making existing markets both economically and computationally efficient and vastly improving consumer welfare. Insights from the economics and computation (EC) community are impacting how the government raises money for wireless spectrum, how publishers monetize their sites through advertising, how rural farmers in Uganda sell produce, how life-saving kidney transplants are maximized, and how business school students choose courses, to name just some examples.

Few markets have grown as fast as the ride-hailing services Uber and Lyft. Now billion-dollar businesses, they epitomize how technology can improve transportation markets, making riders and drivers happier and streamlining the use of cars, roads, and carbon. Glen Weyl and his co-authors, including Microsoft intern Juan Camilo Castillo, show that surge pricing—charging more during peak times—does more than balance supply and demand; it can forestall a type of market collapse unique to ride-hailing markets. During rush hour, drivers will scatter to meet their riders. When that happens, a new rider requesting a trip will often find that the closest driver is far away; the rider has to wait and the driver has to waste time and fuel just making the pickup. As pickup times increase, the number of unserved customers and cancellation rates spike, both signs of a market collapse. The paper explains how surge pricing keeps the market healthy during high-demand peaks, allowing the platform to charge less during most of the day.

Like transportation, affordable housing plays an outsized role in the pursuit of happiness. Many large cities around the world grapple with how to allocate low-cost housing to residents in need. Peng Shi, the ACM SIGecom Doctoral Dissertation Award winner, and his co-authors wrote “How (Not) to Allocate Affordable Housing,” describing a theoretical model of how to assign subsidized housing to city residents with limited means. There is little previous theoretical guidance on how to design the allocation rules: by lottery or waiting list? If by lottery, should each building run an independent lottery, or should there be a centralized lottery? If by waiting list, should those at the top of the list be allowed to turn down offers? Peng and his co-authors find that allocation mechanisms that seem very different may actually be, to a first-order approximation, equivalent in equilibrium, and they compare the social welfare under various mechanisms. They show that per-building lotteries, currently used in New York City, are less effective than waiting lists.

In a cloud-computing environment, classical scheduling becomes a market-design challenge. When users compete for resources, they will not always truthfully report their arrival times, deadlines, and priorities. Nikhil Devanur and his co-authors address the challenge in their paper, “Truth and Regret in Online Scheduling”. Instead of designing a scheduling algorithm that discourages all forms of misreporting, a nearly impossible task, the authors focus on designing an algorithm that performs close to the best among a family of algorithms, preserving truthfulness even while switching algorithms mid-stream. Check the paper for the devilish(ly clever) details. Nikhil had a hand in five papers published at the conference—a remarkable feat!

My own paper, co-written with Jenn Wortman Vaughan and Microsoft intern Rupert Freeman, covers wagering mechanisms, where people put money behind their predictions about future events like elections. Though widespread, none of the popular wagering mechanisms are truthful, raising questions about their use for crowdsourcing predictions. We present the Double Clinching Auction, the only known wagering mechanism that is both truthful and close to Pareto efficient: in my mind the first truly practical wagering mechanism that is truthful.

Market design requires good models of how people react to incentives. Microsoft postdoc Annie Liang co-wrote a paper about validating models of human behavior. When modelers test their theories, they commonly focus on predictiveness: do the predictions of the theory match the data? But whether a given level of predictive accuracy is good enough depends on whether more predictive theories exist, and how much more predictive they might be. The authors call this second issue completeness. The authors show that machine learning approaches can be used to construct practical benchmarks, illustrating their approach with a fascinating example.

Here’s the full list of 16 papers co-authored by Microsoft scientists, covering other aspects of market design and many other topics. Please browse, download, and read those that strike your interest. I hope to see some of you at the conference for what looks like a fantastic week!

Related links: