Pushing the Limits of Fairness in Algorithmic Decision-Making

1 Introduction

With machine learning (ML) deployed worldwide to make critical decisions, there is exploding interest in ensuring that the ML models treat (groups of) people fairly. While algorithmic fairness is a nascent subject of study in machine learning, it has deep roots in social choice theory from economics. The more recent field of computational social choice at the intersection of computer science and economics has explored the applicability of these economic fairness notions to algorithmic paradigms. The purpose of this article is to demonstrate that these notions are well-suited to a broad range of algorithmic decision-making settings and deserve an in-depth study.

Take, for example, the classical economic notion of the core [Gillies, 1953], which demands that when collective resources are divided amongst a group of people, no subset of them be able to find a better 1 allocation of their "entitled share" of the collective resources. This applies to participatory budgeting [Fain et al., 2018], where a city allocates a public budget to fund infrastructure projects and the "entitled share" of any group of residents is defined in proportion to the size of the group. The same notion also applies to conference peer review [Aziz et al., 2023], where the "resource" being divided is the reviewing capacity and the "entitled share" of any group of authors is the reviewing capacity they contribute by also serving as potential reviewers.

These types of fairness notions are appealing because they are well-defined for a wide range of domains, including ones with highly complex decision spaces, and they pay explicit attention to the preferences of the stakeholders involved. In this article, I will survey their applications to various algorithmic decision-making paradigms, based partly on my own work, and argue that these notions can play a key role in realizing the grand vision of an overarching theory for algorithmic fairness that spans a diverse set of applications.

1 Here, "better" means a Pareto improvement, which makes at least one person happier without hurting anyone.

In Section 2, I will first define several fairness definitions, some proposed in my own work, using an example application: the allocation of homogeneous divisible goods. Then, in Section 3, I will demonstrate their applicability to a wide range of real-world domains, which my work has explored extensively. Finally, in Section 4, I will conclude with a call to arms for exploring the applicability of such preference-based fairness definitions in novel domains in an attempt to develop an overarching theory for algorithmic fairness.

2 Fairness Definitions

Let us review the basic model for allocating homogeneous divisible goods, which will serve as our reference context. There is a set of agents N and a set of divisible goods M. Each agent i ∈ N values each good g ∈ M at vi,g, and agents have additive linear preferences: for receiving Xg ∈ [0, 1] fraction of each good g, the utility of agent i is given by vi(X) = ∑g∈M Xg · vi,g, where X = (Xg)g∈M. Let vi(M) ≜ ∑g∈M vi,g be the total value of agent i.

An allocation A ∈ [0, 1]N×M allocates Ai,g fraction of each good g to each agent i; a valid allocation must satisfy ∑g∈M Ai,g ≤ 1 for all i ∈ N. Denoting Ai = (Ai,g)g∈M, each agent i derives utility vi(Ai) under this allocation. This models many real-world applications where divisible resources must be allocated; an example is the division of food items (such as milk or rice) donated to a food bank.

Next, let us review some prominent fairness definitions.

2.1 Entitlement-Based Notions

Some definitions focus on a notion of entitlement of an agent or a group of agents and aim to treat each agent or group of agents no worse than their entitlement. I refer to them as entitlement-based notions. One example is the classical notion of proportionality [Steinhaus, 1948].

Definition 1 (Proportionality). An allocation A is proportional if vi(Ai) ≥ (1/n) · vi(M) for each i ∈ N. Here, agent i is viewed as entitled to receiving 1/n-th of her total value.

The notion of the core [Gillies, 1953], imported from the economic theory of non-transferable utility games, lifts this idea to all (2n - 1 many) non-empty groups of agents.

Definition 2 (The Core). An allocation A is in the core if there is no non-empty group of agents S ⊆ N and allocation B of the goods to agents in S such that vi(Ai) ≤ (|S|/n) · vi(Bi) for all i ∈ S and at least one inequality is strict. Here, each group S is viewed as entitled to receiving |S|/n-th of any combination of values they can achieve by dividing the goods amongst themselves.

Note that the core logically implies proportionality, as the latter basically imposes the core condition on singleton groups. Let me remark that instead of letting group S divide all the goods amongst themselves and scaling their utility down by a factor of |S|/n (utility-scaling version), one may allow them to divide only |S|/n fraction of each good and not perform any utility scaling (endowment-scaling version). For our reference application, the two are equivalent due to additive linear preferences, but in general they can differ significantly (e.g., see Section 3.2). The utility-scaling version is more broadly defined because in some applications it may not be clear what resources to scale or how. But when there is a compelling way to scale resources, the endowment-scaling version can often make more sense.

