Algorithmic Fairness in Distribution of Resources and Tasks

1 Introduction

The rapid growth in the adoption of Artificial Intelligence (AI) systems has transformed the ways social, political, and commercial decisions are governed. These systems are primarily influenced by algorithmic processes, ranging from generative AI that relies on statistical patterns to symbolic and rule-based AI paradigms that require explicit representation of problems. With the rise of algorithmic methods, fairness has emerged as a pivotal concern in decision-making, particularly in application domains that involve the participation of multiple intelligent agents-autonomous agents, institutions, or humans-that often have conflicting preferences over the possible outcomes.

The field of computational social choice combines theoretical principles and axioms of fairness rooted in economics with the necessary algorithmic paradigms in computer science to offer the crucial building blocks of collective decision-making for a "society of agents". The recent efforts in this field have led to fascinating progress in fair preference aggregation methods to reach consensus or to rank outcomes [Brandt et al., 2016], to develop democratic processes for deciding on public budget spending [Aziz and Shah, 2021], and to distribute divisible (e.g. computation) or indivisible (e.g. public housing) resources and tasks [Amanatidis et al., 2023], to name a few. Fairness, in particular, plays an instrumental role in the allocation of public and private resources both in centralized and distributed settings, ranging from the distribution of scarce medical resources (e.g. vaccines) in federated healthcare and the distribution of tasks in digital gig economy

(e.g. ridesharing platforms) to the collective development of foundation models in data-oriented systems.

These problems often have to deal with complex environments with incomplete or uncertain information: preference information may be uncertain or noisy, knowledge about the resources may be incomplete, unavailable, or simply expensive to elicit, participants' strategic behavior may critically influence the desirability of outcomes, and fairness metrics may not be aligned with social axioms. Moreover, complications arise when distributing tasks generating negative values for some agents (e.g. household chores or training a machine learning model), as opposed to positively-valued resources. Despite the recent advancements, achieving fair solutions in complex environments remains a challenging (and exciting) task that begs the following fundamental questions: (i) which fairness axioms are more suitable for different applications, and whether these axioms are compatible with other societal properties (e.g. social welfare)? (ii) how should we design scalable algorithms (or approximation algorithms) to compute such fair solutions? (iii) how do we align agents' incentives to behave truthfully? And which fairness axioms are aligned with human and societal values?

In this paper, I will demonstrate the nuances in investigating algorithmic and axiomatic boundaries of fairness in distributing resources and tasks, and discuss the impact of strategic behavior of agents on fairness of solutions. The goal is to provide an overview of recent results, primarily focused on my research, in addressing the above grand challenges in designing fair algorithms.

The paper is structured as follows: In Section 2, I will survey recent works in achieving fair allocations under a variety of constraints or models, In Section 3, I will discuss the strategic aspects of fair allocation and matching markets. In Section 4, I will argue that fairness axioms should be aligned with human value judgements. Finally, I will conclude, in Section 5, by laying out an overarching plan for research in fair collective decision-making.

2 Allocating Resources and Tasks

Achieving fairness when distributing indivisible resources or tasks is a notoriously difficult problem due to several axiomatic impossibility and computational intractability results. The primary fairness concepts can be seen as either comparison-based notions that rely on pairwise comparisons between the agents (e.g. envy-freeness [Foley, 1967]), or threshold-based criteria that deal with achieving a fair-share of the set of items (e.g. maximin share [Budish, 2011]). When dealing with indivisible items, none of the above fairness notions can be guaranteed, giving rise to a variety of deterministic or randomized relaxations [Caragiannis et al., 2019; Lipton et al., 2004; Bogomolnaia and Moulin, 2004]). These existing approaches to approximate fairness often impose a high cost on information transparency or social welfare, lead to strategic behavior by participating agents, or are not robust to uncertain or dynamic environments. In this section, I will survey some of the recent research in addressing these challenges.

2.1 Allocating Goods and Resources

