Conveners
Morning Session: Challenges in Dynamic Matching
- Itai Ashlagi (Stanford)
Morning Session: Online Matching and Its Practically Motivated Generalizations
- Vahideh Manshadi (Yale School of Management)
Morning Session: Online Matching on Random Graphs
- Matthieu Jonckheere (CNRS & LAAS)
Morning Session: Online Matching: from Theory to Practice
- Aranyak Mehta (Google Research)
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...
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...
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...
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...
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.
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...
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...
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...
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...
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...
