Online Stochastic Matching

Europe/Paris
ENSEEIHT

ENSEEIHT

2 Rue Charles Camichel 31000 Toulouse
Céline Comte (CNRS and LAAS), Itai Gurvich (Northwestern University), Pascal Moyal (Institut Élie Cartan de Lorraine)
Description

In online matching, a sequence of (random) items arrives over time and groups of items are formed to maximize some performance goal. This problem exists in many forms and covers a wide range of applications, from ad placement on the web to question-and-answer pairing in forums to organ donation programs. Although online matching has first been considered mainly in an adversarial framework, with the goal of proving worst-case performance bounds, stochastic modeling and machine learning have recently approached this problem from a stochastic perspective, allowing them to obtain statistical bounds on performance and to translate existing methods from other application areas. However, despite the close links between their approaches, these two communities are still largely disjoint and have little interaction. The goal of this workshop is to bring together researchers from academia and industry who approach online matching from different perspectives and to foster interdisciplinary interaction.

This workshop is part of a thematic semester called Stochastic control and learning for complex networks (SOLACE).

CIMI          

Registration
Registration form
    • Morning Session: [TBA] C002 (Salle des Thèses)

      C002 (Salle des Thèses)

      ENSEEIHT

      2 Rue Charles Camichel 31000 Toulouse
      Convener: Itai Ashlagi (Stanford)
      • 1
        [TBA] C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
        Speaker: Itai Ashlagi (Stanford)
      • 10:00 AM
        Coffee break C101–C102–C103 (ENSEEIHT)

        C101–C102–C103

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
      • 2
        Simulation is All You Need C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse

        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 distance of the same order as the distance to the nearest neighbor, except for the case of d=1 and both supply and demand arriving dynamically over time. If demand and supply have different spatial distributions, the matching constraint has bite and greedy matching fails. We introduce a unifying and practical algorithmic principle for NRM and DSM dubbed SOAR: Simulate, Optimize, Assign, Repeat, which repeatedly simulates the future to enable good matching decisions. Simulating one sample path at each stage already enables SOAR to produce near optimal regret for the majority of NRM models in the literature, and for DSM with non-atomic demand and supply distributions. For more challenging NRM and DSM models, SOAR with multiple simulated sample paths at each stage achieves near optimal regret.

        Speaker: Yash Kanoria (Columbia Business School)
      • 3
        [TBA] C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
        Speaker: Sophie Yu (Duke University)
    • 12:00 PM
      Lunch C101–C102–C103

      C101–C102–C103

      ENSEEIHT

      2 Rue Charles Camichel 31000 Toulouse
    • Afternoon Session: Happy Birthday TTC: A Brief Review and Some Current Results C002 (Salle des Thèses)

      C002 (Salle des Thèses)

      ENSEEIHT

      2 Rue Charles Camichel 31000 Toulouse
      Convener: Bettina Klaus (University of Lausanne)
      • 4
        Happy Birthday TTC: A Brief Review and Some Current Results C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
        Speaker: Bettina Klaus (University of Lausanne)
      • 3:00 PM
        Coffee break C101–C102–C103 (ENSEEIHT)

        C101–C102–C103

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
      • 5
        Characterizing the Typewise Top-Trading-Cycles Mechanism for Multiple-Type Housing Markets C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse

        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 preferences, a mechanism is unanimous (or onto), individually rational, strategy-proof, and non-bossy if and only if it is the tTTC mechanism. Second, we obtain a corresponding characterization for separable preferences. We obtain additional characterizations when replacing [strategy-proofness and non-bossiness] with self-enforcing group (or pairwise) strategy-proofness. Finally, we show that for strict preferences, there is no mechanism satisfying unanimity, individual rationality, and strategy-proofness. We obtain further impossibility results for strict preferences based on weakening unanimity to ontoness and on extending the tTTC solution.

        Our characterizations of the tTTC mechanism constitute the first characterizations of an extension of the prominent top-trading-cycles (TTC) mechanism to multiple-type housing markets.

        Speaker: Flip Klijn (CSIC & Barcelona School of Economics)
      • 6
        Stable solutions for kidney exchanges C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse

        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 KEP in Europe, where optimal solutions with 2-cycles, 3-cycles and altruistic chains are computed for about 300-400 registered pairs in every three months. The concept of stability (or core in the corresponding cooperative game) is an alternative approach, that can provide group fairness and good incentives for the recipients to bring more valuable donors or multiple registered donors to the pool. In this talk, besides some new theorems on the so-called respecting improvement property, we will present novel IP techniques for computing stable (core) solutions for bounded and unbounded exchanges. Furthermore, we will show simulation results on the price of stability, and on the question to what extend the respecting improvement property holds for various solution concepts regarding the stability and optimality requirements.

        Speaker: Péter Biró (HUN-REN KRTK)
    • Morning Session: [TBA] C002 (Salle des Thèses)

      C002 (Salle des Thèses)

      ENSEEIHT

      2 Rue Charles Camichel 31000 Toulouse
      Convener: Vahideh Manshadi (Yale School of Management)
      • 7
        [TBA] C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
        Speaker: Vahideh Manshadi (Yale School of Management)
      • 10:00 AM
        Coffee break C101–C102–C103 (ENSEEIHT)

        C101–C102–C103

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
      • 8
        [TBA] C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
        Speaker: Ali Aouad (London Business School)
      • 9
        [TBA] C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
        Speaker: Jay Sethuraman (Columbia University)
    • 12:00 PM
      Lunch C101–C102–C103

      C101–C102–C103

      ENSEEIHT

      2 Rue Charles Camichel 31000 Toulouse
    • Afternoon Session: [TBA] C002 (Salle des Thèses)

      C002 (Salle des Thèses)

      ENSEEIHT

      2 Rue Charles Camichel 31000 Toulouse
      Convener: Olivier Tercieux (CNRS & Paris School of Economics)
      • 10
        [TBA] C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
        Speaker: Olivier Tercieux (CNRS & Paris School of Economics)
      • 3:00 PM
        Coffee break C101–C102–C103 (ENSEEIHT)

        C101–C102–C103

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
      • 11
        Optimal Queueing Auctions C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse

        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 of time to complete, and many goods, such as public housing, become available at stochastic times. Buyers for these services and goods also arrive stochastically over time. Specifically, we consider an M/M/1 model in which a potential buyer arrives at a Poisson rate, and the arrival of a good takes exponential-distributed time. Each buyer is privately informed of his valuation of the good, which is distributed according to some atomless distribution, and incurs a waiting cost per unit of time.

        The seller commits to a Markovian mechanism that charges a monetary fee as a function of the type a buyer reports. Each feasible mechanism induces a Markov chain on the number and types of buyers in the queue. We look for a mechanism that maximizes the expected revenue at the steady state---the stationary distribution of the Markov chain. The extant literature from Operations Research considers screening buyers with a static policy not contingent on the state. We solve for a dynamically optimal screening mechanism that involves general dynamic allocations, and, in the process, we pin down the associated stationary distribution of the (infinite-dimensional) state. The optimal mechanism uses a reserve price (or minimum bid) that increases with the number of buyers in a queue and an auction to select the buyer with the highest valuations among those in the queue. The former feature means that the arrival of a new buyer either triggers the queue length to increase if all buyers have sufficiently high valuations or triggers an exit of a buyer with the lowest valuation. As the cost of waiting goes to zero, the optimal mechanism converges to the efficient auction rule with a reserve price set at the standard monopoly price.

        Speaker: Andy Choi (Bocconi University)
      • 12
        [TBA] C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
        Speaker: Simon Mauras (Tel Aviv University)
    • Morning Session: [TBA] C002 (Salle des Thèses)

      C002 (Salle des Thèses)

      ENSEEIHT

      2 Rue Charles Camichel 31000 Toulouse
      Convener: Jean Mairesse (CNRS & LIP6)
      • 10:00 AM
        Coffee break C101–C102–C103 (ENSEEIHT)

        C101–C102–C103

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
      • 13
        Greedy Algorithm for Multiway Matching with Bounded Regret C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse

        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 online and can be stored in a buffer), and online-nonqueueable (which arrive online and must be matched on arrival or lost). We prove the efficacy of a simple greedy algorithm when the corresponding static planning linear program (SPP) exhibits a non-degeneracy condition called the general position gap (GPG). In particular we prove that, (i) our greedy algorithm gets bounded any-time regret when no configuration contains both an online-queueable and an online-nonqueueable resource, and (ii) O(log t) expected any-time regret otherwise (we also prove a matching lower bound). By considering the three types of resources, our matching framework encompasses several well-studied problems such as dynamic multi-sided matching, network revenue management, online stochastic packing, and multiclass queueing systems.

        Speaker: Varun Gupta (Northwestern University)
    • 12:00 PM
      Lunch C101–C102–C103

      C101–C102–C103

      ENSEEIHT

      2 Rue Charles Camichel 31000 Toulouse
    • Afternoon Session: Online Matching: from Theory to Practice C002 (Salle des Thèses)

      C002 (Salle des Thèses)

      ENSEEIHT

      2 Rue Charles Camichel 31000 Toulouse
      Convener: Aranyak Mehta (Google Research)
      • 14
        Online Allocation in Online Advertising: Matching, Auctions, and Autobidding C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse

        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 these settings, including optimal algorithms and equilibrium properties.

        Speaker: Aranyak Mehta (Google Research)
      • 3:00 PM
        Coffee break C101–C102–C103 (ENSEEIHT)

        C101–C102–C103

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
      • 15
        Algorithms for Autobidding in Online Advertising C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse

        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 constraints. We consider the problem from the perspective of a single advertiser, and we focus on two of the most prevalent constraints in practice: Budget and Return-on-Spend (RoS). Technically, we take the approach of the primal-dual framework and first-order low-regret dynamics from online learning, and show how the problem-specific structures in "auto-bidding" can lead to simple online algorithms with provable performance guarantees.

        Speaker: Di Wang (Google Research)
      • 16
        Stochastic Matching: A Polytope Perspective C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse

        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 on the conservation equation between arrivals and departures, are:
        - We give simple relationships between departure and arrival rates, the shape of the compatibility graph, and the existence of a stable matching policy.
        - We describe the polytope of non-negative solutions of the conservation in the degenerated and non-degenerated cases. Any stable policy necessarily yields one of these solutions.
        - Reciprocally, we show that any part of the polytope can be reached (possibly asymptotically) by using non-greedy policies. The same result does not hold for greedy policies.

        This is a joint work with Céline Comte, Sushil Varma, and Ana Bušić.

        Speaker: Fabien Mathieu (Swapcard)
    • Morning Session: Matching in Dynamic Environments C002 (Salle des Thèses)

      C002 (Salle des Thèses)

      ENSEEIHT

      2 Rue Charles Camichel 31000 Toulouse
      Convener: Amin Saberi (Stanford)
      • 17
        Online Matching and Applications C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
        Speaker: Amin Saberi (Stanford)
      • 10:00 AM
        Coffee break C101–C102–C103 (ENSEEIHT)

        C101–C102–C103

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
      • 18
        [TBA] C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
        Speaker: Rad Niazadeh (University of Chicago)
      • 19
        Approximating Optimum Online for Online Capacitated Allocation C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse

        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 algorithm for c=0.0115. This can be contrasted to the (tight) 0.5-competitive algorithms to the optimum offline benchmark from the prophet inequality literature. Optimum online is a recently popular benchmark for online Bayesian problems which can use unbounded computation, but not "prophetic" knowledge of future inputs. A key technical challenge in deriving our guarantee is bounding the positive correlation among users introduced when rounding a LP relaxation online. Unlike in the case of unit capacities, this positive correlation is unavoidable for guarantees beyond 0.5. Conceptually, our results show that the study of optimum online as a benchmark can reveal problem-specific insights that are irrelevant to competitive analysis.

        Speaker: Tristan Pollner (Stanford)
    • 12:00 PM
      Lunch C101–C102–C103

      C101–C102–C103

      ENSEEIHT

      2 Rue Charles Camichel 31000 Toulouse
    • Afternoon Session: [TBA] C002 (Salle des Thèses)

      C002 (Salle des Thèses)

      ENSEEIHT

      2 Rue Charles Camichel 31000 Toulouse
      Convener: Matthieu Jonckheere (CNRS & LAAS)
      • 3:00 PM
        Coffee break C101–C102–C103 (ENSEEIHT)

        C101–C102–C103

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse
      • 20
        Online Matching in Geometric Random Graphs C002 (Salle des Thèses)

        C002 (Salle des Thèses)

        ENSEEIHT

        2 Rue Charles Camichel 31000 Toulouse

        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 practice. Some theoretical support for this practical success was established in specific classes of graphs, where the connections between different vertices lack strong correlations - an assumption not always valid. To bridge this gap, we focus on the following model: both users and campaigns are represented as points uniformly distributed in the interval [0,1], and a user is eligible to be paired with a campaign if they are similar enough, i.e. the distance between their respective points is less than c/N, with c>0 a model parameter. As a benchmark, we determine the size of the optimal offline matching in these bipartite random geometric graphs. In the online setting and investigate the number of matches made by the online algorithm closest, which greedily pairs incoming points with their nearest available neighbors. We demonstrate that the algorithm's performance can be compared to its fluid limit, which is characterized as the solution to a specific partial differential equation (PDE). From this PDE solution, we can compute the competitive ratio of closest, and our computations reveal that it remains significantly better than its worst-case guarantee. This model turns out to be related to the online minimum cost matching problem, and we can extend the results to refine certain findings in that area of research. Specifically, we determine the exact asymptotic cost of closest in the ϵ-excess regime, providing a more accurate estimate than the previously known loose upper bound.

        Speaker: Flore Sentenac (HEC Paris)