Introduction

Multi-Agent Systems (MAS) consist of agents interacting with each other and their surrounding environment to achieve their individual or shared goals. The achievement of an agent's goals may depend on the actions it takes, the actions of other agents, the environment they are situated in, and the rules that govern the MAS. Similarly, fairness in MAS depends on multiple factors. Fairness can be influenced by agents' decision-making processes, as evidenced by research in reinforcement learning focused on developing fair and efficient policies [1]. It can also hinge on mechanism design, as seen in scenarios like goods allocation games [2] or cake-cutting problems [3], where rules can ensure fair reward distribution among agents. Additionally, fairness can be affected by things like an agent's utility [4,5] or their priority in accessing resources [6,7], among others.

In human societies, fairness is often defined in terms of characteristics that should not disadvantage an individual or group, such as age, race, disability or gender. For example, in the UK Equality Act 2010 1 these are identified as protected characteristics, and UK law states that individuals cannot be discriminated against on the basis of these. These protected characteristics typically define subgroups of the population who have historically been disadvantaged in particular situations, such as age discrimination in the workplace, unequal access to healthcare or barriers in education for people with disabilities and gender disparities in political representation, among others. Driven by the bias that often exists in the training data as a result of these systemic inequalities, machine learning approaches often produce biased results (e.g., discrimination in credit market [8] or justice [9,10] algorithms); there is a growing body of work (often referred to as algorithmic fairness) that aims to identify and mitigate such bias by applying a range of fairness metrics that compare the outcomes achieved by what is identified as advantaged and disadvantaged subgroups of the population (see, e.g., [11,12] for a review).

Taking inspiration from the UK Equality Act 2010, we define the concept of protected attributes within a multi-agent system, which are any attributes that have been deemed should not disadvantage an agent in terms of its performance within that system. For example, consider a multi-agent setting that includes both artificial agents in the form of autonomous vehicles and human agents who drive their own cars; we may want to ensure that the human agents are not disadvantaged in such a setting. We adapt the following fairness metrics from the algorithmic fairness literature to our multi-agent setting.

• Demographic parity -Agents with and without protected attributes should obtain the same expected rewards. • Counterfactual fairness -In both a factual and a counterfactual scenario, where the only difference is whether the protected attributes hold for an agent, agents should obtain the same expected rewards. • Conditional statistical parity -Within a group of agents characterised by a legitimate factor influencing rewards, agents with and without protected attributes should obtain the same expected rewards.

We are able to evaluate different MAS according to these metrics, with the ultimate aim of designing fairer MAS (for example, by configuring the environment in which agents operate to optimise for fairness). Such an approach is inspired by other works outside MAS, such as designing accessible buildings [13] or safe urban environments [14]. Further studies explore environment configurations to optimise rescue operations and autonomous vehicle planning [15,16]. However, none of them deal with fairness. Hence, we hope this research can offer valuable insights into domains beyond MAS.

To summarise, the contributions of this paper are as follows. We introduce protected attributes to MAS -characteristics that should not impact an agent's expected rewards, all other things being equal. We adapt the concepts of demographic parity, counterfactual fairness and conditional statistical parity from the algorithmic fairness literature to the MAS context. The future aim of this work is to use these metrics to evaluate and optimise MAS for fairness.

Motivating example.

In future urban environments, we may see vehicles operated by humans and vehicles operated by AI undertaking journeys within the same road network. These human and AI agents navigate city streets to reach their destinations, with the rewards they receive dependent on things like time taken and cost of journey. AI-driven vehicles excel by analysing traffic data in real-time, optimising routes, and communicating with other AI vehicles, providing them with an advantage over the human agents in the system, who are generally less efficient at route optimisation and less well-equipped to coordinate with other road users. To mitigate this advantage of AI agents, we might consider altering the road infrastructure, for example, by providing dedicated lanes for human-controlled vehicles.

Related work

