Online Stochastic Matching

Session

Afternoon Session

Sep 24, 2024, 2:00 PM

Amphithéâtre Schwartz (Institut de Mathématiques de Toulouse (IMT))

Conveners

Afternoon Session: The Top Trading Cycles (TTC) Rule: Theory and Applications

• Thomas Hira (IRIT)
• Bettina Klaus (University of Lausanne)

Afternoon Session: Dynamic Matching and Queueing I

• Olivier Tercieux (CNRS & Paris School of Economics)
• Felipe Garrido-Lucero

Afternoon Session: Matching in Dynamic Environments

• Nahuel Soprano-Loto (LAAS-CNRS)
• Amin Saberi (Stanford)
• Itai Gurvich (Northwestern University)

Afternoon Session: Dynamic Matching and Queueing II

• Kristy Gardner (Amherst College)
• Jean Mairesse (CNRS)

20. Happy 50th birthday TTC! & Characterizing the top trading cycles rule for housing markets with lexicographic preferences when externalities are limited (4)

Bettina Klaus (University of Lausanne)

9/24/24, 2:00 PM

In my talk, I would like to commemorate the 50th birthday of the famous top trading cycles algorithm/rule and will mix a survey with a recent paper. The abstract for the paper is as follows.
We consider a housing market model with limited externalities where agents care both about their own consumption via demand preferences and about the agent who receives their endowment via supply...

10. Characterizing the Typewise Top-Trading-Cycles Mechanism for Multiple-Type Housing Markets (5)

Flip Klijn

9/24/24, 3:30 PM

We consider the generalization of the classical Shapley and Scarf housing market model (Shapley and Scarf, 1974) to so-called multiple-type housing markets (Moulin, 1995). Throughout the paper, we focus on strict preferences. When preferences are separable, the prominent solution for these markets is the typewise top-trading-cycles (tTTC) mechanism.

We first show that for lexicographic...

11. Stable Solutions for Kidney Exchanges (6)

Peter Biro (HUN-REN KRTK)

9/24/24, 4:15 PM

In this talk we will survey the main results of three recent papers on stable solutions for kidney exchange programmes (KEPs). These programmes have been established in most of the developed countries in the world during the last two decades to facilitate the exchange of living kidney donors for those recipients who have willing but immunologically incompatible donors. The UK has the largest...

27. Optimal Queue Design (10)

Olivier Tercieux (CNRS & Paris School of Economics)

9/25/24, 2:00 PM

We study the optimal method for rationing scarce resources through a queue system. The designer controls agents’ entry into a queue and their exit, their service priority—or queueing discipline—as well as their information about queue priorities, while providing them with the incentive to join the queue and, importantly, to stay in the queue, when recommended by the designer. Under a mild...

13. Optimal Queueing Auctions (11)

Andy Choi (Bocconi University)

9/25/24, 3:30 PM

This paper studies theoretically the optimal design of a queue system for providing goods or services to buyers that arrive stochastically over time. In a standard auction problem, a fixed number of goods are allocated to a fixed number of potential buyers. However, many services, such as online or phone customer service, repair, food delivery, and restaurant service, take a stochastic amount...

28. Optimal Stopping with Interdependent Values (12)

Simon Mauras (Inria Saclay)

9/25/24, 4:15 PM

Consider a single-item auction, say for a piece of art, where buyers arrive online. The goal is to sell the item to the agent with the highest value, while making the decisions about whether to select each buyer immediately on their arrival. Additionally, buyers’ values can depend on one another: a buyer interested in decorating their living room might be influenced by the impression of those...

29. Match Now or Later? (16)

Itai Gurvich (Northwestern University)

9/26/24, 2:00 PM

The talk will have two parts, both focusing on centralized markets, the tension between short-term and longer-term objectives, and the value of waiting to thicken the market and increase match opportunities.

In the first part I’ll talk about hindsight optimality in networks without departures. A matching policy is hindsight optimal if the policy can (nearly) maximize the total collected...

31. Batching and Optimal Multi-stage Bipartite Allocations (17)

Rad Niazadeh (University of Chicago)

9/26/24, 3:30 PM

In several applications of real-time matching of demand to supply in online marketplaces --- for example, matching delivery requests to dispatching centers in Amazon or allocating video ads to users on YouTube --- the platform allows for some latency (or there is an inherent allowance for latency) in order to batch the demand and improve the efficiency of the resulting matching in such...

30. Approximating Optimum Online for Online Capacitated Allocation (18)

Tristan Pollner (Stanford)

9/26/24, 4:15 PM

We study online capacitated resource allocation, a natural generalization of online stochastic max-weight bipartite matching. This problem is motivated by ride-sharing and Internet advertising applications, where online arrivals may have the capacity to serve multiple offline users. Our main result is a polynomial-time online algorithm which is (0.5+c)-approximate to the optimal online...

34. Stochastic Matching Models (22)

Jean Mairesse (CNRS)

9/27/24, 2:00 PM

35. Online Stochastic Matching Under the First-Come-First-Matched Policy (23)

Céline Comte (CNRS and LAAS)

9/27/24, 3:30 PM

We consider the following online stochastic matching problem: items from different classes arrive according to independent Poisson processes; matching compatibilities between items are described by a simple graph over the classes, so that two items can be matched if and only if their classes are neighbors in the graph; this graph is assumed to be connected and non-bipartite; lastly, each...

12. Greedy Algorithm for Multiway Matching with Bounded Regret (24)

Varun Gupta (Northwestern University)

9/27/24, 4:15 PM

We consider a finite horizon online resource allocation/matching problem where the goal of the decision maker is to combine resources (from a finite set of resource types) into feasible configurations. Each configuration is specified by the number of resources consumed of each type and a reward. The resources are further subdivided into three types - offline, online-queueable (which arrive...