Epistemic Fairness. The most well-studied relaxation of envy-freeness such as envy-freeness up to one item (EF1) requires that any pairwise envy between the agents can be eliminated by the counterfactual removal of items (e.g. a single good from the envied agent) [Lipton et al., 2004; Budish, 2011]. These 'up to one' relaxations have attracted significant attention from the AI/CS community in the past few years. These fairness concepts operate on two strong assumptions: (i) agents are fully aware of other agents' allocations, and (ii) the unfairness can be justified by reminding agents of "hypothetical" worse solutions. These assumptions-although theoretically appealing-do not reflect the inherent nature of fairness in practical domains.

To address these issues, we proposed a rather radical epistemic approach that utilizes information asymmetry which, in contrast to EF1, does not require counterfactual reasoning. This epistemic framework enables us to exploit information asymmetry when allocating indivisible goods (e.g. by carefully hiding minimum information) [Hosseini et al., 2020]. We show that while minimizing this asymmetry to achieve envy-freeness remains intractable, an envy-free allocation can be computed in polynomial time by withholding information about only a small number of items (i.e. n - 1 items). Moreover, such allocations can be computed along with Pareto optimality (a welfare concept that guarantees no improving exchanges among the agents) in pseudo-polynomial time. In Section 4, I will discuss how epistemic fairness concepts are compared to their counterfactual counterparts based on perceived human values.

Guaranteeing a Fair Share. A compelling fairness axiom is maximin share (MMS), which requires that each agent receives a fair share that it is at least as good as if they were to create the best n-partition and receive the least preferred bundle [Budish, 2011]. Since such allocations do not always exist [Kurokawa et al., 2018], several multiplicative approximations have been proposed that give each agent β fraction of their MMS value [Ghodsi et al., 2018; Garg and Taki, 2020]. These approximation techniques are not robust to slight noise in agents' cardinal valuations, i.e., a small perturbation in the valuation of a rather irrelevant item induces a radical change in the final solution. In particular, multiplicative approximations of MMS are extremely sensitive to infinitesimal change in agents' valuations.

We proposed a technique for ordinal approximation of MMS that is robust to slight modifications or noise in valuations. Our work was the first approximation framework on two dimensions, allowing for α fraction of agents to receive β approximation of their fair share value [Hosseini and Searns, 2021; Searns and Hosseini, 2020]. In this vein, we show the existence of allocations that guarantee 2/3 of agents receive their exact MMS value. In addition, we establish a connection between this approximation framework and ordinal approximation of MMS fair share that rely on adding (a small number of) dummy agents to the mix. In fact, we devise algorithms that ensure that each agent receive their MMS value if they were to distribute the goods among ⌊ 3n 2 ⌋ agents [Hosseini et al., 2022b].

Fairness in Dynamic Environments. Real-world applications often deal with complex environments that are inherently dynamic, that is, decisions must be made as new resources emerge over time and the information about future is not available apriori. Thus, it is often impossible to take history or prior decisions into account, and decisions about how (and what) to allocate need to be made when such information is unavailable (or uncertain). These problems are often modeled as online bipartite matching wherein upon arrival of items, preferences of agents are revealed as edges incident to the items, and the algorithmmust irrevocably match the item to such agents. Here, agents may be partitioned into groups, and thus, a fair treatment demands that all groups receive a fair allocation.

In a recent work, we study deterministic and randomized algorithms for allocating indivisible items (leading to integral allocations) and for allocating divisible items (leading to fractional allocations) among such groups. In particular, we design online algorithms that achieve 1/2 approximation of EF1 and MMS, and show that these guarantees are tight. For dealing with divisible items, we design an algorithm that achieves (1 - 1e )-approximation of envy-freeness, and establish a 3/4 upper bound [Hosseini et al., 2023a]. Furthermore, we discuss randomized algorithms to improve the above approximation ratios, and introduce several intriguing open problems.