Fairness has attracted the attention of Game Theory and MAS researchers for decades alongside psychologists and economists [17,18,19,20]. Factors such as the rules that govern the system can influence fairness in MAS. For instance, this can be seen in the Ultimatum Game, where fairness is influenced by the dynamics between proposers and responders [21,22,23]. In goods allocation or cake-cutting games, the rules depend on the type of good being allocated, for example, whether they are divisible or indivisible, goods or chores [24,25], and fairness depends on the distribution of goods among the agents [2,3,7,26,27].

Agent behaviour can also influence fairness. Fair behaviours often balance the rewards collected by the community and individuals. For example, Zhang and Shah [28] propose a minimum reward for the worst-performing agent while improving the overall rewards of the whole community of agents. However, fairness and reward optimisation can be in tension, and compromises must be made regarding one of the two sides. Jiang and Lu [29] propose a two-step solution consisting of a single policy for each agent based on fair and optimal rewards, with a controller agent who decides which sub-policies to implement to maximise environmental rewards and fairness. Other works [30,31,32] implement fair optimisation policies within cooperative multi-agent systems, aiming to integrate individualistic and altruistic behaviours. Grupen et al. [33] introduce a new measure of team fairness, demonstrating how maximising team rewards in cooperative MAS can lead to unfair outcomes for individual agents.

In contrast to these works, which do not distinguish agents that may be particularly disadvantaged within a system, we consider fairness across agents who do or do not possess protected attributes. We adapt demographic parity [34,35], counterfactual fairness [35] and conditional statistical parity [36] fairness metrics from the algorithmic fairness literature to the MAS setting.

Preliminaries

A multi-agent system consists of multiple decision-making agents who act and interact in an environment to achieve their goals. A multi-agent system S = (𝐸, 𝑒 𝑜 , 𝐴𝑐, 𝑃, 𝐴𝑡, 𝐴𝑡 𝑝𝑟 , 𝜏 ) is characterised by: the set of possible environment states 𝐸; the starting state 𝑒 0 ; the set of available actions that may be performed by an agent in the environment 𝐴𝑐 (including a null action); a population 𝑃 = {𝑎 1 , . . . , 𝑎 𝑛 } of agents; the attributes 𝐴𝑡 = {𝑎𝑡 1 , . . . , 𝑎𝑡 𝑚 } available to the agents in 𝑃 ; the protected attributes 𝐴𝑡 𝑝𝑟 ⊂ {𝑎𝑡 1 , . . . , 𝑎𝑡 𝑚 }; and the non-deterministic state transformer function 𝜏 : 𝐸 × 𝐴𝑐 1 × . . . × 𝐴𝑐 𝑛 → 𝐸 × [0, 1] that specifies the probability distribution over the possible resulting states that can occur when each agent in the population performs an action (where the possible null action reflects that an agent chooses not to act).

An agent 𝑎 𝑥 within a multi-agent system (𝐸, 𝑒 𝑜 , 𝐴𝑐, 𝑃, 𝐴𝑡, 𝐴𝑡 𝑝𝑟 , 𝜏 ) (where 𝑎 𝑥 ∈ 𝑃 ) is defined as a tuple (𝐴𝑡 𝑥 , 𝐴𝑐 𝑥 , 𝜋 𝑥 , 𝜌 𝑥 ) where: the attribute evaluation function 𝐴𝑡 𝑥 : 𝐴𝑡 → {0, 1} specifies which attributes hold true for the agent; 𝐴𝑐 𝑥 ⊆ 𝐴𝑐 are the actions available to the agent; the non-deterministic policy 𝜋 𝑥 : 𝐸 → 𝐴𝑐 𝑥 × [0, 1] specifies how an agent will act in any given state (represented as a probability distribution over the possible actions); and the reward function 𝜌 𝑥 : 𝐸 × 𝐸 → R specifies the reward the agent receives for moving between two states.

