In this paper, we discuss the application of abstract argumentation mechanisms to resources allocation. We show how such problems can be modeled as abstract argumentation frameworks, such that speci c sets of arguments corresponds to interesting solutions of the problem. By interesting solutions, here we mean Local Envy-Free (LEF) allocations. Envy-freeness is an important notion of fairness in resources allocation, assuming than no agent should prefer the resource allocated to another agent. We focus on LEF, a generalized form of envy-freeness, and we show that LEF allocations corresponds to some speci c sets of arguments in our argument-based modeling of the problem. This work in progress paves the way to richer connections between the various models of argumentation and resources allocation problems.
Fairness issues are important in multi-agent scenarios, including resources allocation. Among
the various fairness criteria, one of them is envy-freeness, i.e. the fact that no agent is envious of
another agent. A generalized version of envy-freeness is local envy-freeness (LEF) [
Section 2 provides some background notions on LEF allocations and abstract argumentation. Section 3 discusses our transformation from resources allocation problems to abstract argumentation, and shows the relation between LEF allocations and speci c extensions. Finally Section 4 concludes the paper by discussing some interesting questions for future work.
We focus on a resource allocation scenario (previously studied in [
preferences of agent i over O, • G = N, E is an undirected graph representing the social network of agents. i is a linear order expressing the
We are interested in the problem of local envy-freeness, i.e. whether we can assign each agent i an object ok s.t. i does not prefer the object assigned to one of her neighbors, formally j N s.t. {i, j} E, ol i ok, where ok and ol are (respectively) the object assigned to i and the object assigned to j.
To characterize formally this concept, we represent an allocation as a set of pairs (i, ok) N O. Given such a pair x = (i, ok), we use Ag(x) and Obj(x) to denote respectively the agent i and the object ok of this pair. An allocation is valid if for each x, y , if x = y then Ag(x) = Ag(y) and Obj(x) = Obj(y), i.e. no agent receives several objects, and no object is assigned to several agents. A valid allocation can be partial if | | < |O|, and total if | | = |O| = |N |.
De nition 2. Given P RAP = total valid allocation such that i, j
N s.t. {i, j} E, if (i, ok), (j, ol) then ol i ok.
Example 1. Figure 1a describes P RAP = O, N , , G where the agents are N = {A, B, C}, the objects are O = {1, 2, 3} with 1 representing some money, 2 a motorbike, and 3 a car. The social network G is shown at the top of the Figure, and the agents preferences are given underneath. We can easily nd a LEF allocation by giving each agent her preferred object.
Now consider P RAP 2 given at Figure 1b, where this time all the agents know each other, and agent C’s preferences are slightly modi ed as well. Assume there is a LEF allocation . Neither A nor C can receive the object 1 (because otherwise the one receiving another object would be envious of the one receving the object 1). Thus we must have (B, 1) . But in this case, both agents A and C are envious of agent B. So there is no LEF allocation for P RAP 2. A : B : C : 1 2 3 > > > (a) PRAP1 2 3 2 > > > 3 1 1
A : B : C : 1 2 1 > > > (b) PRAP2 2 3 3 > > > 3 1 2
Now let us recall basic notions of Dung’s abstract argumentation [
De nition 3. An abstract argumentation framework (AF) is a directed graph F = A is the set of arguments and R A is the attack relation.
A
Classical reasoning with AF uses the notion of extensions, i.e. sets of arguments that can be jointly accepted. Various semantics have been proposed to obtain the set of extensions of an AF. Formally, an extension-based semantics is a function such that for any AF F = A, R , (F ) 2A. In this paper, we only need the notions of con ict-free sets and stable extensions: where A, R De nition 4. Given F = A, R , S A is con ict-free (S cf(F )) if a, b S, (a, b) .R Then, S is a stable extension (S stb(F )) if S cf(F ) and b A \ S, a S s.t. (a, b) R.
Among the various generalizations of Dung’s argumentation framework, we are interested
in preference-based AFs (PAFs) [
De nition 5. A preference-based argumentation framework is a tuple P = A, R,
A
The preference relation is only assumed to be a pre-order, i.e. a re exive and transitive binary relation. The main approach for reasoning with a PAF consists in reducing it into a standard AF by combining the attacks and the preferences into a defeat relation. Then, the extensions of the PAF for a semantics are the extensions of the defeat graph under the same semantics. where De nition 6. Given a PAF P = x}. Then, (P ) = ( A, D ).
A, R, , we de ne the defeat relation D = {(x, y) R | y
In this section we show how to transform a PRAP into a PAF, such that there is a correspondence between LEF allocations and some sets of arguments, namely con ict-free sets of size |N |, which are guaranteed to be stable extensions as well in our case. De nition 7. Given P RAP =
O, N , , G , we de ne the PAF PLEF =
A, R, with • A = {(i, oj ) | i • R = R1 R2
N, oj
allocation of an object to an agent), – R1 = {((i, oj ), (i, ok)) | i – R2 = {((i, ok), (j, ok)) | i, j – R3 = {((i, ok), (j, ol)) | i, j N, oj , ok
N, ok N, ok, ol
O, {i, j} E and ol i ok} (envy), • = {((i, ok), (i, oj )) | i
N, ok
i oj } (preferences).
Obviously, any allocation corresponds to a set of arguments in A. Observe also that the defeat relation will only remove some of the attacks in R1, namely, for each pair of arguments x = (i, oj ) and y = (i, ok), the defeat relation will contain the defeat (x, y) if oj i ok, and the defeat (y, x) if ok i oj . The other attack relations R2 and R3 are not impacted by the preferences, so they are included in the defeat relation of this PAF.
Example 2. Let us consider again P RAP 1 from Example 1. Figure 2 gives the defeat relation of the corresponding PAF PLEF. More precisely, Figure 2a gives the combination of R1 with the preferences, Figure 2b (resp. 2c) shows R2 (resp. R3). In Figure 2c, the red arrows correspond to the situations where agent A is envious (for instance, because she has received the object 2 while B has received the object 1), blue arrows are for agent B, and green arrows correspond to agent C. (A, 1) (B, 1) (C, 1) (A, 1) (B, 1) (C, 1) (A, 1) (B, 1) (C, 1) (A, 2) (B, 2) (C, 2) (A, 2) (B, 2) (C, 2) (A, 2) (B, 2)
(C, 2) (B, 3) (b) R2 (A, 3) (B, 3) (C, 3) (A, 3) (C, 3) (A, 3) (C, 3) (a) R1 +
The following lemmas will help us to prove the correspondance between LEF allocations and con ict-free sets (and stable extensions) of size |N |.
Lemma 1. Given an allocation , if cf(PLEF) then is valid.
Proof. Assume is not valid. If x, y s.t. Ag(x) = Ag(y), then (x, y), (y, x) R1, which implies that either (x, y) or (y, x) is in the defeat relation of PLEF, so cf(FLEF). Similarly, if x, y s.t. Obj(x) = Obj(y), then (x, y) R2, which implies cf(PLEF). Lemma 2. Given a valid allocation , if cf(PLEF) then is not LEF.
(B, 3) (c) R3 Proof. Assume a valid allocation which is not con ict-free in PLEF. By construction, since is valid, there are no x, y such that (x, y) R1 or (x, y) R2, so we deduce that x, y such that (x, y) R3 which implies that is not LEF.
Proposition 1. Let be an allocation. is LEF i cf(PLEF) and | | = |N |.
Proof. First assume that is a LEF allocation. From Lemma 2 we deduce that is con ict-free. By de nition, since is LEF then is total. Hence the rst part of the result.
Now assume that cf(PLEF) and | | = |N |. From Lemma 1, we know that is valid. Then, since cf(PLEF), we can guarantee that there are no x, y such that (x, y) R3. This means that, for any i N such that (i, ok) , there is no j N such that (j, ol) , {i, j} E and ol i ok. By de nition, this means that is LEF.
Proposition 1 implies that LEF allocations can be easily computed thanks to a minor modi
cation of a very classical approach for solving argumentation problems. Most of the e cient
approaches for reasoning with abstract argumentation frameworks use SAT solvers. For the
basic notion of con ict-freeness, it is enough to consider clauses which forbid to accept together
arguments which are connected by an attack. We will use a MaxSAT version of this encoding [
D} sc = {(x, 1) | x
A}
Given the sets of clauses hc and sc, a MaxSAT solver returns a con ict-free set of PLEF of
maximal cardinality. If this solution has a cardinality equal to |N |, then it is a LEF allocation.
Otherwise, there is no LEF allocation. Another possible approach consists in adding one
cardinality constraint [
Notice that such an allocation also corresponds to a stable extension of cardinality |N |. Corollary 1. Let be an allocation. is LEF i stb(PLEF) and | | = |N |.
Proof. One side of the equivalence is obvious: if stb(PLEF), then cf(PLEF), so under the assumption that | | = |N |, the result follows Proposition 1.
Now, assume that is a LEF allocation. From Proposition 1, we know that cf(PLEF) and | | = |N |. For a given object ok, there is an argument a = (i, ok) , i.e. the object ok has been assigned to agent i. By de nition of R2, a defeats all the arguments of the form (j, ok) for j = i. Since this is true for all the objects, any argument not in is defeated by some argument in , so stb(PLEF).
Argumentation has already shown its interest for providing explanations to other problems, like
e.g. scheduling [
The preliminary study of this connection allows us to envision deeper relations between
both frameworks. For instance, it seems possible to assign numerical values to assignments
(e.g. the preferred object ok of agent i receives the value n, her second preferred object receives
n 1, etc.) in order to de ne a Strength-based Argumentation Framework (StrAF) [
We are also interested in the methods allowing the explanation of arguments status in abstract
argumentation (e.g. [
Another interesting way to go further in the study of argumentation applied to resources
allocation consists in using the con ict-tolerant semantics of Weighted Argumentation
Frameworks (WAFs) [
These few ideas are only a small part of the possible connections between resources allocation and computational argumentation, and pave the way to a rich body of work that will allow to provide explainable solutions to fairness issues in resources allocation problem.
This work bene ted from the support of the project AGGREEY ANR-22-CE23-0005 of the French National Research Agency (ANR).