Of course, allocation problems may involve sequential allocations with dynamic preferences [Hosseini et al., 2015] or dynamic population of agents [Kash et al., 2014; Walsh, 2011]. These settings often require studying randomized algorithms with probabilistic guarantees on fairness (e.g. stochastic dominance envy-freeness) [Hosseini and Larson, 2019; Hosseini et al., 2018].

Degree of Fairness. In some constrained allocation problems, agents are limited to receive only a single resource (e.g. assigning public housing to families). These problems are often known as "Shapley-Scarf Housing Markets" where the goal is often to achieve economic efficiency by resolving mutually-beneficial exchanges among agents with initial endowments [Shapley and Scarf, 1974]. Focusing on fairness, the 'one house per agent' constraint immediately renders previous approximate fairness axioms meaningless: any 'up to one' style axiom or fair-share variants are satisfied vacuously. This motivates the study of fairness metrics that measure the degree of envy among a society of agents (e.g. the aggregate envy of all agents or the number of envious agents). Our recent work has focused on studying the degree of fairness under various measures of economic efficiency (e.g. utilitarian or egalitarian welfare) [Hosseini et al., 2024a]. When the set of agents are placed along the vertices of a social network, we showed theoretical upper bounds on minimizing aggregate envy, and further exploit the graph structures to illuminate the axiomatic and computational boundaries of fairness [Hosseini et al., 2023e; Hosseini et al., 2024c].

Preference Elicitation. It is often challenging, if not impossible, to elicit complete preference information due to uncertainty in the environment, high elicitation cost, or simply cognitive burden on agents to assign exact rankings to each and every one of the items. Instead of asking agents to report their preferences over item (or bundles) at once, it is possible to use a preference elicitation mechanism, in which agents repeatedly respond to queries about their preferences. When agents are constrained to receive only one item, preferences can be elicited through pairwise comparisons or through reporting the k most-preferred alternatives [Aziz et al., 2015; Borodin et al., 2022]. In this vein, our work investigated the query complexity of elicitation mechanisms, and designed algorithms that can achieve competitive social welfare (measured by Pareto optimality or rank maximality). In particular, our online algorithm requires O(√n) queries, with a matching lower bound, which implies that our algorithm is asympotically optimal [Hosseini et al., 2021a].

2.2 Distributing Tasks (andMixtures)

Unlike allocating desirable resources where the more is often preferred, receiving more tasks is never preferred. These problems range from allocating household chores to allocating computational or sampling tasks to servers to train AI models. Interestingly, societal problems that involve collective ownership of responsibility (e.g. limiting gas emissions or managing nuclear waste) at their core involve distribution of negatively valued tasks.

Fair Allocation of Tasks. Distributing tasks is crucially different from allocating goods or resources. While goods are freely disposable, tasks must be completed fully. These fundamental differences along with technical challenges motivates the study of fairness in this domain. For instance, while for positively valued items (goods) an EF1 and PO allocation always exist [Caragiannis et al., 2019] and can be computed in pseudo-polynomial time [Barman et al., 2019], for tasks even the existence of EF1 allocations together with PO remains an open problem.

Our work aims at providing a more fine-grained notion for distributing chores. Under the aforementioned epistemic framework, we introduce 'dubious' tasks to achieve envyfreeness through minimal information asymmetry. In this setting, we prove the existence of envy-free and PO allocations with only 2n - 2 dubious tasks and strengthen it to n - 1 in some special classes of valuations.

Similar to the allocation of resources, one may also take a threshold-based approach such as MMS to distribute tasks. The non-existence and computational intractability once again strike [Aziz et al., 2017], motivating the investigation of approximate fair share. In particular, an agent's ordinal fair share, aka 1-out-of-k MMS, is determined by partitioning the indivisible tasks into k bundles in a counterfactual world where there are fewer agents (k < n) available. We prove the existence of allocations with k ≤ ⌊ 3n 4 ⌋, and develop efficient algorithms to compute such allocations for k ≤ ⌊ 2n 3 ⌋ [Hosseini et al., 2022a].