2.2 Comparison-Based Notions

Other notions focus on comparing the treatment provided to two agents or two groups of agents. I refer to them as comparison-based notions. A widely known example is envyfreeness [Gamow and Stern, 1958; Foley, 1967].

Definition 3 (Envy-freeness). An allocation A is envy-free if vi(Ai) ≥ vi(Aj) for all i, j ∈ N. Here, the allocations to agents i and j are being compared using the preferences of agent i (and, due to the quantifier, also those of agent j).

Crucially, the definition uses the same valuation function on both sides of the equation, thus avoiding any interpersonal comparison of utilities. Group envy-freeness [Varian, 1974; Berliant et al., 1992] extends this to all pairs of groups of agents of equal size.

Definition 4 (Group Envy-freeness). An allocation A is group envy-free if there are no non-empty groups S, T ⊆ N with |S| = |T | and allocation B of the resources ∪j∈TAj allocated to group T to agents in S such that vi(Ai) ≤ vi(Bi) for all i ∈ S and at least one inequality is strict. This ensures that group S does not envy group T collectively.

2.3 The Master Axiom

In recent work [Conitzer et al., 2019], we formulated a novel fairness definition that is logically stronger than both the core and group envy-freeness, thus sitting at the apex of both entitlement-based and comparison-based notions defined above. These logical implications are depicted in Figure 1. Group fairness extends group envy-freeness to all pairs of groups S and T , but with a careful adjustment to the notion of envy based on the difference in the sizes of the groups.

Definition 5 (Group Fairness). An allocation A is group fair if there are no non-empty groups S, T ⊆ N and allocation B of the resources ∪j∈TAj allocated to T to agents in S such that vi(Ai) ≤ (|S|/|T|) · vi(Bi) for all i ∈ S and at least one inequality is strict. Here, after allowing S to reallocate T's resources amongst themselves, their utilities are scaled down by |S|/|T|, reflecting the difference in group sizes.

At this point, one wonders whether any algorithm can provably satisfy these notions of fairness. Proportionality and envy-freeness are rather easy to satisfy, e.g., by dividing each good equally among the agents. Prior work in economics shows that an allocation maximizing the Nash social welfare (i.e., product of utilities) of the agents, which coincides with the competitive equilibrium from equal incomes (CEEI), satisfies the core [Varian, 1974] and group envy-freeness [Varian, 1974; Berliant et al., 1992]. We prove that it actually satisfies group fairness [Conitzer et al., 2019] and, together with a mild axiom, it is in fact characterized by group fairness [Freeman et al., 2020].

3 Expansive Applicability

I will now review several applications for which these fairness notions have been shown to be appealing in recent work, including in some of my own. In addition to the applications listed below, I have also explored them for public good allocation [Conitzer et al., 2017a; Fain et al., 2018; Banerjee et al., 2023], ad allocation [Hosseini et al., 2023], multi-armed bandits [Hossain et al., 2021], land division [Caragiannis et al., 2022], and team formation [Li et al., 2023].

3.1 Allocating Indivisible Goods

In the reference setting of Section 2, if the goods being allocated are indivisible (i.e., cannot be split fractionally between agents), none of the fairness notions can be guaranteed. Nonetheless, our work has shown that maximizing the Nash social welfare 2 satisfies "up to one good"-style relaxations of these notions, 3 all the way up to group fairness [Caragiannis et al., 2019; Conitzer et al., 2019].

One may find the violation of fairness, even up to one good, troubling, especially if a high-valued good causes a large violation. There are multiple ways to address this. On the one end, our work has shown that the violation can be removed ex-ante by using randomization: specifically, there always exists a randomization over envy-free up to one good allocations that is (exactly) envy-free in expectation [Freeman et al., 2020]. On the other end, we have also identified a stronger expost guarantee of envy-freeness up to any good (EFX), which informally demands that the fairness violation be caused by the least-valued good. Resolving whether an EFX allocation always exists is "fair division's biggest problem" [Procaccia, 2020], and there are promising recent developments towards a (positive) resolution [Chaudhury et al., 2020; Amanatidis et al., 2021; Akrami et al., 2023].

Our work has also shown that some of these fairness guarantees remain achievable when allocating (negativelyvalued) chores instead of goods [Ebadian et al., 2022b; Freeman et al., 2020], but many important questions remain open; see the recent survey by Amanatidis et al. [2022].

