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)
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...
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...
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...
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...
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...
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...
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...
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...
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...
