Technical Note—Greedy Algorithm for Multiway Matching with Bounded Regret

Varun Gupta ()
Additional contact information
Varun Gupta: Booth School of Business, University of Chicago, Chicago, Illinois 60637

Operations Research, 2024, vol. 72, issue 3, 1139-1155

Abstract: In this paper, we prove the efficacy of a simple greedy algorithm for a finite horizon online resource allocation/matching problem when the corresponding static planning linear program (SPP) exhibits a nondegeneracy condition called the general position gap (GPG). The key intuition that we formalize is that the solution of the reward-maximizing SPP is the same as a feasibility linear program restricted to the optimal basic activities, and under GPG, this solution can be tracked with bounded regret by a greedy algorithm, that is, without the commonly used technique of periodically resolving the SPP. The goal of the decision maker is to combine resources (from a finite set of resource types) into configurations (from a finite set of feasible configurations) in which each configuration is specified by the number of resources consumed of each type and a reward. The resources are further subdivided into three types—off-line (whose quantity is known and available at time 0), 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). Under GPG, we prove that (i) our greedy algorithm gets bounded anytime regret of O ( 1 / ϵ 0 ) for matching reward ( ϵ 0 is a measure of the GPG) when no configuration contains both an online-queueable and an online-nonqueueable resource and (ii) O ( log t ) expected anytime 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 multisided matching, network revenue management, online stochastic packing, and multiclass queueing systems.

Keywords: Market Analytics and Revenue Management; dynamic matching; sum-of-squares; general position gap; Lyapunov analysis; amortized analysis (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2400 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:3:p:1139-1155

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().