Online Stochastic Matching

Session

Morning Session

Sep 24, 2024, 9:00 AM

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

Conveners

Morning Session: Challenges in Dynamic Matching

• Itai Gurvich (Northwestern University)
• Itai Ashlagi (Stanford)

Morning Session: Practically Motivated Matching Problems

• Vahideh Manshadi (Yale School of Management)
• Sushil Varma (Georgia Tech)

Morning Session: Online Matching on Random Graphs

• Matthieu Jonckheere (CNRS & LAAS)
• Alejandro Hernandez Wences (LAAS - CNRS)

Morning Session: Online Matching: from Theory to Practice

• Aranyak Mehta (Google Research)
• Ernesto Garcia (LAAS-CNRS)

22. Challenges in Dynamic Matching (1)

Itai Ashlagi (Stanford)

9/24/24, 9:00 AM

14. Simulation is All You Need (2)

Yash Kanoria (Columbia Business School)

9/24/24, 10:30 AM

Motivated by online matching markets and network revenue management (NRM) problems with many types (e.g., fulfillment optimization), we study dynamic spatial matching (DSM) in which supply and demand live in d dimensional space and need to be matched with each other dynamically. If demand and supply have the same spatial distribution, greedy matching suffices, and achieves average match...

23. Designing Efficient Interview Graphs for Interim Stable Matchings: A Signaling Approach (3)

Sophie Yu (University of Pennsylvania)

9/24/24, 11:15 AM

In many two-sided matching markets agents initially engage in costly interviews in order to refine their interim preferences. We study how signaling mechanisms can reduce the number of interviews in random markets. We are interested in interim stability, which expands the notion of stability to ensure that no two agents regret not interviewing with each other. The final match is almost interim...

24. Dynamic Matching with Post-Allocation Service and its Application to Refugee Resettlement (7)

Vahideh Manshadi (Yale School of Management)

9/25/24, 9:00 AM

Motivated by our collaboration with a major refugee resettlement agency in the U.S., we study a dynamic matching problem where each new arrival (a refugee case) must be matched immediately and irrevocably to one of the static resources (a location with a fixed annual quota). In addition to consuming the static resource, each case requires post-allocation services from a server, such as...

25. Adaptive Policies and Approximation Schemes for Dynamic Matching (8)

Ali Aouad (London Business School)

9/25/24, 10:30 AM

In the dynamic matching problem, customers arrive according to a Poisson process and must be matched to available servers within a network of queues. These servers independently replenish and renege from the market. Previous literature on the dynamic matching problem often concentrates on static policies—where the matching decisions are not adapted to dynamic information on queue lengths. In...

26. Teacher Redistribution in a Public School System (9)

Jay Sethuraman (Columbia University)

9/25/24, 11:15 AM

The Right to Free and Compulsory Education Act (2009) (RTE) of the Government of India prescribes teacher-student ratios for state-run schools. One method advocated by the Act to achieve its goals is the redeployment of teachers from surplus to deficit schools. I'll discuss a model in which teachers can either remain in their initially assigned schools or be transferred to a deficit school in...

33. Online Matching on Large Graphs: Theoretical and Practical Challenges (13)

Matthieu Jonckheere (CNRS & LAAS)

9/26/24, 9:00 AM

We discuss both some theoretical advances for online matching on random graphs and how to reach practical efficient schemes for critical applications like organ donations based on reinforcement learning and orchestration of expert policies.

21. Online Matching in Geometric Random Graphs (14)

Flore Sentenac (HEC Paris)

9/26/24, 10:30 AM

We investigate online maximum cardinality matching, a central problem in ad allocation. In this problem, users are revealed sequentially, and each new user can be paired with any previously unmatched campaign that it is compatible with. Despite the limited theoretical guarantees, the greedy algorithm, which matches incoming users with any available campaign, exhibits outstanding performance in...

32. A Framework for Weighted Matchings In Dynamic Graphs (15)

Aditi Dudeja (University of Salzburg)

9/26/24, 11:15 AM

In dynamic graph algorithms, the goal is to maintain a key property of the graph while an adversary makes changes to the graph in the form of edge deletions or insertions. The goal is to minimize the update time of the algorithm, which is the time taken by the algorithm to adapt to a single adversarial edge insertion or deletion and output accordingly. I will briefly talk about some algorithms...

18. Online Allocation in Online Advertising: Matching, Auctions, and Autobidding (19)

Aranyak Mehta (Google Research)

9/27/24, 9:00 AM

Internet ad auctions are a fascinating innovation with a huge impact. Advertising auctions match buyers and sellers under various constraints, at scale, enabling highly valuable services for their users. The talk will give an overview of this area, from online budgeted matching to the interplay between matching, autobidding, and auctions. We will present the theory and practical aspects of...

17. Algorithms for Autobidding in Online Advertising (20)

Di Wang (Google Research)

9/27/24, 10:30 AM

Online advertising has recently grown into a highly competitive and complex multi-billion-dollar industry, with advertisers bidding for ad slots at large scales and high frequencies. This has resulted in a growing need for efficient "auto-bidding" algorithms that determine the bids on behalf of advertisers for incoming queries to maximize advertisers' objectives subject to their specified...

19. Stochastic Matching: A Polytope Perspective (21)

Fabien Mathieu (Swapcard)

9/27/24, 11:15 AM

Stochastic dynamic matching has numerous applications, ranging from supply-chain management to kidney exchange programs. We consider a generic model where items of different classes arrive randomly. Two items can be matched if their classes are compatible. Unmatched items are queued.

We study the stability of such systems and the matching rates between classes. Our main results, which rely...