There is arbitrariness in optimum solutions of graph-theoretic problems that can give rise to unfairness. Incorporating fairness in such problems, however, can be done in multiple ways. For instance, fairness can be defined on an individual level, for individual vertices or edges of a given graph, or on a group level. In this work, we analyze in detail two individual-fairness measures that are based on finding a probability distribution over the set of solutions. One measure guarantees uniform fairness, i.e., entities have equal chance of being part of the solution when sampling from this probability distribution. The other measure maximizes the minimum probability for every entity of being selected in a solution. In particular, we reveal that computing these individual-fairness measures is in fact equivalent to computing the fractional covering number and the fractional partitioning number of a hypergraph. In addition, we show that for a general class of problems that we classify as independence systems, these two measures coincide. We also analyze group fairness and how this can be combined with the individual-fairness measures.
Traditionally, when confronted with an instance of an optimization problem, the instance is considered solved when a provably optimum solution has been found. After all, what more can be wished for? We should acknowledge that there can be a large amount of arbitrariness in selecting an optimum solution, and that this can be perceived as a source of unfairness.
Imagine one is a patient with end-stage renal disease, and that there is a donor who is willing to donate a kidney but who is incompatible with you. Imagine further that you and your incompatible donor enter a kidney exchange program; we will refer to the pair entering the program as a node. Entering this program means that at regular moments, runs of software are made, and the output of such a run consists of a set of exchanges between nodes. A patient from a node involved in such an exchange receives a kidney, other patients do not. Clearly, it is quite relevant whether one is included in such an exchange or not. While the software may find an optimum solution (according to some criterion, say maximizing the number of exchanges), it can be the case that some node is not selected for an exchange while being part of some optimum solution. In such cases it can be hard to explain that the software simply selects an optimum solution which somehow favors some nodes at the expense of others. In this contribution, we aim to pursue this matter from a fairness point of view, using kidney exchange as a running example.
We analyze an approach that has been used by, among others, Farnadi et al. [
Although this sampling approach is not new, it has mostly been studied computationally. In
this article, we take a fresh look into this approach. While existing results in the literature mostly
considered the approach by Flanigan et al. [
We formulate a model for finding a probability distribution over the set of feasible solutions of
a graph-theoretical optimization problem. This model resembles fairness models for concrete
problems that exist in the literature [
To achieve individual fairness, we construct a probability distribution {}∈ over , such that if we sample according to , every element ∈ has equal probability to be in the sampled subset. Our aim is to maximize this probability, which we call (for uniform probability). For any ∈ , let ⊆ denote the collection of subsets from that contain the . We model the problem of maximizing with the following linear program (LP). = maximize subject to
∑︁ = ∈ ∑︁ = 1, ∈ ≥ 0 ∈ R.
∀ ∈ , ∀ ∈ , (1a) (1b) (1c) (1d) (1e) Constraints (1b) ensure that each element ∈ is selected with uniform probability, while Constraint (1c) and Constraints (1d) ensure that is a probability distribution over .
We also consider a variant of this problem, where our notion of fairness is relaxed to
maximizing the minimum probability that a ground set element is selected. This is also referred
to as Rawlsian justice, based on fairness principles introduced by Rawls [
The fairness measures and are related to concepts developed in fractional hypergraph
theory. We refer to Scheinerman and Ullman [
One can show that determining can then be alternatively formulated as determining the fractional partitioning number and similarly that measure can be formulated as determining the fractional covering number, as summarized in the following result.
Lemma 1. Let ℋ = (, ) be a hypergraph. Then it holds that =
1 = =(ℋ) if =(ℋ) is finite, and = 0 otherwise.
In fact, when we apply this to the kidney exchange example, one can show that this implies the following, rather high, lower bound on when it is positive.
Corollary 1. For fair matching for vertices, if > 0, then ≥ 23 .
1 . Furthermore, ≥ (ℋ)
A fair probability distribution with respect to and can be found by solving the LP (1)
for and , respectively. Linear programs are solved routinely in practice by the simplex
algorithm [
Examples where minimizing ∑︀∈ can be done in polynomial time are matching, shortest paths, spanning trees, and many other combinatorial problems.
The framework that determines and (Section 2) can be applied to arbitrary set systems (, ). The system (, ) is an independence system when ∅ ∈ and for every ∈ , we have ′ ∈ for all ′ ⊆ . Independence systems are also known as simplicial complexes or downward-closed set systems. Many independence systems are known; we mention here: edge sets that form matchings, edge sets that form forests, vertex sets that are independent sets, and matroids. While in general there is no relation between and other than ≤ , one of our main contributions is that for independence systems that these two measures coincide. Theorem 3. For any independence system (, ), = .
Other than arbitrariness in selecting a solution, unfairness can also be introduced through systemic bias in the definition of the model or the description of the problem. For the kidney exchange example, patients with certain blood types are more likely to be matched, simply because they are compatible with a larger group of donors. To achieve this so-called group fairness among diferent types of patients, one can ensure representation of protected groups in the solution. Not much existing work combines individual and group fairness, while we show that both approaches can be combined in a single framework.
Our problem input now not only consists of a set system (, ), but also of a collection of groups = {1, . . . , }, with ⊆ subsets of the ground set , for all ∈ []. We assume that the groups are pairwise disjoint; when considering groups that arise from a single sensitive attribute, this is in many cases a natural assumption. We impose group fairness constraints on the possible solutions, i.e., we require ex-post group fairness. We thus restrict the set to only solutions that satisfy the group fairness constraints, gf ⊆ . Although it is possible to also handle group fairness in an ex-ante setting as opposed to ex-post, group fairness constraints are often hard conditions imposed on solutions, and in some cases required by regulations or law.
We consider two types of group fairness constraints. Absolute constraints enforce that the number of individuals from a group is between a given lower and upper bound. Relative constraints bound the ratio between the number of individuals for a pair of groups, e.g., to impose that a solution must contain the same number of individuals from each group. For the fair matching for vertices problem in the kidney exchange example, we obtain the following. Theorem 4. Let = (, ) be a graph with a constant number of pairwise disjoint groups of vertices. Let gf denote the collection of vertex-subsets covered by matchings in , restricted to absolute and/or relative group fairness constraints. Then determining and for gf can be done in polynomial time. This research is supported by NWO Gravitation Project NETWORKS, Grant Number 024.002.003.