A possible run within a multi-agent system S = (𝐸, 𝑒 𝑜 , 𝐴𝑐, 𝑃, 𝐴𝑡, 𝐴𝑡 𝑝𝑟 , 𝜏 ) (where 𝑃 consists of 𝑛 agents) is denoted 𝑟 = (𝑒 0 , (𝑎𝑐 1 1 , . . . , 𝑎𝑐 𝑛 1 ), 𝑒 1 , . . . , (𝑎𝑐 1 𝑗 , . . . , 𝑎𝑐 𝑛 𝑗 ), 𝑒 𝑗 ) where: for each 𝑎 𝑥 ∈ 𝑃 and for each 𝑖 such that 0 < 𝑖 ≤ 𝑗, (𝑎𝑐 𝑥 𝑖 , 𝑝) ∈ 𝜋 𝑥 (𝑒 𝑖−1 ) and 𝑝 > 0; and for each 𝑖 such that 0 ≤ 𝑖 < 𝑗, (𝑒 𝑖+1 , 𝑝) ∈ 𝜏 (𝑒 𝑖 , (𝑎𝑐 1 𝑖 , . . . , 𝑎𝑐 𝑛 𝑖 )) and 𝑝 > 0. The set of all possible runs within a multi-agent system S is denoted ℛ S .

Let 𝑟 = (𝑒 0 , (𝑎𝑐 1 1 , . . . , 𝑎𝑐 𝑛 1 ), 𝑒 1 , . . . , (𝑎𝑐 1 𝑗 , . . . , 𝑎𝑐 𝑛 𝑗 ), 𝑒 𝑗 ) ∈ ℛ S where S = (𝐸, 𝑒 𝑜 , 𝐴𝑐, 𝑃, 𝐴𝑡, 𝐴𝑡 𝑝𝑟 , 𝜏 ). We can determine the probability 𝑟 will occur, denoted 𝑝(𝑟 | S ), as follows.

𝑝(𝑟| S ) = (︃ 𝑗−1 ∏︁ 𝑖=0 (︃ 𝑛 ∏︁ 𝑥=1 𝑝 𝑥 where (𝑎𝑐 𝑥 𝑖+1 , 𝑝 𝑥 ) ∈ 𝜋 𝑥 (𝑒 𝑖 ) )︃)︃ • (︃ 𝑗−1 ∏︁ 𝑖=0 𝑝 𝑖 where (𝑒 𝑖+1 , 𝑝 𝑖 ) ∈ 𝜏 (𝑒 𝑖 , (𝑎𝑐 1 𝑖+1 , . . . , 𝑎𝑐 𝑛 𝑖+1 ))

)︃

