Please visit http://www.bklaus.net/ for an up to date version of this webpage.

     VIDI Project "How to Design Allocation and Matching Mechanisms?"

Main Investigator: Bettina Klaus (Associate Professor, Maastricht University, Department of Economics)

Project Summary:  

The allocation of scarce resources (e.g., goods, funding, votes) is a widely observed problem in many economic, political, and social conflict situations. Whenever jobs or positions have to be allocated, for instance places at a university or school, we refer to the allocation problem at hand as a matching problem. Important examples of matching problems are student placements for over-demanded studies as medicine and law.

We will study allocation problems as the ones mentioned above with the goal to design and recommend mechanisms that satisfy important properties, e.g., efficiency, fairness, non-manipulability, and stability. Given any specific allocation problem, the first step is to determine which properties are desirable (e.g., by social norms or because of legal constraints or economic interests). Second, after modeling these relevant properties accordingly, we will explore compatibilities and trade-offs between them in order to find appropriate solution mechanisms. Thirdly, for specific centralized economic markets policy advice will be issued to the respective central authority.

In three broadly defined projects we will model and analyze markets (many of which have not been studied before) in the domain of

1. division and trade economies,

2. two-sided matching economies, and

3. generalized matching economies.

Our main objective is to lay a solid theoretical foundation for the analysis and design of resource allocation and matching mechanisms. Therefore, apart from studying specific economies, we will study the connections between different models of allocation and matching. The innovation of this approach lies in the use of insights from one model in the analysis of the other models and in the development of new tools for the design of resource allocation and matching markets. This new approach will not only enhance our understanding of these (interconnected) allocation problems, but it will also help to develop new solutions and important applications.  

Keywords: economic design, normative approach, resource allocation, matching

The Research Team as of September 1st 2007 (with a short summary of ongoing research):

Rahmi Ilkilic            homepage    (postdoctoral researcher)

My area of research is network economics. My initial works were on game theoretical analysis of strategic network formation. Currently I am working on networks of flow. The most typical examples are power lines for electricity distribution, international natural gas pipelines and water resources distribution. I study the international natural gas market using a Cournot model. But different from a classical market, buyers and sellers can trade only if they are connected by a pipeline. This leads to different prices at different nodes in the network and the market outcome is determined by the network structure. The study of power line network centers on determining the value of additional lines for consumers and suppliers. This is a first step in the analysis of dynamic efficiency in energy markets. Such markets should not only be competitive, but also evolve to provide for the changing and increasing energy demand. The study of water resources aims to analyze the commons problem, where multiple users and sources are embedded in a network. In such an environment the classical one source many users model fails to provide a solution. The research incorporates graph theory to find efficient allocations of water among users. 

Cagatay Kayi            homepage    (postdoctoral researcher)

I am interested in studying matching mechanisms where the agents could revise their preferences during the matching process. When agents preferences are incomplete and interdependent, agents learn about their own preferences from others in a dynamic mechanism. I consider the simplest extension of the Gale and Shapley's the deferred acceptance algorithm to a dynamic setting which is to run the algorithm once and give "some" information about the environment afterwards, and then run the algorithm again. An example is the college admissions problem where agents' preferences are formed by the colleges' last year base scores and agents have constrained choices. I look for situations where dynamic matching mechanisms may improve outcomes over the static mechanisms.

Bettina Klaus                homepage    (principal investigator)

I am currently working on various projects within the VIDI research project. As a first step towards generalized matching economies such as network formation and coalition formation models, I currently study roommate markets.

In a roommate market (see Gale and Shapley, 1962), a finite set of agents has to be partitioned into pairs (roommates) and singletons. We will refer to such a partition as a matching. Each agent has strict preferences over each of the other agents (i.e., sharing a room with him) and staying alone (or relying on an outside option). Hence, a roommate market is a simple example of hedonic coalition as well as network formation. In hedonic coalition formation (see Bogomolnaia and Jackson, 2002), a set of agents has to be partitioned and agents have preferences over coalitions (i.e., all subsets of agents). Thus, for roommate markets coalition formation is restricted to coalitions of at most two agents. In network formation (see Jackson and Watts, 2002), links between agents can be established and agents have preferences over their links (or even the entire network structure). Thus, for roommate markets network formation is restricted to at most one link per agent (and agents have preferences over this direct link only). Moreover, a roommate market can be interpreted as an extension of one of the most famous and simplest type of (two-sided) matching markets, a so-called marriage market. In a marriage market, agents are either male or female, and a man (woman) only wants to be matched to a woman (man) or to him(her)self. This setting is equivalent to a roommate market where the set of agents consists of two disjoint subsets and every agent in a certain subset prefers staying alone to being matched to another agent in the same subset. Hence, roommate markets are a particularly interesting class of matching markets because they lie in the "intersection" of network and coalition formation models.

In all the matching, coalition, and network models mentioned above, stability is a central property. For roommate markets, a matching is stable if all roommates are mutually acceptable and no pair of agents would prefer to be roommates instead of having their current matches. It is well-known that for marriage and roommate markets this (pairwise) stability notion is equivalent to core stability. However, when extending the class of marriage markets to the class of roommate markets a problem occurs: while the core for a marriage market is always non-empty, the core of a roommate market can well be empty
(see Gale and Shapley, 1962). As a consequence, roommate markets can be considered an important benchmark for the development of solution concepts for matching, network and coalition formation models that may exhibit an empty core or set of stable matchings, network or coalition structures (For more general models of matching as well as coalition or network formation, various stability notions exist and pairwise stability is no longer equivalent to core stability).

For more information and first results on roommate markets within the VIDI project see

B. Klaus and F. Klijn (2008): “Smith and Rawls Share a Room: Stable Generalized Medians in Matching Markets," working paper (will be send upon request).

B. Klaus, F. Klijn, and M. Walzl (2008): “Stochastic Stability for Roommate Markets,” working paper (will be send upon request).

B. Klaus (2007): “Competition and Resource Sensitivity in Marriage and Roommates Markets,” Meteor RM/07-046, Maastricht University: downloadable.

B. Klaus, F. Klijn, and M. Walzl (2007): “The Evolution of Roommate Networks: A Comment on Jackson and Watts JET (2002),” METEOR RM/07/012, Maastricht University: downloadable.

Alexandru Nichifor    homepage    (PhD student)

My main research interests are in matching markets, cooperative games with transferable utility and mechanism design. In a first project (joint with Bettina Klaus) I analyze consistency together with other normative properties for one-sided assignment games. Side projects include interest in industrial organization and finance.

Some literature on the topic can be found on Al Roth's Market Design page. This page will be updated in due course with more information on the research team members and the project.

For more information please contact Bettina Klaus:  b.klaus@algec.unimaas.nl.