Research map / Multi-agent systems and games / Games and equilibria
A Unified Approach to Online Matching with Conflict-Aware Constraints
Pan Xu, Yexuan Shi, Hao Cheng, John Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, Yongxin Tong, Leonidas Tsepenekas
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use LP-guided sampling SAMP(1) instead of Greedy | online matching with conflict-aware constraints · Meetup (San Francisco) and synthetic | competitive ratio: ratio gap of at least 0.1 | Improved |
| use SAMP(1) instead of Uniform sampling | online matching with conflict-aware constraints · Meetup and synthetic | competitive ratio: ratio gap of at least 0.1 | Improved |
| scale sampling probability to 0.8 (SAMP(0.8)) instead of 1 (ablation) | SAMP · Meetup and synthetic | competitive ratio | Hurt |
| use theory-suggested alpha = 1/(1+Delta) instead of larger alpha such as 1 or 0.8 (ablation) | SAMP(alpha) · practical instances | competitive ratio | Hurt |
| increase online rounds T (ablation) | LP-based heuristics vs Greedy · synthetic, T from 100 to 1000 | competitive ratio | Mixed |
| increase event capacity upper bound CU (ablation) | LP-based heuristics and Greedy · synthetic, CU from 6 to 20 | competitive ratio: gap stays around 0.1 | Improved |
| increase neighbor probability p (larger Delta) (ablation) | SAMP · synthetic, p from 0.05 to 0.25 | competitive ratio | Hurt |
| raise user capacity from 1/3 Dcv to Dcv (ablation) | SAMP(1) vs baselines · Meetup | competitive ratio | No clear effect |
Closest papers by meaning
- Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions (NeurIPS 2024 · similarity 0.88)
- Online bipartite matching with imperfect advice (ICML 2024 · similarity 0.87)
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning (NeurIPS 2024 · similarity 0.86)
- Beyond the Half Approximation: Fair and Efficient Online Class Matching (NeurIPS 2026 · similarity 0.85)
- Fairness and Efficiency in Online Class Matching (NeurIPS 2024 · similarity 0.85)
- Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
