We study online metric matching with $n$ servers and $n$ requests, all sampled independently and uniformly from $[0,1]^d$. We analyze the Greedy algorithm, which matches each arriving request to its closest available server. Despite its strong empirical performance, non-trivial bounds on Greedy's competitive ratio were previously known only for $d = 1$, where it is $O(1)$-competitive [BFP23]. We prove that Greedy is $O(1)$-competitive for every fixed $d\geq3$ and has competitive ratio $Θ(\sqrt{\log n})$ for $d=2$. Our proof first analyzes Greedy on the flat torus and then transfers the resulting estimates to the cube.
Token systems support repeated service exchange without monetary transfers, but their viability depends on the stability of token balances. We study token systems with compatibility constraints among agents. A requester is randomly sampled in each period, and only a few randomly sampled agents are available to provide service. We establish a necessary and sufficient condition for stability and show that the minimum-token rule, which selects the available provider with the lowest token balance, achieves the optimal stability region. We then apply this stability criterion to a random token system generated from stochastic block models with uniformly sampled requesters. We tightly characterize the stability regime by identifying two obstructions to stability: insufficient service opportunities for a group of communities or for an individual agent.
Süleyman Kerimov, Pengyu Qian, Mingwei Yang, Sophie H. Yu
原文摘要
We study centralized two-way dynamic matching markets in which agents arrive stochastically over time and wait in queues associated with their types. We focus on static priority policies that assign each agent type a fixed ranking over its neighbors and make online matching decisions using only queue availability. We propose the General Priority ($\mathbf{GP}$) policy, which builds on the Tree Priority ($\mathbf{TP}$) policy introduced in [KAG25]. Under the general position gap condition, $\mathbf{GP}$ selects matches using a nondegenerate optimal basic solution of the fluid relaxation. It prioritizes children over parents within trees and consistently gives clockwise neighbors priority over counterclockwise neighbors on each cycle. We establish the optimal all-time regret scaling $O(ε^{-1})$ for $\mathbf{GP}$ on general two-way matching networks, where the general position gap $ε$ measures the fluid relaxation's distance from degeneracy. In particular, this resolves the conjecture by [KAG25] on the optimal $ε$-dependence for $\mathbf{TP}$.