Goods, Chores, andMixtures. Inmany domains, the preferences over items (or outcomes) may be subjective, i.e., some agents may consider a resource as a good (with nonnegative utility) while others may see the same as a task (with negative utility). For instance, in peer reviewing, reviewers may consider a paper to be a chore if it is outside of their immediate expertise while another subset of reviewers consider it as a good due its proximity to their own field. A goldstandard fairness relaxation is envy-freeness up to any item (EFX) [Caragiannis et al., 2019]. Yet, its existence and computation has remained a notable open problem even when all items are considered to be goods. Focusing on mixtures of goods and chores, we showed, for the first time, that an allocation satisfying EFX could fail to exist [Hosseini et al., 2023f] and its corresponding decision problem is computationally hard [Hosseini et al., 2023c] even under a restricted domain of lexicographic preferences-a subdomain of additive preferences. These results stand in contrast to goodsonly [Hosseini et al., 2021b; Hosseini and Larson, 2019] and chores-only [Hosseini et al., 2023f] settings where efficient algorithms exist that can compute fair (EFX) and efficient (Pareto optimality) allocations under the lexicographic domain of preferences.

Despite the challenges posed in settings with mixture of resources and tasks, we demonstrate that it is possible to identify natural domains where fairness notions (e.g. EFX, MMS, EF1) in conjunction with optimality always exist and can be computed efficiently [Hosseini et al., 2023c]. Interestingly, the results on restricted domains can often, but not always, be lifted up to include more complex preferences. For instance, in a recent work we develop algorithms to compute EFX and MMS allocation of goods under weakly lexicographic preferences; and demonstrate that the problem becomes far more challenging when it comes to distributing tasks when preferences contain ties [Hosseini et al., 2024b].

DistributingTasks onGraphs. When agents, resources, or tasks are located on vertices of a connected graph, often the graph structure plays an instrumental role in the design of fair algorithmic solutions. Fair distribution of tasks or resources among agents that are either connected by a network or need to cover a path on a network is particularly critical with the rise of digital marketplaces (e.g. package delivery tasks). We investigated balancing fairness (e.g. EF1 and MMS) and efficiency (measured by delivery time or distance travelled) and study the price of fairness [Bertsimas et al., 2011; Dickerson et al., 2014] when distributing delivery orders among agents on a network with possibly submodular costs [Hosseini et al., 2023d].

3 Incentives and Strategic Behavior

In many novel application domains (e.g. federated healthcare or data/compute sharing frameworks), decisions heavily rely on eliciting data (e.g. preference information) from the involving parties. Yet, participants may act strategically to exploit the system or influence the outcome to their own benefit, which could drastically hinder the quality of decisions (measured by stability, fairness, and efficiency). In fact, incentivizing truthful behavior (e.g. strategyproofness) stands in contrast with other socially desirable axioms such as fairness and stability in both one-sided and two-sided matching markets [Roth, 1982; Svensson, 1999].

3.1 One-Sided AllocationMechanisms

The interaction between economic efficiency and fairness with truthful incentives has been a subject of extensive studies within economics and computer science. Unfortunately, with a few exceptions, incentivizing truthful reporting stands in contrast with fairness (and efficiency) [Zhou, 1990; Bogomolnaia and Moulin, 2004]. When agents are restricted to receive a single item, randomized mechanisms can sometimes strike a balance between truthfulness (aka strategy-proofness) and weaker axioms of ex ante fairness [Abdulkadiro˘glu and Sönmez, 1998; Hosseini et al., 2018].

It turns out that when allocating multiple resources or tasks, no truthful mechanism can guarantee any 'up to one' style fairness axiom ex post even for two agents [Amanatidis et al., 2017]. These impossibility results raise the question of whether truthfulness and fairness remain incompatible under some natural restrictions. For binary valuations, truthfulness is compatible with fairness and economic efficiency [Halpern et al., 2020], which as we show extends to lexicographic preferences. In fact, we characterize such mechanisms and develop algorithms that satisfy the stronger fairness axiom of envy-freeness up to any item (EFX) [Hosseini et al., 2021b].

