Fairness and Uncertainty in Graph Matching

Abstract

Graph matching is a fundamental computational problem with a broad range of applications across different domains, including resource allocation, e-commerce, kidney exchange, ad placement, and ride-sharing. While the classical maximum matching problem is well-understood, many real-world applications impose additional practical considerations such as uncertainty in the graph structure and fairness requirements. In this dissertation, we consider variations of matching that incorporate these considerations, and describe some key results for these problems. First, we examine online bipartite matching with stochastic edges, where the vertices of one side of the partition arrive sequentially and the algorithm knows only the \emph{probability} with which each of its incident edges exists. Upon the arrival of a vertex, the algorithm must \emph{probe} the edges one by one to determine existence, committing to match the first one found to exist. Arriving vertices may further have a \emph{patience} value (the maximum number of its incident edges that may be probed), which may itself be stochastic (in which case the algorithm has only distributional knowledge of the patience). We present a framework for these problems and derive results under adversarial, known IID, and prophet'' arrival models, so long as the single-arrival case can be solved. To this end, for the single-arrival case, we show an optimal algorithm for a constant hazard rate'' model, and a $1/2$-approximation under general patience distributions. We also consider a two-sided arrival model and demonstrate a constant-factor approximation for this model. Finally, we present some negative results related to these settings. We then consider \emph{offline} stochastic matching for bipartite graphs, and give a $(1-1/\euler)$-approximation for this problem when the vertices of one side all have patience 1. Our approach has connections to contention resolution schemes, which we then investigate further. We describe results for contention resolution schemes for the matching polytope under two different arrival settings: adversarial order and random order; and for both general graphs and bipartite graphs. Finally, we study proportionally fair matching, where we are given an \emph{edge-colored} graph, and we must find a matching of maximum possible weight while ensuring that the proportion of edges in the matching of any given color is between some specified parameters $\alpha$ and $\beta$. Due to strong hardness results for the exact version of this problem, we consider a slightly relaxed probabilistic version instead. Here, we allow for small violations in the proportional fairness constraints, and achieve a constant factor approximation with probabilistic guarantees on the amount by which the proportionality constraint is violated.