Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Proportionally Fair Matching via Randomized Rounding
Authors: Sharmila Duppala, Nathaniel Grammel, Juan Luque, Calum MacRury, Aravind Srinivasan
AAAI 2025 | Venue PDF | 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. |