3.2 Two-Sided AllocationMechanisms

One of the most prominent application domains involves allocation markets that are inherently two-sided, i.e., two disjoint sets have preferences over the alternatives on the opposite side with some capacity constraints: drivers are matched with one or few riders according to both preferences; freelancers may prefer certain tasks while job requesters prefer higherrated freelancers. Here, the stability of an allocation relies on an individual fairness notion known as justified envy-freeness, i.e., any envy towards another agent should be justified by the preferences of the matched partner.

In these settings-similar to their one-sided counterpartsno mechanism can simultaneously satisfy individual fairness while incentivizing truthful behavior of agents [Roth, 1982] (see our recent survey on strategic manipulation in these markets [Hosseini and Pathak, 2024]). Thus, the strategic behavior (by single or coalition of agents) plays a key role on the fairness of the resulting outcome. In a series of work, we proposed a novel framework for "two-sided" manipulations where a misreporting agent (aka the accomplice) and the manipulator (or the beneficiary) are on different sides of the market. We characterized optimal and sub-optimal manipulation strategies when agents can employ one or a coalition of accomplices to strategically change the outcome of the celebrated Deferred Acceptance algorithm (DA) [Gale and Shapley, 1962]. These characterizations immediately imply polynomial-time algorithms for computing an optimal strategy for coalitions of size two [Hosseini et al., 2021c; Bendline and Hosseini, 2019], and give rise to strategies that benefit all agents of one side [Hosseini et al., 2022c]. A rather surprising consequence is that an optimal strategy preserves fairness (i.e. justified envy-freeness), while strategies that involve misreporting agents on both sides may no longer guarantee fairness, and thus, result in unstable allocations.

4 Alignment with Human Values

Due to the simplistic nature of fairness axioms (and their approximate counterparts), they often fail to capture the intricacies of the human perception of fairness in complex realworld problems. It is not yet clear how the algorithmic outcomes driven by these axioms are perceived by individuals and the society. A human-centered approach to fairness calls for establishing a 'hierarchy of fairness axioms' and designing algorithmic solutions that are aligned with human and societal values, among several other natural criteria such as explainability [Hosseini, 2024].

In a recent work, we conducted a series of studies with human subjects, to investigate how individuals perceive two conceptually different relaxations of envy-freeness. In particular, our results demonstrated that an epistemic relaxation (as discussed in Section 2) that is based on information asymmetry [Hosseini et al., 2020] is perceived to be fairer compared to other approximations (e.g. EF1) that are rooted in counterfactual reasoning [Hosseini et al., 2023b]. These results demonstrate the influence of human cognition, societal values, and individual biases in human judgments, and further call for axioms based on 'distributional preferences' [Herreiner and Puppe, 2009] that are aligned with human values.

5 Concluding Remarks

Algorithmic fairness is fundamental in a variety of application domains that involve distribution of resources, tasks, or mixtures thereof. It demands the cross-fertilization of ideas between AI, computation, and economics to establish the foundation of socially-responsible collective decisionmaking. The grand vision is promoting fairness principles in (re)designing new AI and algorithmic systems that are provably fair and are aligned with human and societal values; one that can be suited for any complex domain involving a variety of diverse and often conflicting preferences.

Fulfilling this vision involves overcoming numerous milestones throughout this exciting journey. For example, with algorithmic solutions we need to take into account how individuals interact with algorithms, and whether outcomes (or procedures) are explainable. En route to achieving these goals, we additionally need platforms that facilitate human interactions with allocating algorithms [Ferris and Hosseini, 2020; Bao and Hosseini, 2023] and systems that provide explainable recommendations to users, planners, and the society at large [Suryanarayana et al., 2022].

Acknowledgments

I am grateful to all my mentors for their unwavering support. I am thankful to the students in my group (FAIR Lab) and my amazing collaborators who have been vital part of this research journey. The reported research has been generously supported by NSF Awards IIS-2052488 and IIS-2107173, and an NSF Early Career Award IIS-2144413.