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