3.2 Participatory Budgeting

Participatory budgeting (PB) is a process whereby residents of a geographical region vote over how a portion of the public budget should be allocated to fund some of the proposed public projects, and hundreds of millions of dollars have been allocated worldwide via PB. See our recent book chapter for a detailed account of research on PB [Aziz and Shah, 2021].

Here, (the endowment-scaling version of) the core especially makes natural sense: it demands that no group of residents be able to find an allocation of their proportional share of the budget 4 that they prefer to chosen allocation of the whole budget. We show that ˜O(logm)-approximate core is achievable with m proposed projects [Fain et al., 2018].

Stronger notions such as group fairness or proportional fairness [Kelly, 1997] remain unexplored for PB, although our recent work explores proportional fairness for randomized single-winner selection [Ebadian et al., 2022a], which can be viewed as a special case of PB.

2 The exact rule is a subtle refinement of this.

3 Informally, violation of fairness must be due to a single good.

4 It is reasonable to demand that tax dollars be spent equitably, so each resident is entitled an equal share of the available budget and any group of residents can pool their entitlements together.

3.3 Conference Peer Review

Large conferences such as IJCAI, AAAI, and NeurIPS invite submissions from many subcommunities, and the authors of the submissions often serve as reviewers too. An advantage touted by such conferences is that their large reviewer pool can enable finding suitable reviewers with diverse expertise for many submissions. But the algorithms used to match reviewers to submissions can also mistreat a community by assigning its submissions to less qualified external reviewers, incentivizing the community to leave and set up its own conference, in which its submissions can be reviewed by more qualified reviewers from within the community.

The core turns out to be aptly-suited to addressing this issue. Defining a group of researcher's "entitled share of resources" as the reviewing capacity they offer, the core demands that no group be able to find a better reviewing assignment for their submissions using their entitled share of resources, thus preventing groups from breaking off and setting up their own conferences. Here, in addition to guaranteeing fairness, the core also contributes stability to the system.

We prove that, at least in a limited model with single-author submissions and mild conditions on authors' preferences over reviewers, a reviewing assignment in the core that satisfies load and conflict avoidance constraints always exists, and can be computed efficiently [Aziz et al., 2023]. It remains to be seen whether this can be extended to more realistic models.

3.4 Locating Public Facilities

Another interesting application of the core is public facility location via clustering, where the goal is to choose k locations for building public facilities that would fairly serve n people in a geographical region (represented as points in metric space). This application admits a natural definition of entitlements: each group of n/k people is entitled to one public facility, each group of 2n/k people is entitled to two public facilities, and so on. Then, the core demands that, for any ℓ, no group of at least ℓn/k people be able to find ℓ locations such that each member is closer to some one of the ℓ new locations than to any of the k locations chosen by the algorithm.

Chen et al. [2019] prove that there are instances with no clustering in the core, but a (1 + √2)-approximate core clustering exists for any metric. We prove that for the common case of L2 distance over a Euclidean space Rt , the approximation factor can be improved to 2 [Micha and Shah, 2020].

3.5 Allocating Educational/Computing Resources

While the maximum Nash social welfare solution works well for additive preferences, our prior work shows that another solution called the leximin solution, a refinement of Rawls' egalitarian criterion, is more appealing for other preferences.

We consider the problem of allocating unused classrooms in public schools to local charter schools [Kurokawa et al., 2018], a process mandated by California's Proposition 39. After extensive discussions with public school districts in California, we observe that a particular style of dichotomous preferences best models the needs of the charter schools, and prove that for such preferences the (randomized) leximin solution satisfies proportionality and envy-freeness, while also ensuring that no group of charter schools can manipulate the process to their advantage.

In other work, we consider the problem of allocating computing resources such as CPU, RAM, and network bandwidth among processes in a cluster environment [Parkes et al., 2015], where the class of Leontief preferences is more suitable. Noticing that the Dominant Resource Fairness (DRF) algorithm implemented in the popular distributed computing framework Apache Hadoop essentially implements the egalitarian criterion, we prove that using its leximin refinement instead would again satisfy proportionality, envy-freeness, and resistance to strategic manipulations by groups of users.

3.6 Recommender Systems

While the above applications model one-sided markets in which resources are allocated to agents with preferences, these versatile fairness notions can also be extended to twosided markets, in which agents on two sides of a market are matched to each other and agents on each side have preferences over those on the other side. This models, e.g., matching consumers to products (and, in turn, to producers) in recommender systems, matching students to schools or medical residents to hospitals, or matching refugees to pro bono service providers. A natural goal in this case is to ensure fairness among agents on each side of the market simultaneously.

