Optimal matching under size priority

Nathanaël Enriquez, Mike Liu, Laurent Ménard, Vianney Perchet · 2026

Read Optimal matching under size priority by Nathanaël Enriquez, Mike Liu, Laurent Ménard, Vianney Perchet (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-20502.txt.

Introduction

Nathanaël Enriquez, Mike Liu, Laurent Ménard, and Vianney Perchet study optimal matching under size priority in edge-weighted random graphs. Earlier work on the local limit of maximal weight matchings assumed the weights are atomless, which guarantees a unique best matching. That assumption excludes maximal size matchings, where all edge weights are equal.

The authors overcome the difficulty by assigning independent random weights as tiebreakers. Matching problems sit beneath assignment markets, from jobs to kidneys. Handling the equal-weight case extends the theory to the setting where sheer size, not weight, is the goal.

Catalog record

CREATORNathanaël Enriquez, Mike Liu, Laurent Ménard, Vianney Perchet
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE227 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-20502

Browse the full library · About the Tower of Babel