Proportionally Fair Matching via Randomized Rounding
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912158178082816 |
|---|---|
| author | Duppala, Sharmila Grammel, Nathaniel Luque, Juan MacRury, Calum Srinivasan, Aravind |
| author_facet | Duppala, Sharmila Grammel, Nathaniel Luque, Juan MacRury, Calum Srinivasan, Aravind |
| contents | Given an edge-colored graph, the goal of the proportional fair matching problem is to find a maximum weight matching
while ensuring proportional representation (with respect to the number of edges) of each color. The colors may correspond to demographic groups or other protected traits where we seek to ensure
roughly equal representation from each group.
It is known that, assuming ETH, it is impossible to approximate the problem with $\ell$ colors in time $2^{o(\ell)} n^{\mathcal{O}(1)}$ (i.e., subexponential in $\ell$) even on \emph{unweighted path graphs}. Further, even determining the existence of a non-empty matching satisfying proportionality is NP-Hard.
To overcome this hardness, we relax the stringent
proportional fairness constraints to a probabilistic notion. We introduce a notion we call $δ$-\textsc{ProbablyAlmostFair}, where we ensure proportionality up to a factor of at most $(1 \pm δ)$ for some small $δ>0$ with high probability. The violation $δ$ can be brought arbitrarily close to $0$ for some \emph{good} instances with large values of matching size.
We propose and analyze simple and fast algorithms for bipartite graphs that achieve
constant-factor approximation guarantees, and return a $δ$-\textsc{ProbablyAlmostFair} matching. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_11238 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Proportionally Fair Matching via Randomized Rounding Duppala, Sharmila Grammel, Nathaniel Luque, Juan MacRury, Calum Srinivasan, Aravind Data Structures and Algorithms Given an edge-colored graph, the goal of the proportional fair matching problem is to find a maximum weight matching while ensuring proportional representation (with respect to the number of edges) of each color. The colors may correspond to demographic groups or other protected traits where we seek to ensure roughly equal representation from each group. It is known that, assuming ETH, it is impossible to approximate the problem with $\ell$ colors in time $2^{o(\ell)} n^{\mathcal{O}(1)}$ (i.e., subexponential in $\ell$) even on \emph{unweighted path graphs}. Further, even determining the existence of a non-empty matching satisfying proportionality is NP-Hard. To overcome this hardness, we relax the stringent proportional fairness constraints to a probabilistic notion. We introduce a notion we call $δ$-\textsc{ProbablyAlmostFair}, where we ensure proportionality up to a factor of at most $(1 \pm δ)$ for some small $δ>0$ with high probability. The violation $δ$ can be brought arbitrarily close to $0$ for some \emph{good} instances with large values of matching size. We propose and analyze simple and fast algorithms for bipartite graphs that achieve constant-factor approximation guarantees, and return a $δ$-\textsc{ProbablyAlmostFair} matching. |
| title | Proportionally Fair Matching via Randomized Rounding |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.11238 |