Matching and Barter Exchange (1)

Itai Ashlagi
Massachusetts Institute of Technology

In the first part we will discuss matching or barter exchange in a dynamic environment.
In particular, we will consider the problem of efficient operation of a barter exchange platform for indivisible goods. We introduce a dynamic model of barter exchange where in each period one agent arrives with a single item she wants to exchange for a different item. We will explore different types of exchanges, such as bilateral, multi-way and chains and show that greedy policies, which attempt to match agents upon arrival, are close to optimal among a large class of matching mechanisms that seek to minimize the average waiting time of agents. We will discuss open questions and directions for future research.

In the second part we will discuss two-sided matching markets in which agents have random preferences, and develop properties that are likely to occur. We will study matching markets with an unequal number of agents in each side and show that two-sided matching markets are highly competitive and have almost a unique stable matching. Furthermore, the short side is much better off in all stable matchings.

Back to Graduate Summer School: Games and Contracts for Cyber-Physical Security