Secretary Matching with Vertex Arrivals and No Rejections

Mohak GoyalAAAI 2022 · DOI

Abstract

This paper addresses the challenge of online matching in scenarios where every arriving vertex must be matched, precluding the option of rejection. Operating under the Secretary Matching model—characterized by random arrival orders and arbitrary edge weights—the author develops constant-factor competitive algorithms for bipartite, general, and roommate matching problems. Notably, the work improves the competitive ratio for roommate matching from 24.72 to 7.96 and introduces the first constant-factor results for several "no-rejection" variants.

Introduction

In traditional online matching literature, such as ad auctions or ride-hailing, algorithms often have the luxury of leaving a vertex unmatched if no suitable partner is available. However, many real-world allocation problems, such as assigning students to dormitory rooms or pairing mentors with mentees, require that every participant be matched. This "no-rejection" constraint introduces significant complexity.

In the classic Secretary Problem, an algorithm typically rejects the first $1/e$ fraction of candidates to establish a quality threshold. In a no-rejection environment, these early arrivals must be matched immediately, risking the "waste" of resources on suboptimal pairings before the global distribution of edge weights is understood. This paper explores how to maintain competitive performance while satisfying the requirement that every vertex is assigned a partner by the end of the process.

The Secretary Matching Model

The paper operates within a specific theoretical framework:

  1. Random Arrival: Vertices arrive one by one in a uniformly random order.
  2. Arbitrary Weights: Edge weights (representing the value of a match) are arbitrary and only revealed upon a vertex's arrival.
  3. No Rejections: Every vertex must be matched by the conclusion of the algorithm.

Algorithmic Approaches

The author proposes a suite of multi-phase algorithms tailored to different graph structures.

Bipartite Matching (ALG1 & ALG2)

For bipartite graphs with offline resources, the paper utilizes a two-phase strategy. During the exploration phase, arriving vertices are matched to available offline resources uniformly at random. In the subsequent exploitation phase, the algorithm calculates an optimal matching based on the vertices observed thus far. If the optimal partner for a new arrival is still available, the match is made; otherwise, the algorithm defaults to a random available partner to satisfy the no-rejection constraint.

General (Non-Bipartite) Matching (ALG3)

General matching is more complex because all vertices arrive online. The author introduces a three-phase approach:

  • Exploration: Initial vertices are placed into a "waiting pool."
  • Selective Matching: Arriving vertices are matched to those in the waiting pool only if they contribute to a locally optimal matching.
  • Forced Matching: To ensure no vertex is left unmatched, the algorithm triggers a forced match to a random waiting vertex if the pool size threatens to exceed the number of remaining arrivals.

Roommate Matching (ALG4)

The roommate matching problem is addressed by bifurcating the valuations into person-to-room and person-to-person utilities. The algorithm uses a randomized coin flip to decide whether to apply the bipartite or general matching logic to a specific instance.

Key Insights

The Waiting Pool Strategy

A critical insight in general matching is the management of the waiting pool. The algorithm is designed to never match two waiting vertices together. By only matching new arrivals to the waiting pool, the algorithm preserves the diversity of the pool for future arrivals, which is essential for maintaining a high competitive ratio.

Self-Correcting Processes

The proof of the general matching algorithm's efficiency relies on the observation that the waiting process is self-correcting. As the pool grows, the probability of adding more vertices decreases. This allows for the application of Chernoff-like concentration bounds to dependent variables, providing a robust mathematical foundation for the competitive ratio.

The Impact of Capacity

Interestingly, the research demonstrates that increased capacity can simplify the problem. In bipartite matching, having a capacity of 2 (e.g., two beds per room) allows for a better competitive ratio (4.62) compared to a capacity of 1 (5.46). The "second chance" provided by the additional capacity allows the algorithm to be more selective in its exploitation phase.

Results and Competitive Ratios

The paper establishes the following competitive ratios, representing the performance of the online algorithm against an offline optimal solution:

Problem Type Competitive Ratio Significance
Bipartite (Capacity 1) 5.46 Refined analysis of prior work
Bipartite (Capacity 2) 4.62 New result
General Matching 3.34 New result for non-bipartite graphs
Roommate Matching 7.96 Improvement over previous 24.72

All proposed algorithms are computationally efficient, operating in polynomial time.

Limitations and Future Directions

While this work provides significant upper bounds, several avenues for future research remain. First, the paper does not establish tight lower bounds; it is currently unknown if a 2-competitive algorithm is achievable for these variants. Second, the current algorithms are not incentive-compatible, meaning participants might achieve better outcomes by misrepresenting their preferences. Finally, the results depend on the random arrival assumption of the Secretary model. Exploring these problems under adversarial arrival orders (Prophet Inequality models) remains a significant open challenge.

Summary updated

BibTeX
@inproceedings{goyal2022secretary,
  author = {Mohak Goyal},
  title = {{Secretary Matching with Vertex Arrivals and No Rejections}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20437},
}
Figure