skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Dynamic Matching: Characterizing and Achieving Constant Regret
We study how to optimally match agents in a dynamic matching market with heterogeneous match cardinalities and values. A network topology determines the feasible matches in the market. In general, a fundamental tradeoff exists between short-term value—which calls for performing matches frequently—and long-term value—which calls, sometimes, for delaying match decisions in order to perform better matches. We find that in networks that satisfy a general position condition, the tension between short- and long-term value is limited, and a simple periodic clearing policy (nearly) maximizes the total match value simultaneously at all times. Central to our results is the general position gap ϵ; a proxy for capacity slack in the market. With the exception of trivial cases, no policy can achieve an all-time regret that is smaller, in terms of order, than [Formula: see text]. We achieve this lower bound with a policy, which periodically resolves a natural matching integer linear program, provided that the delay between resolving periods is of the order of [Formula: see text]. Examples illustrate the necessity of some delay to alleviate the tension between short- and long-term value. This paper was accepted by David Simchi-Levi, revenue management and market analytics. Funding: This work was supported by the National Science Foundation [Grant CMM-2010940] and the U.S. Department of Defense [Grant STTR A18B-T007].  more » « less
Award ID(s):
2137286
PAR ID:
10538045
Author(s) / Creator(s):
; ;
Publisher / Repository:
INFORMS
Date Published:
Journal Name:
Management Science
Volume:
70
Issue:
5
ISSN:
0025-1909
Page Range / eLocation ID:
2799 to 2822
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Operations Research)
    Hindsight Optimality in Two-Way Matching Networks In “On the Optimality of Greedy Policies in Dynamic Matching”, Kerimov, Ashlagi, and Gurvich study centralized dynamic matching markets with finitely many agent types and heterogeneous match values. A matching policy is hindsight optimal if the policy can (nearly) maximize the total value simultaneously at all times. The article establishes that suitably designed greedy policies are hindsight optimal in two-way matching networks. This implies that there is essentially no positive externality from having agents waiting to form future matches. Proposed policies include the greedy longest-queue policy, with a minor variation, as well as a greedy static priority policy. The matching networks considered in this work satisfy a general position condition. General position is a weak (but necessary) condition that holds when the static-planning problem (a linear program that optimizes the first-order matching rates) has a unique and nondegenerate optimal solution. 
    more » « less
  2. ; ; ; ; (, Journal of Algebra and Its Applications)
    Let [Formula: see text] be a prime power and [Formula: see text]. In this paper we complete the classification of good polynomials of degree [Formula: see text] that achieve the best possible asymptotics (with an explicit error term) for the number of totally split places. Moreover, for degrees up to [Formula: see text], we provide an explicit lower bound and an asymptotic estimate for the number of totally split places of [Formula: see text]. Finally, we prove the general fact that the number [Formula: see text] of [Formula: see text] for which [Formula: see text] splits obeys a linear recurring sequence. For any [Formula: see text], this allows for the computation of [Formula: see text] for large [Formula: see text] by only computing a recurrence sequence over [Formula: see text]. 
    more » « less
  3. ; (, Mathematics of Operations Research)
    Let ρ be a general law-invariant convex risk measure, for instance, the average value at risk, and let X be a financial loss, that is, a real random variable. In practice, either the true distribution μ of X is unknown, or the numerical computation of [Formula: see text] is not possible. In both cases, either relying on historical data or using a Monte Carlo approach, one can resort to an independent and identically distributed sample of μ to approximate [Formula: see text] by the finite sample estimator [Formula: see text] (μNdenotes the empirical measure of μ). In this article, we investigate convergence rates of [Formula: see text] to [Formula: see text]. We provide nonasymptotic convergence rates for both the deviation probability and the expectation of the estimation error. The sharpness of these convergence rates is analyzed. Our framework further allows for hedging, and the convergence rates we obtain depend on neither the dimension of the underlying assets nor the number of options available for trading. Funding: Daniel Bartl is grateful for financial support through the Vienna Science and Technology Fund [Grant MA16-021] and the Austrian Science Fund [Grants ESP-31 and P34743]. Ludovic Tangpi is supported by the National Science Foundation [Grant DMS-2005832] and CAREER award [Grant DMS-2143861]. 
    more » « less
  4. ; (, Mathematics of Operations Research)
    We study the convergence of divergence-regularized optimal transport as the regularization parameter vanishes. Sharp rates for general divergences including relative entropy or Lpregularization, general transport costs, and multimarginal problems are obtained. A novel methodology using quantization and martingale couplings is suitable for noncompact marginals and achieves, in particular, the sharp leading-order term of entropically regularized 2-Wasserstein distance for marginals with a finite [Formula: see text]-moment. Funding: This work was supported by the Alfred P. Sloan Foundation [Grant FG-2016-6282] and the Division of Mathematical Sciences [Grants DMS-1812661 and DMS-2106056]. 
    more » « less
  5. ; (, Operations Research)
    The fundamental problem in the study of parallel-server systems is that of finding and analyzing routing policies of arriving jobs to the servers that efficiently balance the load on the servers. The most well-studied policies are (in decreasing order of efficiency) join the shortest workload (JSW), which assigns arrivals to the server with the least workload; join the shortest queue (JSQ), which assigns arrivals to the smallest queue; the power-of-[Formula: see text] (PW([Formula: see text])), which assigns arrivals to the shortest among [Formula: see text] queues that are sampled from the total of [Formula: see text] queues uniformly at random; and uniform routing, under which arrivals are routed to one of the [Formula: see text] queues uniformly at random. In this paper we study the stability problem of parallel-server systems, assuming that routing errors may occur, so that arrivals may be routed to the wrong queue (not the smallest among the relevant queues) with a positive probability. We treat this routing mechanism as a probabilistic routing policy, named a [Formula: see text]-allocation policy, that generalizes the PW([Formula: see text]) policy, and thus also the JSQ and uniform routing, where [Formula: see text] is an [Formula: see text]-dimensional vector whose components are the routing probabilities. Our goal is to study the (in)stability problem of the system under this routing mechanism, and under its “nonidling” version, which assigns new arrivals to an idle server, if such a server is available, and otherwise routes according to the [Formula: see text]-allocation rule. We characterize a sufficient condition for stability, and prove that the stability region, as a function of the system’s primitives and [Formula: see text], is in general smaller than the set [Formula: see text]. Our analyses build on representing the queue process as a continuous-time Markov chain in an ordered space of [Formula: see text]-dimensional real-valued vectors, and using a generalized form of the Schur-convex order. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email