The study of markets has long been a central focus of economics, management sciences, and more recently, computer science. Matching without money led to substantial research at the intersection of these fields, and there is also a long history of thought on price-based markets. For example, general equilibrium theory attempts to explain supply, demand, and prices in an economy with several interacting markets for objects. The celebrated Arrow–Debreu model suggests that, under certain assumptions such as divisible objects, convex preferences, and demand independence, there must be a set of anonymous and linear (Walrasian) prices such that aggregate supplies will equal aggregate demands for every commodity in the economy in a competitive equilibrium. Stable matchings in the classical Gale-Shapley college admission model and its generalizations are based on similar equilibrium concepts, where cutoff scores are playing a role similar to prices to induce fair allocations.

Goods are typically not divisible in most markets, and they need to consider complex allocation constraints and preferences. Spectrum auctions where telecoms have preferences for packages of licenses or day-ahead electricity markets provide illustrative examples. Complexities arise from superadditive valuations for packages of items or allocation constraints. The resulting allocation problems are typically non-convex, which leads to computational as well as economic challenges. A competitive equilibrium does not generally exist in such markets, which has led to significant research on the stability of non-convex and price-based markets. Likewise, stable matchings may not exist in complex markets without payments, such as college admissions with lower and upper quotas, and the related problems can be NP-hard. The computational complexity barriers require sophisticated optimization techniques to resolve.

General equilibrium theory focuses on economies where participants are price-takers, which can be a reasonable assumption for large non-convex markets where bidders often do not have enough market power or information to manipulate strategically. For most markets, however, this is too strong an assumption. Ideally, market designs are incentive-compatible. However, designing markets that consider real-world constraints and that are robust against strategic manipulation has proven challenging. Practically feasible market designs might not be incentive-compatible, and one needs to understand equilibrium strategies in markets where the truthful revelation of preferences might not be an equilibrium strategy. This has led to a growing interest in equilibrium learning and the manipulability of non-truthful market designs. Engineering economics is a new interdisciplinary approach tackling all the above issues.

The same problems arise in matching markets without money. Further examples include course allocation, hospital-resident matching, kidney exchanges, refugee resettlement, or school choice. Complex constraints arise in many of these applications, e.g., hospital-resident matching where couples of doctors need to be considered, as well as distributional constraints on the assignment of minorities or quotas that need consideration in school choice. In applications such as course matching, students have preferences for bundles of courses. All these constraints make it hard or impossible to implement incentive-compatible and stable or efficient market mechanisms. Market designers explored approximation and randomization or the introduction of fake money in pseudo-markets to circumvent some impossibilities.

There are many connections between market design with and without money, and this Dagstuhl Seminar aims to provide a platform for scholars in auctions, matching, and learning in games to work together and develop new ideas on how to deal with the complexities in designing and analyzing real-world markets.

Creative Commons BY 4.0

Martin Bichler, Péter Biró, and Bettina Klaus