Graph matching forms a fundamental computational problem that can be used in many wide-ranging applications such as resource allocation, e-commerce, kidney exchange, ad placement, and ride-sharing. While the most classical version of this problem is well understood, many real-world applications impose additional practical considerations, such as inherent uncertainty in the underlying graph structure or requirements that constructed solutions adhere to some notion of fairness. For instance, in many applications the vertices of the graph are not known in advance, but are instead revealed to the algorithm in discrete stages. For instance, in ad placement applications, users arrive one by one, and neither the users nor their order of arrival is known to the algorithm a priori. The many variants of the online matching problem model such situations and capture real-world problems such as e-commerce, ad allocation, and ride-sharing. This family of problems is far less well understood than the classical (offline) matching problem.

We also consider the case where the graph may be stochastic, so that the edge set of the graph is unknown and random. In this setting, there is a known probability associated with each edge, indicating the probability that the edge exists; but the actual existence is only discovered upon probing the edge, wherein the edge must be matched if it exists. This models uncertainty in the success or quality of a match: for instance, in the ad allocation application, it is unknown a priori whether a user will click on an ad (and, thus, if revenue will be earned, in the pay-per-click model). We may further introduce patience constraints for the vertices, limiting the total number of its incident edges that may be probed

Some matching problems will include variants of both of these types of uncertainty, leading to the online stochastic matching problem. In this variant (which models ad allocation settings), vertices arrive one at a time and the algorithm must probe its incident edges, committing to match the first probed edge that exists. We present results for this setting, particularly with patience constraints. We further generalize the model to consider settings where the patience of a vertex is not known in advance and is stochastic (with some known distribution).

Beyond these notions of uncertainty, we also consider variations that seek to incorporate fairness into the solutions. We specifically consider the case of proportional fairness, wherein the edges of the graph are assigned colors and the constructed solution must ensure that each color is represented in the matching in roughly equal proportions (specifically, that the proportion of edges of each color within the matching lies between some given bounds alpha and beta). In this setting, strong hardness results are known when the proportionality constraints are strictly enforced: In fact, prior work shows that in this case, it is not possible to find any approximately optimal solution in polynomial time unless ETH is false. To remedy this, we consider a slight relaxation, where a small violation in the proportionality constraint is allowed; we propose a randomized algorithm and show that, with high probability, the violations in the proportionality constraints are small.