In recent work [Freeman et al., 2021], we propose such an extension of envy-freeness, dubbed double envy-freeness, for many-to-many two-sided matching markets, and prove that, at least when agents on each side agree over a ranking of the agents on the other side (but may disagree in intensities), an "up to one"-style relaxation of double envy-freeness can be guaranteed in polynomial time. A natural direction for the future is to design algorithms satisfying two-sided versions of other fairness notions from Section 2.

3.7 Classification

The groupwise fairness notions of the core and group envyfreeness strengthen the individual fairness notions of proportionality and envy-freeness, respectively. But in some applications, individual fairness may already be a bar too high. For example, when using a classification algorithm to determine which defendants to grant bail or which loan applications to approve, certain individuals would inevitably be left emptyhanded. Traditional ML fairness notions such as statistical parity and equalized odds thus impose fairness with respect to specific groups only on average over their members.

Building on prior work [Balcan et al., 2019], we show that envy-freeness can also be extended in this fashion to prevent envy between groups on average, this new fairness notion subsumes notions like statistical parity and equalized odds as special cases, and it generalizes well from a small sample to an underlying population [Hossain et al., 2020].

The key advantage of such preference-based fairness notions is that they naturally apply to non-binary decisions. Thus, they prevent classifiers from "gerrymandering" fairness guarantees by, e.g., granting bail to black and white defendants at the same rate, thus satisfying statistical parity, but discriminating in the average bail amounts assigned to the two groups [Arnold et al., 2018].

4 The Quest for an Overarching Theory

The grand vision here is to develop an overarching theory for algorithmic fairness, which can be used to pick or formulate the best-suited notions of fairness for any application at hand and design efficient algorithms provably satisfying them.

One should not mistake this for a quest for an "ultimate notion of fairness" that supersedes all others. Such an assertive notion, which certifies that no unfairness would remain upon its satisfaction, does not yet exist as this requires a deep understanding of long-term impacts of algorithmic decisions. Instead, we have preventive notions, each of which prevent the algorithm from imposing a specific type of harm. Since there exist many types of harms, we need to aim for (approximately) satisfying multiple fairness notions simultaneously.

Several milestones must be conquered along the long road to achieving this grand vision. Surely, we need to identify novel types of harms and formulate fairness notions which prevent them. As we design provably fair algorithms, we also need to understand their generalization guarantees [Balcan et al., 2019; Micha and Shah, 2020; Hossain et al., 2020] and the price of imposing fairness in terms of other objectives of interest [Barman et al., 2020; Hossain et al., 2020].

But most importantly, we need to expand the study of fairness to new domains. For example, these notions are applicable to online problems where agents and/or resources arrive and depart over time [Kash et al., 2014; Hosseini et al., 2023; Banerjee et al., 2023]. Another domain of significant recent interest is political redistricting or gerrymandering [Borodin et al., 2018; Borodin et al., 2022], for which the core seems aptly-suited to define a fair redistricting [Benade et al., 2023]. Finally, the core can also be used to automate moral decision-making [Noothigattu et al., 2018; Lee et al., 2019; Conitzer et al., 2017b]. For example, in the classical trolley problem, where one must decide whether to divert a trolley to save five people at the expense of one, the core demands that the diversion happen with probability exactly 5/6, the collective entitlement of the five people. This is an ethical position worth exploring, but the real strength of the core lies in generalizing this basic idea to arbitrarily complex ethical scenarios.

To that end, let me reiterate that notions like the core are appealing because they simultaneously provide guarantees for all possible groups without needing to prespecify them based on fixed attributes such as race, gender, or sexual orientation. Most other fairness notions apply either only to prespecified groups (e.g., statistical parity, equalized odds [Hardt et al., 2016], and calibration [Dawid, 1982; Pleiss et al., 2017]) or to exponentially many groups (e.g., multicalibration [H´ebert-Johnson et al., 2018] and subgroup fairness [Kearns et al., 2018]), but not to all possible groups.

I conclude with a call to arms for exploring preferencebased fairness notions in a wide range of domains and understanding how well they align with human perceptions of fairness [Saxena et al., 2019; Lee et al., 2019; Gal et al., 2017].

Acknowledgments

I acknowledge the support of an NSERC Discovery Grant. I am grateful to all my collaborators, who were the driving force behind the work reported in this article.