The Nobel Prize in Economics 2020 and the Connections with Computer Science




The latest edition of the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel has been awarded jointly to Paul Milgrom and Robert Wilson for “improvements to auction theory and inventions of new auction formats.” Eight years ago, Alvin Roth and Lloyd Shapley were awarded the same prize for their seminal work on the theory and application of matching markets. The 2012 and 2020 awards are an acknowledgement of the impact of the field of market design — -the science of designing rules for markets.

Whereas the 2012 award focussed on markets that explicitly prohibit money (such as in matching doctors to hospitals and kidney donors to patients), the 2020 award concerns important large-scale markets in which money matters (such as allocating radio-spectrum frequencies). At their heart, both types of markets are concerned with facilitating better and more efficient outcomes.

Market design has now become recognized as a prominent field in economics. But as is true for many thriving fields, their growth and impact are intertwined with their interdisciplinary nature. In this article, I point out some intrinsic connections of market design with computer science. The connections are the driving force of various research communities, including those in EconCS and algorithmic game theory.

Mechanisms as algorithms

An auction or a market-clearing mechanism is essentially a set of rules and steps that are followed by the participating agents to arrive at an outcome which specifies who gets what items and who pays what. In view of this, an auction can invariably be viewed as an algorithm that takes into account the bids and preferences of the participants to compute an outcome. An algorithmic approach is useful to design mechanisms irrespective of whether the auctioneer is a human or not. Tools from algorithm design are suitable when trading off several features of the auction such time complexity versus allocative efficiency.

Allocative efficiency via optimisation

A major goal of market design is facilitating participants towards a mutually beneficial and efficient outcome. However, computing such outcomes is computationally intractable. Prominent examples include computing allocations that maximize social welfare in radio-spectrum auctions or match the highest number of kidney patients in various kidney exchange problems. This immediately leads to the need to leverage the state-of-the-art techniques in optimisation to solve such problems. The computational challenges have led to exemplary collaborations between researchers in economics, operations research, and computer science. For example, one of the most prominent applications cited in the 2020 prize is that of spectrum auctions. The latest interventions on the US spectrum auctions are based on developments in optimisation including fast algorithms for solving the Boolean satisfiability problem.

Information and communication

An essential ingredient of market design is to coordinate the agents by eliciting sufficient information about their preferences. It is impossible or at least costly to elicit complete information from the participants. From this perspective, a computer science took-kit is useful especially useful we want to represent preferences in a compact way and to design protocols that do not have heavy communication complexity. Learning-based approaches are also relevant in making suggestions to the end-user.

Computer as the auctioneer

Typically, an auction conjures an image of an auctioneer in an art gallery overseeing the bidding of items. However, some of the most commonly and widely used auctions are on electronic marketplaces such as eBay are ones where the computer replaces the human auctioneer. If the computer is the auctioneer, there is no option but to frame the auction in the form of computer code.

Electronic Market Places

The ubiquity of mobile devices makes electronic marketplaces efficient and convenient. Some of the biggest innovations in the tech sector concerns setting up electronic marketplaces for books (Amazon), car-rides (Uber), and housing (Airbnb). Similarly, the business model of some of the biggest tech companies, such as Google, is based on revenue from online advertisements. Electronic marketplaces bring a whole host of challenges including privacy and security that the computer sciences communities are working on.

Bidding Agents

It is not just the auctioneer that can be replaced by an algorithm. In various situations, the auction participants can give their preferences to an electronic bot who can bid on their behalf. The approach of designing agents that coordinate with each other is one of the characteristics of the field of multi-agent systems.

Conclusions

In this article, I have highlighted how computer science provides conceptual and technical tools that are beneficial in market design. Preston McAfee, Chief Economist Microsoft states that ‘‘Over the next 10 years, the major breakthrough of economics will be in applications of market design, which improves the efficiency of markets using a combination of game theory, economics and algorithm design.” The past decades have seen a developing collaboration between the economics and computer science communities. One foresees these collaborations to grow further.

Comments

Popular posts from this blog

Smart Lotteries in School Choice Ex-ante Pareto-Improvement with Ex-post Stability

Fair budgets from ranked ballots: PB-EAR

Proportionally Representative Clustering