Proportionally Fair Matching via Randomized Rounding
Authors: Sharmila Duppala, Nathaniel Grammel, Juan Luque, Calum MacRury, Aravind Srinivasan
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We propose and analyze simple and fast algorithms for bipartite graphs that achieve constant-factor approximation guarantees, and return a δ-PROBABLYFAIR matching. (...) The paper talks about algorithm design, pseudocode, theorems, lemmas, and mathematical analysis of approximation ratios and probabilities. |
| Researcher Affiliation | Academia | 1Department of Computer Science, University of Maryland, College Park 2Graduate School of Business, Columbia University EMAIL, EMAIL, EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1 OCRS Rounding Algorithm Input: G = (U, V, E) with color classes (Ec)c [ℓ], 0 α β 1, and 0 < ε < 1. Output: subset of edges forming a matching M. 1: M 2: If α > 0, compute an optimal solution x = (xe)e E to LP-FAIR with 0 < α β 1. Otherwise, compute an optimal solution x to LP-FAIR with β in (1b) replaced by β = (1 ε)β. 3: Order the vertices of V as v1, . . . , vn arbitrarily. 4: Draw (Fvt)n t=1 as described in (2). 5: for t = 1, . . . , n with Fvt = do 6: Set u := Fvt, and au,vt := 1/2 1 (1/2) P i<t xu,vi . 7: Draw Au,vt Ber(au,vt) independently. 8: If Au,vt = 1 and u is currently unmatched, add (u, vt) to M 9: return M. |
| Open Source Code | No | The paper does not contain an unambiguous statement about releasing code, nor does it provide a direct link to a code repository. It mentions a full version on arXiv as a preprint, but this is not a code release. |
| Open Datasets | No | The paper introduces a theoretical problem on 'edge-colored graphs' and does not use any specific datasets for empirical evaluation. Thus, there is no mention of publicly available datasets or access information. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on specific datasets, therefore, there is no mention of training/test/validation splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe any experimental hardware used. |
| Software Dependencies | No | The paper describes a theoretical algorithm and its analysis. It does not mention any specific software, libraries, or solvers with version numbers that would be required to reproduce experiments. |
| Experiment Setup | No | The paper is theoretical, proposing and analyzing an algorithm. It does not contain any experimental setup details such as hyperparameters or training configurations for empirical evaluation. |