For a run 𝑟 = (𝑒 0 , (𝑎𝑐

𝑅𝑒𝑤(𝑎 𝑥 , 𝑟).𝑝(𝑟 | S ).

Motivating example, continued. The city traffic consists of a population of cars, each capable of steering, accelerating or braking. Cars also possess attributes like speed or safety features. Cars are either driven by AI or humans, and we consider being driven by humans to be a protected attribute of cars. AI-driven cars can find optimal paths to reach their destination more efficiently than human-driven ones. If we consider agents reaching a hospital, we can foresee fairness problems as AI-driven cars would be advantaged. When the cars act with a specific probability, the environment changes state. Also, each car obtains a reward when reaching its destination. A car's policy is a decision rule based on the state of the crossroads.

Fairness in MAS

We define fairness by comparing, in different ways, the rewards gathered by individuals or groups of agents possessing and not possessing protected attributes. We adapt demographic parity [34,35], counterfactual fairness [35] and conditional statistical parity [36] to MAS. Demographic parity in MAS is achieved when the expected rewards of agents are not influenced by whether or not they possess protected attributes, all else being equal.

Definition 1 (Demographic Parity). Let S = (𝐸, 𝑒 𝑜 , 𝐴𝑐, 𝑃, 𝐴𝑡, 𝐴𝑡 𝑝𝑟 , 𝜏 ) be a system and let 𝑎𝑡 𝑝𝑟 ∈ 𝐴𝑡 𝑝𝑟 be the protected attribute under consideration. Demographic parity is satisfied for 𝑎𝑡 𝑝𝑟 in S if and only if: for all 𝑎 𝑥 , 𝑎 𝑦 ∈ 𝑃 , if 𝐴𝑡 𝑥 (𝑎𝑡 𝑝𝑟 ) = 1, 𝐴𝑡 𝑦 (𝑎𝑡 𝑝𝑟 ) = 0, and for all 𝑎𝑡 ′ ∈ 𝐴𝑡∖{𝑎𝑡 𝑝𝑟 }, 𝐴𝑡 𝑥 (𝑎𝑡 ′ ) = 𝐴𝑡 𝑦 (𝑎𝑡 ′ ), then 𝐸𝑥𝑝𝑅𝑒𝑤(𝑎 𝑥 , S ) = 𝐸𝑥𝑝𝑅𝑒𝑤(𝑎 𝑦 , S ).

Where demographic parity is not satisfied for a particular protected attribute, we can measure the extent to which this is the case, denoted 𝐷𝑒𝑚𝑃 𝑎𝑟(𝑎𝑡 𝑝𝑟 , S ), as follows.

𝐷𝑒𝑚𝑃 𝑎𝑟(𝑎𝑡 𝑝𝑟 , S ) = ∑︁

𝑎𝑥,𝑎𝑦∈𝑃 such that 𝐴𝑡𝑥(𝑎𝑡 𝑝𝑟 )=1, 𝐴𝑡𝑦(𝑎𝑡 𝑝𝑟 )=0, and for all 𝑎𝑡 ′ ∈𝐴𝑡∖{𝑎𝑡 𝑝𝑟 },𝐴𝑡𝑥(𝑎𝑡 ′ )=𝐴𝑡𝑦(𝑎𝑡 ′ ) 𝐸𝑥𝑝𝑅𝑒𝑤(𝑎 𝑥 , S ) − 𝐸𝑥𝑝𝑅𝑒𝑤(𝑎 𝑦 , S )

(1) Note that if demographic parity holds for 𝑎𝑡 𝑝𝑟 in S then 𝐷𝑒𝑚𝑃 𝑎𝑟(𝑎𝑡 𝑝𝑟 , S ) = 0.

Counterfactual fairness in MAS is achieved when the expected rewards of agents remain the same in both a factual and a counterfactual world, where in the latter, we change the protected attribute of the agents while keeping all other elements the same.

Definition 2 (Counterfactual Fairness).

Let S = (𝐸, 𝑒 𝑜 , 𝐴𝑐, 𝑃, 𝐴𝑡, 𝐴𝑡 𝑝𝑟 , 𝜏 ) be a system where 𝑃 = {(𝐴𝑡 1 , 𝐴𝑐 1 , 𝜋 1 , 𝜌 1 ), . . . , (𝐴𝑡 𝑛 , 𝐴𝑐 𝑛 , 𝜋 𝑛 , 𝜌 𝑛 )}, and let 𝑎𝑡 𝑝𝑟 ∈ 𝐴𝑡 𝑝𝑟 be the protected attribute under consideration. Let S ′ = (𝐸, 𝑒 𝑜 , 𝐴𝑐, 𝑃 ′ , 𝐴𝑡, 𝐴𝑡 𝑝𝑟 , 𝜏 ) be the counterfactual of S such that 𝑃 ′ = {(𝐴𝑡 ′ 1 , 𝐴𝑐 1 , 𝜋 1 , 𝜌 1 ), . . . , (𝐴𝑡 ′ 𝑛 , 𝐴𝑐 𝑛 , 𝜋 𝑛 , 𝜌 𝑛 )} where for all 𝑖 such that 1 ≤ 𝑖 ≤ 𝑛: if 𝐴𝑡 𝑖 (𝑎𝑡 𝑝𝑟 ) = 0, then 𝐴𝑡 ′ 𝑖 (𝑎𝑡 𝑝𝑟 ) = 1; if 𝐴𝑡 𝑖 (𝑎𝑡 𝑝𝑟 ) = 1, then 𝐴𝑡 ′ 𝑖 (𝑎𝑡 𝑝𝑟 ) = 0; and for all 𝑎𝑡 ∈ 𝐴𝑡 ∖ {𝑎𝑡 𝑝𝑟 }, 𝐴𝑡 𝑖 (𝑎𝑡) = 𝐴𝑡 𝑎 𝑖 𝑝𝑟𝑖𝑚𝑒(𝑎𝑡). Counterfactual fairness is satisfied for 𝑎𝑡 𝑝𝑟 in S if and only if: for all 𝑎 𝑥 = (𝐴𝑡 𝑥 , 𝐴𝑐 𝑥 , 𝜋 𝑥 , 𝜌 𝑥 ) ∈ 𝑃 , for all 𝑎 ′ 𝑥 = (𝐴𝑡 ′ 𝑥 , 𝐴𝑐 𝑥 , 𝜋 𝑥 , 𝜌 𝑥 ) ∈ 𝑃 ′ , 𝐸𝑥𝑝𝑅𝑒𝑤(𝑎 𝑥 , S ) = 𝐸𝑥𝑝𝑅𝑒𝑤(𝑎 ′ 𝑥 , S ′ ). Where counterfactual fairness is not satisfied, we can measure the extent to which this is the case, denoted 𝐶𝑜𝑢𝑛𝑡𝐹 𝑎𝑖𝑟(𝑎𝑡 𝑝𝑟 , S ), as follows.

𝐶𝑜𝑢𝑛𝑡𝐹 𝑎𝑖𝑟(𝑎𝑡 𝑝𝑟 , S ) = ∑︁ 𝑎𝑥∈𝑃 such that 𝐴𝑡𝑥(𝑎𝑡 𝑝𝑟 )=1 𝐸𝑥𝑝𝑅𝑒𝑤(𝑎 𝑥 , S ) − 𝐸𝑥𝑝𝑅𝑒𝑤(𝑎 ′ 𝑥 , S ′ )(2)

Note that if counterfactual fairness holds for 𝑎𝑡 𝑝𝑟 in S then 𝐶𝑜𝑢𝑛𝑡𝐹 𝑎𝑖𝑟(𝑎𝑡 𝑝𝑟 , S ) = 0.

Conditional statistical parity in MAS is achieved when the expected rewards of agents are not influenced by whether or not they possess protected attributes when conditioning on a legitimate factor, assuming all other elements are the same. A legitimate factor is an attribute that has been identified as one that may legitimately affect an agent's reward.

Definition 3 (Conditional Statistical Parity).

Let S = (𝐸, 𝑒 𝑜 , 𝐴𝑐, 𝑃, 𝐴𝑡, 𝐴𝑡 𝑝𝑟 , 𝜏 ) be a system, let 𝐿𝐹 ⊆ (𝐴𝑡 ∖ 𝐴𝑡 𝑝𝑟 ) be the set of legitimate factors, and let 𝑎𝑡 𝑝𝑟 ∈ 𝐴𝑡 𝑝𝑟 be the protected attribute under consideration. Conditional statistical parity is satisfied for 𝑎𝑡 𝑝𝑟 with 𝐿𝐹 in S if and only if: for all 𝑎 𝑥 , 𝑎 𝑦 ∈ 𝑃 , if 𝐴𝑡 𝑥 (𝑎𝑡 𝑝𝑟 ) = 1, 𝐴𝑡 𝑦 (𝑎𝑡 𝑝𝑟 ) = 0, 𝐴𝑡 𝑥 (𝑎𝑡 𝑙𝑓 ) = 𝐴𝑡 𝑦 (𝑎𝑡 𝑙𝑓 ) = 1 for all 𝑎𝑡 𝑙𝑓 ∈ 𝐿𝐹 , and for all 𝑎𝑡 ′ ∈ 𝐴𝑡 ∖ {𝑎𝑡 𝑝𝑟 }, 𝐴𝑡 𝑥 (𝑎𝑡 ′ ) = 𝐴𝑡 𝑦 (𝑎𝑡 ′ ), then 𝐸𝑥𝑝𝑅𝑒𝑤(𝑎 𝑥 , S ) = 𝐸𝑥𝑝𝑅𝑒𝑤(𝑎 𝑦 , S ).

Where conditional statistical parity is not satisfied, we can measure the extent to which this is the case, denoted 𝐶𝑜𝑛𝑑𝑆𝑃 (𝑎𝑡 𝑝𝑟 , 𝐿𝐹, S ), as follows.

𝐶𝑜𝑛𝑑𝑆𝑃 (𝑎𝑡 𝑝𝑟 , 𝐿𝐹, S ) = ∑︁ 𝑎𝑥,𝑎𝑦∈𝑃 such that 𝐴𝑡𝑥(𝑎𝑡 𝑝𝑟 )=1, 𝐴𝑡𝑦(𝑎𝑡 𝑝𝑟 )=0, 𝐴𝑡𝑥(𝑎𝑡 𝑙𝑓 )=𝐴𝑡𝑦(𝑎𝑡 𝑙𝑓 )=1 for all 𝑎𝑡 𝑙𝑓 ∈𝐿𝐹, and for all 𝑎𝑡 ′ ∈𝐴𝑡∖{𝑎𝑡 𝑝𝑟 }, 𝐴𝑡𝑥(𝑎𝑡 ′ )=𝐴𝑡𝑦(𝑎𝑡 ′ ) 𝐸𝑥𝑝𝑅𝑒𝑤(𝑎 𝑥 , S ) − 𝐸𝑥𝑝𝑅𝑒𝑤(𝑎 𝑦 , S )

(3) Note that if conditional statistical parity holds for 𝑎𝑡 𝑝𝑟 with 𝐿𝐹 in S then 𝐶𝑜𝑛𝑑𝑆𝑃 (𝑎𝑡 𝑝𝑟 , 𝐿𝐹, S ) = 0.

Conditional statistical parity is demographic parity within subsets of the population characterised by legitimate factors. For example, in algorithmic fairness, such a metric is used to verify whether the probability of predicting re-offence for male and female prisoners is the same for similar age groups, which is the legitimate factor [37].

Motivating example, continued. In the city traffic example, demographic parity would be achieved if the sum of the expected rewards obtained by AI-driven cars and human-driven cars were equal, all other things being equal. In other words, the protected attribute should not affect the expected rewards gathered by the human-driven cars compared to the AI-driven ones. Counterfactual fairness is achieved if the sum of the expected rewards of the cars remains the same in both a factual and a counterfactual world, where in the latter, agents possess the protected attribute (i.e., cars are driven by humans) while keeping all other factors constant. Conditional statistical parity is achieved if the sum of the cars' expected rewards is not influenced by whether or not they possess protected attributes when conditioned on a legitimate factor, e.g., a certain range of speed capacity of the cars, assuming all other elements are the same.

We can use the metrics above to measure fairness of different systems. Our ultimate goal is to optimise systems for these different fairness measures, for example by adjusting the starting state of the environment, or the way the environment responds to the agents' actions.

Conclusion and future work

This paper is a first step towards ensuring that certain sub-groups of agents are not disadvantaged in multi-agent systems. We identify protected attributes, which are characteristics that should not disadvantage an agent in terms of its expected rewards. Inspired by algorithmic fairness, we adapt demographic parity, counterfactual fairness and conditional statistical parity to analyse fairness in MAS. Our metrics assess fairness from various perspectives in any multi-agent system where expected rewards are applicable. Additional metrics from the algorithmic fairness literature, such as equal opportunity, equalised odds [38], disparate impact [39], or other metrics based on causal reasoning [40,41] could be adapted to this setting to capture other aspects of fairness. Our methodology applies to MAS, involving both human and AI agents, as motivated by our example. It could also be used to improve the fairness of human societies by modelling these as multi-agent systems and seeing how changes to the system affect the various fairness metrics defined here.

In future work, we plan to analyse these fairness metrics experimentally in different settings, both competitive and cooperative, to find system configurations that enhance fairness. We will use techniques such as Bayesian optimisation [42], evolutionary algorithms [43] and sparse sampling techniques [44] to try to identify system configurations that optimise for the different fairness metrics.