Abstract argumentation and (optimal) stable marriage problems

Abstract

In his pioneering work on Abstract Argumentation, P.M. Dung set a wide scenario by connecting stable models in Logic and Game Theory to simple Abstract Argumentation Frameworks (AAF), which are essentially directed graphs in which arguments are represented as nodes, and the attack relation is represented by arrows. From such abstraction and simplicity, it is possible to capture important properties in many different fields. The Stable Marriage (SM) problem is exactly one of such representable problems. Given two sets of individuals partitioned into men and women, a matching is stable when there does not exist any man-woman match by which both man and woman would be individually better off than they are with the person to which they are currently matched. Stable matchings correspond to stable extensions if an AAF is correctly generated from the given SM problem. In this paper we elaborate on the original formulation by Dung, by also encoding SM problems with ties and incomplete preference lists into AAFs. Moreover, we use Weighted Abstract Argumentation to represent optimality criteria in the optimal extension of SM problems, where some matchings are better than others: criteria may consider only the preference of either men, or women, or a more global view obtained by combining the preferences of both.

Keywords

Abstract Argumentation Stable Marriage optimality criteria

1. Introduction

In his seminal paper on Abstract Argumentation [16], P. M. Dung develops the core notions behind the collective acceptability of arguments. In addition, he shows that some major approaches to non-monotonic reasoning in AI and Logic Programming are special forms of such a theory, and that the same theory can be used to capture the solutions of n-person Games and Stable Marriage (SM) problems. In this paper our wish is to tribute such a pioneering work by designing and applying a Weighted (Abstract) Argumentation approach to the latter problem, that is SM problems.

The SM problem [20,27] and its many variants [25] have been widely studied in the literature, because of the inherent appeal of the problem and its important practical applications. A classical instance of the problem comprises a bipartite set of n men and n women, and each person has a preference list in which they rank all members of the opposite sex in a strict total order. Then, a matching MT is simply a bijection between men and women. A man $m_{i}$ and a woman $w_{j}$ form a blocking pair for $MT$ if $m_{i}$ prefers $w_{j}$ to his partner in $MT$ and $w_{j}$ prefers $m_{i}$ to her partner in $MT$ . A matching that involves no blocking pair (included in $MT$ ) is said to be stable, otherwise the matching is unstable. Even though the SM problem has its roots in combinatorial problems, it has also been studied in Game Theory, Economics, and Operations Research.

In this paper we also consider the Optimal Stable Marriage (OSM) problem [25,27], whose goal is to find a matching that is not only stable, but also “good” according to some criterion based on the preferences of all the considered individuals. Classical solutions deal only with men-optimal (or women-optimal) marriages instead, in which every man (woman), gets his (her) best possible partner.

In this work, we cover part of the plethora of the SM problem extensions which are not investigated in [16]. More in particular, we investigate to what extent a simple formalisation as the one provided by Abstract Argumentation Frameworks (AAFs) [16] is capable of representing incomplete lists of preferences and ties. Further on, we also take advantage of Weighted AAFs, and in particular of c-semiring based WAAFs [5,8], in order to consider optimisation criteria characterising OSM problems. C-semiring based WAAFs can be described by a tuple $⟨ A_{rgs}, R, W, S ⟩$ that encompasses a weight function W with domain in R, and a c-semiring $S$ to be parametrically instantiated to a specific metric of weights (see Section 2). The first steps in the direction were performed in [2], by using Soft Constraints to model preferences and find a solution to OSM problems.

The paper is structured as follows: in Section 2 we introduce the necessary background notions about c-semiring based WAAFs [5,8]. Section 3 introduces the SM and OSM problem variants; this section reports the original encoding of the SM problem in a framework, but it also proposes some novelty, as for instance a view of preferences using c-semirings. Section 4 shows how incomplete lists of preferences and ties among them can be represented in AAFs. Afterwards, Section 5 adds optimisation to the picture: we show how to optimise different criteria in weighted frameworks, as WAAFs based on c-semirings. Section 6 positions the work with respect to the related work on Cooperative Games, and, in general, Game Theory. To conclude, Section 7 wraps up the paper with final thoughts and future work.

2. Weighted Abstract Argumentation with C-semirings

In this section we rephrase some of the classical definitions in [16], with the purpose to parametrise them with the notion of weighted attack and c-semiring [4]. Such notions, e.g., the one of w-defence, are the premises behind the stable semantics we then propose in Section 2.1. This background section is mainly extracted from the results in [5,8].

We start by recalling a few preliminary notions about classical Abstract Argumentation. In his pioneering work [16], P. M. Dung proposes Abstract Frameworks, where an argument is an abstract entity whose role is solely determined by its relations to other arguments:

Definition 2.1 (Abstract Frameworks [16]).

An Abstract Argumentation Framework (AAF) is a pair $⟨ A_{rgs}, R ⟩$ of a set $A_{rgs}$ of arguments and a binary relation R on $A_{rgs}$ , called attack relation. $\forall a_{i}, a_{j} \in A_{rgs}$ , $a_{i} R a_{j}$ (or $R (a_{i}, a_{j})$ ) means that $a_{i}$ attacks $a_{j}$ (R is asymmetric).

A semantics is the formal definition of a method (either declarative or procedural) ruling the argument evaluation process. In the extension-based approach, a semantics definition specifies how to derive a set of extensions from an AAF, where an extension $B$ of an AAF $⟨ A_{rgs}, R ⟩$ is simply a subset of $A_{rgs}$ . In Definition 2.2 we define conflict-free sets:

Definition 2.2 (Conflict-free sets [16]).

A set $B \subseteq A_{rgs}$ is conflict-free iff no two arguments a and b in $B$ exist such that a attacks b.

All the semantics proposed in [16] rely (explicitly or implicitly) upon the concept of defence:

Definition 2.3 (Defence [16]).

An argument b is defended by a set $B \subseteq A_{rgs}$ (or $B$ defends b) iff for any argument $a \in A_{rgs}$ , if $R (a, b)$ then $\exists b \in B$ such that $R (b, a)$ .

An admissible set of arguments [16] must be a conflict-free set that defends all its elements. Formally:

Definition 2.4 (Admissible sets).

A conflict-free set $B \subseteq A_{rgs}$ is admissible iff each argument in $B$ is defended by $B$ .

After describing basic properties of extensions, the only semantics on which we focus in this paper is the stable one.

Definition 2.5 (Stable semantics [16]).

A conflict-free set $B \subseteq A_{rgs}$ is a stable extension iff for each argument which is not in $B$ , there exists an argument in $B$ that attacks it.

We now start introducing our formalism to represent frameworks where weights are associated with attacks. The following definitions present WAAFs based on c-semirings, or ${WAAF}_{S}$ for short, where $S$ is a c-semiring:

Definition 2.6 (C-semirings [4]).

A commutative semiring is a tuple $S = ⟨ S, \oplus, \otimes, ⊥, ⊤ ⟩$ such that S is a set, $⊤, ⊥ \in S$ , and $\oplus, \otimes : S \times S \to S$ are binary operators making the triples $⟨ S, \oplus, ⊥ ⟩$ and $⟨ S, \otimes, ⊤ ⟩$ commutative monoids (semi-groups with identity), satisfying (i) $\forall s, t, u \in S . s \otimes (t \oplus u) = (s \otimes t) \oplus (s \otimes u)$ (distributivity), and (ii) $\forall s \in S . s \otimes ⊥ = ⊥$ (annihilator). If $\forall s, t \in S . s \oplus (s \otimes t) = s$ , the semiring is said to be absorptive. In short, c-semirings are defined as commutative and absorptive semirings.

Definition 2.7 (Semiring-based WAAF [9]).

A c-semiring based Weighted AAF ( ${WAAF}_{S}$ ) is a tuple $⟨ A_{rgs}, R, W, S ⟩$ , where $S$ is a c-semiring $⟨ S, \oplus, \otimes, ⊥, ⊤ ⟩$ , $A_{rgs}$ is a set of arguments, R the attack binary-relation on $A_{rgs}$ , and $W : A_{rgs} \times A_{rgs} ⟶ S$ is a binary function. Given $a, b \in A_{rgs}$ and $R (a, b)$ , then $W (a, b) = s$ means that a attacks b with a weight $s \in S$ . We require that $R (a, b)$ iff $W (a, b) <_{S} ⊤$ .

The idempotency of ⊕ leads to the definition of a partial ordering $⩽_{S}$ over the set S (S is a poset). Such a partial order is defined as $s ⩽_{S} t$ if and only if $s \oplus t = t$ , and ⊕ returns the least upper bound of s and t. This intuitively means that t is “better” than s. Some more properties can be derived on c-semirings [4]: (i) both ⊕ and ⊗ are monotone over $⩽_{S}$ , (ii) ⊗ is intensive (i.e., $s \otimes t ⩽_{S} s$ ), and (iii) $⟨ S, ⩽_{S} ⟩$ is a complete lattice. ⊥ and ⊤ respectively are the bottom and top elements of such lattice. When also ⊗ is idempotent, (i) ⊕ distributes over ⊗, (ii) ⊗ returns the greatest lower bound of two values in S, and (iii) $⟨ S, ⩽_{S} ⟩$ is a distributive lattice.

In Fig. 1 we provide an example of a ${WAAF}_{S}$ defined by $A_{rgs} = {a, b, c, d, e}$ , $R = {(a, b), (c, b), (c, d), (d, c), (d, e), (e, e)}$ , with $W (a, b) = 7$ , $W (c, b) = 8$ , $W (c, d) = 9$ , $W (d, c) = 8$ , $W (d, e) = 5$ , $W (e, e) = 6$ , and $S_{weighted} = ⟨ R^{+} \cup {\infty}, min, +, \infty, 0 ⟩$ (i.e., the Weighted c-semiring). Other well-known instances of c-semirings are: $S_{boolean} = ⟨ {false, true}, \lor, \land, false, true ⟩$ ,1

¹
Boolean c-semirings can be used to model Abstract Argumentation à-la-Dung [8].

S_{fuzzy} = ⟨ [0, 1], max, min, 0, 1 ⟩

S_{bottleneck} = ⟨ R^{+} \cup {+ \infty}, max, min, 0, \infty ⟩

S_{probabilistic} = ⟨ [0, 1], max, \times, 0, 1 ⟩

Fig. 1.

An example of WAAF.

A c-semiring value equal to the top element of the c-semiring ⊤ (e.g., 0 for the Weighted c-semiring) represents a no-attack relation between two arguments: for instance, $(a, c) \notin R$ in Fig. 1 corresponds to $W (a, c) = 0$ . Note that, whenever there is an attack between two arguments, its weight is different from ⊤: for example, $W (a, b) = 7$ in Fig. 1. On the other side, the bottom element, i.e., ⊥ (e.g., ∞ for the Weighted c-semiring), represents the worst attack possible.

In Definition 2.8 we define the attack strength for a set of arguments that attacks an argument, a different set of arguments, or an argument that attacks a set of arguments; the former and the latter are what we need to define w-defence. In the following, we will use ⨂ to indicate the ⊗ operator of the c-semiring $S$ on a set of values:

Definition 2.8 (Attacks to/from sets of arguments).

Given a ${WAAF}_{S}$ , $WF = ⟨ A_{rgs}, R, W, S ⟩$ ,

a set of arguments $B$ attacks an argument a with a weight of $k \in S$ if $W (B, a) = ⨂_{b \in B} W (b, a) = k$

an argument a attacks a set of arguments $B$ with a weight of $k \in S$ if $W (a, B) = ⨂_{b \in B} W (a, b) = k$

a set of arguments $B$ attacks a set of arguments $D$ with a weight $k \in S$ if $W (B, D) = ⨂_{b \in B, d \in D} W (b, d) = k$ .

For example, in Fig. 1 we have that $W ({a, c}, b) = 15$ , $W (c, {b, d}) = 17$ , and $W ({a, c}, {b, d}) = 24$ . We can now define our version of weighted defence, i.e., w-defence:

Definition 2.9 (w-defence ( $D_{w}$ )).

Given a ${WAAF}_{S}$ , $WF = ⟨ A_{rgs}, R, W, S ⟩$ , $B \subseteq A_{rgs}$ w-defends $b \in A_{rgs}$ iff $\forall a \in A_{rgs}$ such that $R (a, b)$ , we have that $W (a, B \cup {b}) ⩾_{S} W (B, a)$ .

As previously advanced, a set $B \subseteq A_{rgs}$ w-defends an argument b from a, if the ⊗ of all attack weights from $B$ to a is worse2

²
Note that, when considering the partial order of a generic c-semiring, we will often use “worse” or “better” because “greater” or “lesser” would be misleading: in the Weighted c-semiring, $7 ⩽_{S} 3$ , i.e., lesser means better.

(w.r.t.

⩽_{S}

) than the ⊗ of the attacks from a to

B \cup {b}

. For example, the set

{c}

in Fig. 1 defends c from d because

W (d, {c}) ⩾_{S} W ({c}, d)

, i.e., (

8 ⩽ 9

). On the other hand,

{d}

in Fig. 1 does not w-defend d because

W (c, {d}) ≱_{S} W ({d}, c)

Moreover, in the following proposition classical defence [16] and w-defence collapse one into the other in case we adopt the boolean c-semiring:

Proposition 2.10.

Given a ${WAAF}_{S}$ , $WF = ⟨ A_{rgs}, R, W, S ⟩$ , where $S = ⟨ {true, false}, \lor, \land, false, true ⟩$ (i.e., the boolean c-semiring), “ $B$ w-defends a” ⟺ “ $B$ defends a”.

Although c-semirings have been historically used as monotone structures where to aggregate costs [38, Ch. 9], the need of making ⊗ non-monotone raised in many different applications, thus requiring to define an inverse operator for it. A solution comes from residuation theory [12], a standard tool on tropical arithmetic (studying c-semirings with an idempotent +), which allows for obtaining a “weak” inverse of ⊗.

Definition 2.11 (Residuation).

Let $S$ be a tropical c-semiring. $S$ is residuated if the set ${x \in S ∣ t \otimes x ⩽_{S} s}$ admits a maximum for all elements $s, t \in S$ , such that $s ⩽_{S} t$ . The maximal element among solutions is denoted as $s ⊘ t$ .

Since a complete3

³
$S$ is complete if it is closed with respect to infinite sums, and the distributivity law holds also for an infinite number of summands.

tropical-semiring is also residuated, then all the classical instances of c-semiring previously introduced are residuated. A c-semiring is invertible if there exists an element

r \in S

such that

t \otimes r = s

for all elements

s, t \in A

such that

s ⩽_{S} t

S

is uniquely invertible if r is unique whenever

t \neq ⊥

Definition 2.12 (Unique invertibility).

If $S$ is absorptive and invertible, then it is uniquely invertible iff it is cancellative, i.e., $\forall s, t, u \in S . (s \otimes u = t \otimes u) \land (u \neq 0) \Rightarrow s = t$ .

Since all the previously listed instances of c-semirings are cancellative, they are uniquely invertible as well. For instance, considering the (i) Weighted and (ii) Fuzzy c-semirings: $\begin{array}{l} (i) min {x ∣ b + x ⩾ a} = \{\begin{matrix} 0 & if b ⩾ a \\ a - b & if a > b \end{matrix} \\ (ii) max {x ∣ min (b, x) ⩽ a} = \{\begin{matrix} 1 & if b ⩽ a \\ a & if a < b \end{matrix} \end{array}$

Having introduced ⊘, the notion of w-defence given in Definition 2.9 can be relaxed in order to be less restrictive. The result is γ-defence, and it is parametrised on a threshold-value γ: such γ is used to consider arguments that are not “fully” w-defended, i.e., for which $W (a, B \cup {b}) ≱_{S} W (B, a)$ :

Definition 2.13 (γ-defence ( $D_{γ}$ )).

Given $⟨ A_{rgs}, R, W, S = ⟨ S, \oplus, \otimes, ⊥, ⊤ ⟩ ⟩$ and $γ \in S$ , $B \subseteq A_{rgs}$ γ-defends $b \in A_{rgs}$ iff $\forall a \in A_{rgs}$ such that $R (a, b)$ we have that $W (B, a) \neq ⊤$ and $\begin{matrix} (W (a, B \cup {b}) ⊘ W (B, a)) ⩾_{S} γ \end{matrix}$

Considering the example in Fig. 1, for instance ${d}$ 1-defends d from c (i.e., $γ = 1$ ): $(W (c, {d}) - W ({d}, c)) ⩽_{S} 1$ , since $9 - 8 = 1$ and $1 ⩽ 1$ (using the Weighted c-semiring).

2.1. $α^{γ}$ -stable semantics and properties

In this section we redefine the classical stable semantics [16] by exploiting both the notion of (i) an inconsistency amount α inside an extension (to be tolerated), and (ii) the concept of γ-defence. All classical semantics are extended as $α^{γ}$ -semantics in [8].

In Definition 2.14 we relax the notion of conflict-freeness: conflicts can be now part of the solution up to a cost-threshold α. Such sets are now called α-conflict-free:

Definition 2.14 (α-conflict-free sets).

Given a ${WAAF}_{S}$ , $WF = ⟨ A_{rgs}, R, W, S ⟩$ , a subset of arguments $B \subseteq A_{rgs}$ is α-conflict-free iff $W (B, B) ⩾_{S} α$ .

With respect to the ${WAAF}_{S}$ in Fig. 1, while the set ${a, b, c}$ is not conflict-free in the crisp version of the problem (since it includes the attacks between a and b, and between c and b), ${a, b, c}$ is instead 15-conflict-free because $W (a, b) + W (c, b) = 15$ (as a a reminder, we are using the Weighted c-semiring).

We now introduce $α^{γ}$ -admissible sets:

Definition 2.15 ( $α^{γ}$ -admissible sets).

Given $WF = ⟨ A_{rgs}, R, W, S ⟩$ , an α-conflict-free set $B \subseteq A_{rgs}$ is $α^{γ}$ -admissible iff the arguments in $B$ are γ-defended by $B$ from the arguments in $A_{rgs} ∖ B$ .

Still considering Fig. 1, the set ${d, e}$ is $11^{1}$ -admissible, since it is 11-conflict-free, and d defends ${d, e}$ from c with $γ = 9 - 8$ .

Definition 2.16 proposes Dung’s stable semantics revisited in a ${WAAF}_{S}$ .

Definition 2.16 ( $α^{γ}$ -stable semantics).

Given $⟨ A_{rgs}, R, W, S ⟩$ , an $α^{γ}$ -admissible set $B$ is also an $α^{γ}$ -stable extension iff $\forall a \notin B$ , $\exists b \in B . W (b, a) \neq ⊤$ , and $B \cup {a}$ is not $α^{γ}$ -admissible.

For example, considering Fig. 1, the set ${a, d}$ corresponds to the single $0^{1}$ -stable extension, since $W (c, d) ⊘ W ({a, d}, c) = 9 - 8 ⩽ 1$ satisfies $γ = 1$ (in the Weighted c-semiring).

We conclude this section by summarising some formal results related to α-conflict-free and $α^{γ}$ -admissible sets, and the $α^{γ}$ -stable semantics (see [8] for more extended results).

Theorem 2.17.
Given $⟨ A_{rgs}, R, W, S = ⟨ S, \oplus, \otimes, ⊥, ⊤ ⟩ ⟩$ , and $α_{1}, α_{2}, γ_{1}, γ_{2} \in S$ such that $α_{1} ⩾_{S} α_{2}$ and $γ_{1} ⩾_{S} γ_{2}$ , then
the set of ⊤-conflict-free sets in $WF$ is equal to the set of conflict-free sets in F;

the set of ⊤-conflict-free sets in $WF$ is equal to the set of conflict-free sets in F;

the set of $α_{1}$ -conflict-free sets is a subset of the set of $α_{2}$ -conflict-free sets.

the set of $⊤^{⊥}$ -admissible sets in $WF$ is equal to the set of admissible sets in F;

the set of $⊤^{⊤}$ -admissible sets in $WF$ is a subset of the set of admissible sets in F;

the set of $α_{1}^{γ_{1}}$ -admissible sets is a subset of the set of $α_{2}^{γ_{2}}$ -admissible sets;

the set of $⊤^{⊥}$ -stable extensions in $WF$ is equal to the set of stable extensions in F;

for each $⊤^{⊤}$ -stable extension $B_{WF}$ in $WF$ , there exists a stable extension $B_{F}$ in F, such that $B_{WF} \subseteq B_{F}$ ;

for each $α_{1}^{γ_{1}}$ -stable extension $B_{1}$ , there exists an $α_{2}^{γ_{2}}$ -stable extension $B_{2}$ , such that $B_{1} \subseteq B_{2}$ .

3. From stable marriage problems to abstract argumentation frameworks

We divide this background section in two: in Section 3.1 we described the SM problem and its variants, while Section 3.2 reports the original formalisation of SM problems as AAFs, given by Dung in his pioneering work [16]. Both these sub-sections contain some novelty, since definitions are rephrased by using c-semirings with the purpose to pave the way for the results in the subsequent sections.

3.1. Stable matchings

An instance of the classical SM problem [18] comprises n men and n women, where each of these individuals has a preference list in which all the members of the opposite sex are ranked in a strict total order (i.e., no tie). All men and women must be matched together in a couple such that no element x of couple a prefers an element y of different couple b that also prefers x: this statement represents the overall stability condition. If such an $(x, y)$ pair exists in the matching, then it is defined as blocking; a matching is stable if no blocking pair exists. Algorithms for finding solutions to the stable marriage problem have applications in a variety of real-world situations, for instance the assignment of graduating medical students to their first hospital appointments, or assigning users to servers in a large distributed Internet service [28].

In the original formalisation of the problem [18], it is supposed to have two sets of cardinality n: $M = {m_{1}, m_{2}, \dots, m_{n}}$ and $W = {w_{1}, w_{2}, \dots, w_{n}}$ , with $M \cap W = \emptyset$ (i.e., the sets are disjoint). Associated with each element in $M \cup W$ is a strictly ordered preference list containing all the elements in the other set: $w_{k} ≻_{m_{i}} w_{j}$ means that $m_{i}$ prefers $w_{k}$ to $w_{j}$ , where $≻_{m_{i}}$ is a strict total order on W (i.e., a total ranking on W). We define a matching as $MT \subseteq {(m, w) ∣ m \in M, w \in W} such that each x \in M \cup W appears exactly once in MT$ . A pair $(m_{i}, w_{j})$ is blocking in a matching $MT$ iff $\exists m_{k}$ , $w_{l}$ such that $w_{l} ≻_{m_{i}} w_{j}$ and $m_{k} ≻_{w_{j}} m_{i}$ . $MT$ is stable if $\forall (m_{i}, w_{j}) \in MT$ , $(m_{i}, w_{j})$ is not blocking.

We initially define $p : M \cup W \times M \cup W \to N_{n}$ (with $n = | M | = | W |$ and $N_{n} = {1, \dots, n}$ ): $p (x, y)$ is a function that returns the ordinal position of y in the preference list of x, e.g., $p (m_{i}, w_{j}) = 1$ if $w_{j}$ is the most preferred woman, while $p (m_{i}, w_{k}) = n$ if $w_{k}$ is the least preferred woman: 1 represents the best position in the ranking. Same considerations hold for $p (w_{j}, m_{i})$ , that is the preference of $w_{j}$ for $m_{i}$ .

The SM problem was first studied by Gale and Shapley [18]. They showed that there always exists at least one stable MT in any problem instance as previously described. In addition, they also proposed a $O (n^{2})$ -time algorithm to solve the problem, i.e., the so-called Gale–Shapley (GS) algorithm. An extended version of the GS algorithm, i.e. the EGS algorithm [20], avoids some unnecessary steps: it reduces the preference lists by eliminating pairs that can be readily identified as not belonging to any stable matching. Notice that, in the “men-oriented” (or men optimal) version of the GS/EGS algorithm, each man has the best partner (according to his preference list) that he could obtain, whilst each woman has the worst partner that she can accept. Similar considerations hold for the “woman-oriented” (or women optimal) version of GS, where women have the best, and men have the worst possible partner.

In general, there can be more than one stable matching: in a uniformly-random instance of an SM problem with n men and n women, the average number of stable matchings is asymptotically $e^{- 1} n ln n$ [34]. The problem of counting the number of stable matchings in a given instance is ♯P-complete [23]. Readers can refer to [25] and the works by R. W. Irving for further information on counting SM solutions. While in the following we suppose that the number of men and women is always the same, there exist also variants where this number is unequal.

The classical SM problem was extended [18] in order to find an SM under a more equitable measure of optimality, thus defining an Optimal SM problem (OSM) [19,24,25,27]. For example, in [24] the authors maximise the global satisfaction in an SM by simply summing together the preferences of both men and women in a matching. This sum needs to be minimised since $p (m_{i}, w_{j})$ represents the rank of $w_{j}$ in $m_{i}$ ’s list of preferences. Therefore, we need to minimise the egalitarian cost [24] in Equation (1): $\begin{array}{rcl} (1) & min (\sum_{(m_{i}, w_{j}) \in MT} p (m_{i}, w_{j}) + \sum_{(m_{i}, w_{j}) \in MT} p (w_{j}, m_{i})) \end{array}$ Such an optimisation problem was originally posed by D. Knuth [24]. Other optimisation criteria are represented by minimising the regret cost [19], as represented in Equation (2): $\begin{array}{rcl} (2) & min {max_{(m_{i}, w_{j}) \in MT} max (p (m_{i}, w_{j}), p (w_{j}, m_{i}))} \end{array}$

A third criterion consists in minimising the sex-equalness cost [26], as represented in Equation (3): $\begin{array}{rcl} (3) & min | \sum_{(m_{i}, w_{j}) \in MT} p (m_{i}, w_{i}) - \sum_{(m_{i}, w_{j}) \in MT} p (w_{j}, m_{i}) | \end{array}$

Finding a solution satisfying the goals represented by Equation (1) and Equation (2) already found their solution in polynomial time by using ad-hoc algorithms, such as [24] and [19], respectively. These algorithms exploit a lattice structure that condenses the information about all the stable matchings. On the contrary, reaching the optimality represented by Equation (3) was proved to be an NP-hard problem, for which approximation algorithms are proposed [26].

In the following, we consider preferences as more general values taken from a c-semiring, instead of a position in the preference list of an individual; thus, we suppose to model weighted preference lists [24]. For this reason we define a c-semiring-based extension of SM, by changing the co-domain of p into S:

Definition 3.1 (C-semiring-based SM/OSM).

An ${SM}_{S} / {OSM}_{S}$ problem is defined by a tuple $⟨ M, W, p, S ⟩$ , where M and W are two non-overlapping sets of elements both of the same cardinality, $p : M \cup W \times M \cup W \to S$ , and $S = ⟨ S, \oplus, \otimes, ⊥, ⊤ ⟩$ .

The description given in Definition 3.1 is capable of representing both ordinal preference lists and weighted ones: the former can be straightforwardly encoded in the latter. Briefly, ${SM}_{S}$ problems also model classical SM problems.

A different variant of the SM problem, but still compatible with respect to SM/OSM ones, allows incomplete preference lists: an SM problem has incomplete lists (SMI) if an individual can exclude a partner whom she/he does not want to be matched with [25] (some preferences are omitted). Therefore, function p is partial: there exists some $(m_{i}, w_{j})$ for which p is not defined, i.e., $p (m_{i}, w_{j}) ↑$ and/or $p (w_{j}, m_{i}) ↑$ .4

⁴
Conversely, $p (m_{i}, w_{j}) ↓$ and/or $p (w_{j}, p_{i}) ↓$ if p is defined on that couple.

In this case, a matching of all men or women may not exist (i.e., a perfect matching), and this can be decided/found in polynomial time. A further extension is represented by preference lists that allow ties, i.e., in which it is possible to express the same preference for more than one possible partner: the problem is usually named as “SM with ties” [25] (SMT). In this case, three stability notions are proposed in the literature [25]:

given any two couples $(m_{i}, w_{j})$ and $(m_{k}, w_{z})$ , in a super stable matching a pair $(m_{i}, w_{z})$ is blocking iff $p (m_{i}, w_{z}) ⩾_{S} p (m_{i}, w_{j}) \land p (w_{z}, m_{i}) ⩾_{S} p (w_{z}, m_{k})$ ;

in a strongly stable matching a pair $(m_{i}, w_{z})$ is blocking iff $p (m_{i}, w_{z}) >_{S} p (m_{i}, w_{j}) \land p (w_{z}, m_{i}) ⩾_{S} p (w_{z}, m_{k})$ or $p (m_{i}, w_{z}) ⩾_{S} p (m_{i}, w_{j}) \land p (w_{z}, m_{i}) >_{S} p (w_{z}, m_{k})$ ;5

⁵

Note that, since the set of preferences is in general partially ordered in a c-semiring, a strict $>_{S}$ could not be possible to achieve. This does not hold for classical c-semirings introduce in Section 2 as the Weighted, Fuzzy, and Probabilistic ones, where preference values are totally ordered.

in a weakly stable matching a pair $(m_{i}, w_{z})$ is blocking iff $p (m_{i}, w_{z}) >_{S} p (m_{i}, w_{j}) \land p (w_{z}, m_{i}) >_{S} p (w_{z}, m_{k})$ .

Fig. 2.

An OSM problem represented as a bipartite graph. Preference lists are complete and with ties (w.r.t. $m_{2}$ ).

Hence, if a matching is super stable then it is also strongly stable; if it is strongly stable then it is weakly stable [25]. A weakly stable matching always exists and can be found in polynomial time [22] in classical SM problems. Super- and strongly-stable matchings may not exist instead. Nevertheless, allowing ties in preferences means that the problem of finding an optimal weakly stable matching using Equation (1), Equation (2), or Equation (3) (i.e., considering OSMT problems) becomes hard even to approximate: there exists a positive constant ϵ such that there is no polynomial time approximation algorithm with approximation ratio $ϵ n$ , unless $P = NP$ [25].

Moreover, even the solution of a classical SM problem becomes harder in presence of ties and incomplete lists (SMTI): the SMTI problem is proved to be an NP-complete [25].

In Fig. 2 we present a small example of an ${SM}_{S}$ problem with two men and two women, as a bipartite graph. We suppose to use the Weighted c-semiring: $S = ⟨ R^{+} \cup {+ \infty}, min, +, + \infty, 0 ⟩$ . The lists of preference are complete and with ties (that is an SMT problem): $m_{2}$ shows the same preference for $w_{1}$ and $w_{2}$ . For instance, the matching ${(m_{1}, w_{2}), (m_{2}, w_{1})}$ is not weakly (then neither strongly nor super) stable because $(m_{1}, w_{1})$ is a blocking pair: $p (m_{1}, w_{1}) >_{S} p (m_{1}, w_{2}) \land p (w_{1}, m_{1}) >_{S} p (w_{1}, m_{2})$ , i.e. $1 >_{S} 4 \land 1 >_{S} 5$ .

3.2. Stable marriages as abstract argumentation frameworks

In [16] P. M. Dung shows how his theory based on Abstract Argumentation can be used to investigate the logical structure of the classical SM problem solutions (and others, as n-person games). The SM problem can be formalised as the task of finding a stable extension of $F = ⟨ A_{rgs}, R ⟩$ as follows: $w_{z}$ represents a threat to a marriage $(m_{i}, w_{j})$ if $m_{i}$ prefers $w_{z}$ to $w_{j}$ . In other words, a hypothetical marriage of $m_{i}$ to $w_{z}$ poses an attack to the couple $(m_{i}, w_{j})$ . But this attack is eliminated if $w_{z}$ is married to someone whom $w_{z}$ prefers to $m_{i}$ .

To assemble a framework representing a SM problem, the set of arguments $A_{rgs}$ has cardinality $| M | \cdot | W |$ ,6

⁶
$| M | \cdot | W | = n^{2}$ in case their cardinality n is the same.

and each argument is labelled by using an element from the set of men, and one from the set of women:

Definition 3.2 (SMs and AFs).

Given an ${SM}_{S}$ problem with complete preference lists and no tie, a corresponding AAF is $A_{rgs} = {(m \times w) ∣ m \in M, w \in W}$ , and $R \subseteq A_{rgs} \times A_{rgs}$ such that $R ((m_{k}, w_{l}), (m_{i}, w_{j}))$ iff

$i = k$ and $p (m_{i}, w_{l}) >_{S} p (m_{i}, w_{j})$ , or

$j = l$ and $p (w_{j}, m_{k}) >_{S} p (w_{j}, m_{i})$ .

In [16] it is also proved that the set of stable extensions and the set of stable marriages correspond.

Theorem 3.3 (Stability [16]).

A set $B \subseteq A_{rgs}$ represents a solution to the SM problem iff $B$ is a stable extension of the corresponding AAF.

From previous results in the literature, reported in Section 3.1, we can immediately derive some simple statements about existence and enumeration complexity of stable extensions, which can be straightforwardly proven by the fact that stable matchings and stable extensions correspond.

Corollary 3.4 (Existence of stable extensions).

Given any (classical) SM problem, the corresponding $⟨ A_{rgs}, R ⟩$ always has one stable extension at least.

Proof.
An SM problem always have one solution at least, hence a stable extensions always exists. □

From well-founded frameworks and their absence of cycles [16] we can derive sufficient conditions for the uniqueness of a stable matching.
Corollary 3.5 (Unicity).

In $F = ⟨ A_{rgs}, R ⟩$ obtained from an SM problem, if F is well-founded then there exists a unique stable matching.

Proof.
A framework F is well-founded [16] if there exists no infinite sequence $a_{0}, a_{1}, \dots, a_{n}, \dots$ such that $\forall i > 0, R (a_{i + 1}, a_{i})$ . Then in F has only one stable extension (which is also grounded, preferred, and complete). □

The following corollary derives from the complexity of enumerating stable matchings.
Corollary 3.6 (Enumeration complexity).

Given any SM, the problem of enumerating all the stable extensions in the corresponding $⟨ A_{rgs}, R ⟩$ is ♯P-complete.

Proof.
Counting the number of stable matchings in an SM problem is ♯P-complete [23]. □

From Corollary 3.4 and the results in [14], it is possible to relate stable and semi-stable extensions.
Corollary 3.7 (Stable and semi-stable).

In $F = ⟨ A_{rgs}, R ⟩$ obtained from an SM problem, the set of stable and semi-stable extensions always coincide.

Proof.
Theorem 3 in [14] states that the set of stable and semi-stable extensions coincide if a framework has at least one stable extension. According to Corollary 3.4, a stable extension always exists in F. □

In addition, the following statement relates the presence of some pairs in all possible matchings.
Corollary 3.8.
Given a $⟨ A_{rgs}, R ⟩$ obtained from an SM problem, an argument $(m_{i}, w_{j})$ where $m_{i}$ / $w_{j}$ prefers $w_{j}$ / $m_{i}$ than all other partners, is (sceptically) accepted in all the stable extensions, and it consequently belongs to all stable matchings.
Proof.
If there exists $(m_{i}, w_{j})$ such that $\forall h \neq i$ , $k \neq j . R ((m_{i}, w_{j}), (m_{h}, w_{j}))$ , then $(m_{i}, w_{j})$ has to belong to any stable extension. □

To conclude this section, we show a simple example of an SM problem (complete preferences without ties) and its encoding as an AAF. The preference function p is expressed in tabular form in Fig. 3. The obtained AAF is represented in Fig. 4, where the only stable extension is given by ${(m_{1}, w_{2}), (m_{2}, w_{1})}$ .

Fig. 3.
An SM problem given in tabular form, with men preferences on the left and women preferences on the right, e.g., $p (m_{1}, w_{1}) = 1$ and $p (w_{2}, m_{1}) = 2$ .

Fig. 4.
The AAF encoding of the SM problem in Fig. 3. The only stable extension is ${(m_{1}, w_{2}), (m_{2}, w_{1})}$ .
4. Argumentation frameworks for incomplete lists and ties

In his original encoding, P. M. Dung does not show how to deal with ties and incomplete lists. In this section we extend the formalism in [16] in order to extend his work along this direction.

4.1. Argumentation frameworks and incomplete lists

The first issue we address is the absence of some preference values from a list: if x does not express a preference with respect to y (different sex), this means that matching x and y is not allowed. To model this case we refer to Definition 4.1.

Definition 4.1 (SMI and AAFs).

Given an ${SMI}_{S}$ problem, a corresponding AAF is $A_{rgs} = {(m \times w) ∣ m \in M, w \in W, p (m, w) ↓ \land p (w, m) ↓}$ , and $R \subseteq A_{rgs} \times A_{rgs}$ such that $R ((m_{k}, w_{l}), (m_{i}, w_{j}))$ iff

$i = k$ and $p (m_{i}, w_{l}) >_{S} p (m_{i}, w_{j})$ , or

$j = l$ and $p (w_{j}, m_{k}) >_{S} p (w_{j}, m_{i})$ .

Hence, the only difference with Dung’s original formulation (encoded in Definition 3.2 by using c-semirings) is that the assembled AAF has indeed less than $n^{2}$ arguments if the preference lists are incomplete. On the other hand, the attack relation R is defined as for the case with complete lists.7

⁷
Note that the proposed formalisation is equivalent to removing an argument representing a couple that is never preferred, i.e., which is only attacked without attacking any other couple.

Figure 5 presents an example of an incomplete list for $m_{2}$ , while Fig. 6 shows the AAF assembled using Definition 4.1. Theorem 4.2 relates stable extensions obtained from the encoding in Definition 4.1 with the stable marriages in case of incomplete preference lists. All and only stable extensions that represent perfect matchings are valid solutions.

Fig. 5.

An SMI problem, where “−” means $m_{2}$ expresses no preference for $w_{1}$ .

Fig. 6.

The AAF encoding of the SM problem in Fig. 5. The only stable extension is ${(m_{1}, w_{1}), (m_{2}, w_{2})}$ . Argument $(m_{2}, w_{1})$ does not belong to the framework because of the missing preference.

Theorem 4.2 (Equivalence and incomplete lists).

Being $⟨ A_{rgs}, R ⟩$ a framework representing an ${SMI}_{S}$ problem, $B$ is a stable solution of the problem iff there exists a stable extension $B \subseteq A_{rgs}$ such that $\forall m_{i}, \exists! (m_{k}, w_{j}) \in B$ s.t. $i = k$ , and $\forall w_{j}, \exists! (m_{i}, w_{k}) \in B$ such that $j = k$ . 8

⁸
In mathematical logic, the $\exists!$ quantification is known as uniqueness quantification or unique existential quantification.

Proof.

Attacks are added to the AAF in the same way as in [16] and they enforce stability of couples. The side condition requires the single presence of every man and every woman in the matching, despite incompleteness. If this condition is not satisfied, then the obtained stable extension $B$ cannot represent a (perfect) matching. The proof then proceeds in the same way as in [16]. □

As an example of non-existence, if we consider the preference lists in Fig. 3 and we remove the entry between $m_{1}$ and $w_{2}$ , the only stable extension is ${(m_{2}, w_{1})}$ , which is not enough to (perfectly) match all the men and women.

4.2. Argumentation frameworks and ties

Ties can be managed in different ways if the goal is to obtain either weakly- or super-stable matchings (see Section 3).9

⁹
Strong-stability is left to future work (see Section 7).

First of all, the description already proposed in Definition 4.1 is enough to directly obtain weakly-stable matchings: it is possible to model different stability conditions by differently adding attacks to the framework. We start by defining how to achieve weak-stability.

Theorem 4.3 (Equivalence and weak-stability).

Being $F = ⟨ A_{rgs}, R ⟩$ a framework representing an ${SMT}_{S}$ problem and using $⩾_{S}$ in Definition 3.2 , $B$ is a weakly-stable solution of the problem iff $B$ is a stable extension in F.

Proof.
If $p (m_{i}, w_{j}) = p (m_{i}, w_{k})$ (a tie with respect to $m_{i}$ , or $p (m_{i}, w_{j}) = p (m_{h}, w_{j})$ a tie with respect to $w_{j}$ ), a symmetric attack10
¹⁰
Hence, to model parity between preferences, the use of asymmetric attacks is enough to model the underlying uncertainty between two equivalent choices represented by a tie.

is posed between these two couples in the corresponding AAF; hence, either one of these pairs can be part of a stable marriage, alternatively. Therefore, ties are allowed and the proof proceeds as proposed by Dung in [16]. □

On the other hand, in order to model super-stability, instead of $>_{S}$ we need to use $⩾_{S}$ in Definition 4.1, and require that what obtained is a matching, as in presence of incomplete lists (Theorem 4.2).
Theorem 4.4 (Equivalence and super-stability).

Being $F = ⟨ A_{rgs}, R ⟩$ a framework representing an ${SMT}_{S}$ problem and using $>_{S}$ in Definition 3.2 , $B$ is a weakly-stable solution of the problem iff $B$ is a stable extension such that $\forall m_{i}, \exists! (m_{k}, w_{j}) \in B$ such that $i = k$ , and $\forall w_{j}, \exists! (m_{i}, w_{k}) \in B$ such that $j = k$ always exists.

Proof.
If $p (m_{i}, w_{j}) = p (m_{i}, w_{k})$ (a tie with respect to $m_{i}$ , or $p (m_{i}, w_{j}) = p (m_{h}, w_{j})$ a tie with respect to $w_{j}$ ), no attack is posed between these two couples in the corresponding AAF. Therefore, attacks model conflicts between strictly better preferences, and thus super-stability, while the condition for a stable extension to represent a valid matching avoids marrying the same man/woman twice. □

An example of ${SMT}_{S}$ problem is given in Fig. 7, while Fig. 8 shows the derived AAF considering weak-stability. Symmetric attacks are used between any two equally preferred arguments, that is in case of a tie: between $(m_{1}, w_{1})$ and $(m_{2}, w_{1})$ , and between $(m_{2}, w_{1})$ and $(m_{2}, w_{2})$ . Figure 9 shows a framework derived to obtain super-stability from the same preference values in Fig. 7. As we can see, the framework is completely different with respect to Fig. 8, and by discarding ${(m_{1}, w_{1}), (m_{2}, w_{1}), (m_{2}, w_{2})}$ as a non-valid solution, as a result that framework has no super-stable matching.

Fig. 7.
An SMT problem (i.e., with ties with respect to $m_{2}$ and $w_{1}$ ), with men preferences on the left and women preferences on the right.

Fig. 8.
The AAF encoding of the SMT problem in Fig. 7, modeling weak-stability. The two stable extensions are ${(m_{1}, w_{1}), (m_{2}, w_{2})}$ and ${(m_{1}, w_{2}), (m_{2}, w_{1})}$ .

Fig. 9.
The AAF encoding of the SMT problem in Fig. 7, using super-stability. The only stable extension ${(m_{1}, w_{1}), (m_{2}, w_{1}), (m_{2}, w_{2})}$ , which is not a matching, means that no super-stable matching exists in this case.
4.3. Argumentation frameworks for incomplete lists and ties

In this section we present a larger example of an SMTI problem, hence considering both incomplete lists and ties, and we show how the stable extensions on the derived AAF represent all the (super- and weakly-stable) solutions. We use the following definition, using weak-stability.

Definition 4.5 (Weakly-stable SMTI and AAFs).

Given an ${SMT}_{S}$ problem, a corresponding AAF is $A_{rgs} = {(m \times w) ∣ m \in M, w \in W, p (m, w) ↓ \land p (w, m) ↓}$ , and $R \subseteq A_{rgs} \times A_{rgs}$ such that $R ((m_{k}, w_{l}), (m_{i}, w_{j}))$ iff

$i = k$ and $p (m_{i}, w_{l}) ⩾_{S} p (m_{i}, w_{j})$ , or

$j = l$ and $p (w_{j}, m_{k}) ⩾_{S} p (w_{j}, m_{i})$ .

Corollary 4.6 (Equivalence, incomplete lists, and weak-stability).

Being $F = ⟨ A_{rgs}, R ⟩$ a framework representing an ${SMTI}_{S}$ problem and assembled as in Definition 4.5 , $B$ is a weakly-stable solution of the problem iff $B$ is a stable extension in F.

Proof.
The proof directly derives by Theorem 4.2 and Theorem 4.3, by satisfying both incompleteness and ties in preference lists respectively. □

As as result of Theorem 4.4, by only replacing $⩾_{S}$ with $>_{S}$ we can find super-stable matchings. The tables of preferences in Fig. 10 represent an example of ${SMTI}_{S}$ problem with six men and six women. We still suppose to use the Weighted c-semiring ( $S = ⟨ R^{+} \cup {+ \infty}, min, +, + \infty, 0 ⟩$ ) to model preferences in ${SMTI}_{S}$ problems. We developed a Python script that automatically translates two matrices (men/women) of preferences into an AAF using the aspartix format (.apx files): an argument is represented as arg(m1w1), and attacks as as list of att(m1w1,m1w2). We first encoded it to model super-stable solutions. The obtained framework, using the preferences in Fig. 10, counts 31 arguments out of 36 (i.e., $n^{2}$ ): $(m_{1}, w_{3})$ , $(m_{3}, w_{2})$ , $(m_{3}, w_{5})$ , $(m_{5}, w_{4})$ , $(m_{6}, w_{2})$ miss because of incomplete preference lists. This framework has 128 attacks. We computed the stable extensions by using ConArg11
¹¹
ConArg Website: http://www.dmi.unipg.it/conarg/.

[6,7,10]: the obtained graph is represented in Fig. 11, within the ConArg Web-interface environment. ConArg returns three stable extensions:

${(m_{1}, w_{1}), (m_{2}, w_{2}), (m_{3}, w_{4}), (m_{4}, w_{5}), (m_{5}, w_{6}), (m_{6}, w_{3})}$ ,

${(m_{1}, w_{1}), (m_{2}, w_{2}), (m_{3}, w_{4}), (m_{4}, w_{6}), (m_{5}, w_{5}), (m_{6}, w_{3})}$ ,

${(m_{1}, w_{1}), (m_{2}, w_{2}), (m_{3}, w_{4}), (m_{4}, w_{3}), (m_{5}, w_{6}), (m_{6}, w_{5})}$ .

Fig. 10.
A larger ${SMTI}_{S}$ problem with six men and six women.

Fig. 11.
The example with 6 men and 6 women in Fig. 10, drawn in the Web interface of ConArg.

The three solutions are the same as what obtained on the same case-study by using an Integer Logic Programming approach in [2], hence validating the result in the practice.

If we assemble the framework with the purpose to model weak stability (hence using $>_{S}$ instead of $⩾_{S}$ ), we obtain one more matching (for a total of four weakly-stable matchings):

${(m_{1}, w_{1}), (m_{2}, w_{6}), (m_{3}, w_{4}), (m_{4}, w_{2}), (m_{5}, w_{5}), (m_{6}, w_{3})}$ .
5. OSM problems and (weighted) argumentation frameworks

Referring to Section 3, men and women biased optimality criteria were the first objective functions proposed to distinguish different kinds of satisfaction among all possible matchings obtained as result. However, further criteria were proposed to suggest fairer criteria, or at least considering both the preferences of men and women, as, for example, the egalitarian cost. In this section we show how to represent these problems in AAFs, and obtain such solutions as stable extensions.

5.1. Preferences on arguments

We start by labelling arguments with weights. We use c-semirings and their operators to model preference values and find the best stable extension, but we do not adopt WAAFs introduced in the background section (Section 2), where attacks are weighted: this second approach will be proposed in Section 5.2 instead. Considering the three optimisation criteria in Section 3, all of them can be captured by using a c-semiring $S = ⟨ S, \oplus, \otimes, ⊥, ⊤ ⟩$ and a function $f : S \times S \to S$ that we use to compose $p (m_{i}, w_{j})$ and $p (w_{j}, m_{i})$ . We use f to find the overall preference if we match $m_{i}$ with $w_{j}$ , i.e., if $(m_{i}, w_{j}) \in MT$ , that is the combined man-woman/woman-man preference. In addition, the two c-semiring operators represent the different optimisation criteria. The obtained parametric formula is given by Term (1). $\begin{matrix} (1) & ⨁ (⨂_{(m_{i}, w_{j}) \in MT} f (p (m_{i}, w_{j}), p (w_{j}, m_{i}))) \end{matrix}$

By embedding the Weighted c-semiring $⟨ R^{+} \cup {+ \infty}, min, +, + \infty, 0 ⟩$ and with $f \equiv +$ (the arithmetic addition) we obtain the egalitarian cost in Equation (1). By instead using the Fuzzy c-semiring $⟨ [0, 1], max, min, 0, 1 ⟩$ and $f \equiv max$ , we can model the regret cost in Equation (2).

Moreover, we can also represent man and woman optimality by using the Weighted c-semiring $⟨ R^{+} \cup {+ \infty}, min, +, + \infty, 0 ⟩$ , and a function f that always return the first (man-optimal) or second (woman-optimal) component of the considered couple of preferences.

For men-optimality: $f_{mo} (p (m_{i}, w_{j}), p (w_{j}, m_{i})) \to p (m_{i}, w_{j})$ ,

while for women-optimality: $f_{wo} (p (m_{i}, w_{j}), p (w_{j}, m_{i})) \to p (w_{j}, m_{i})$ .

We now formally describe what introduced above:

Definition 5.1 (OSMTI to weighted frameworks).

Given an ${SMTI}_{S}$ problem, a c-semiring $S = ⟨ S, \oplus, \otimes, ⊥, ⊤ ⟩$ , and preference composition operator $f : S \times S \to S$ , a corresponding weighted framework is $A_{rgs} = {(m \times w) ∣ m \in M, w \in W, p (m, w) ↓ \land p (w, m) ↓}$ , and $R \subseteq A_{rgs} \times A_{rgs}$ such that $R ((m_{k}, w_{l}), (m_{i}, w_{j}))$ iff

$i = k$ and $p (m_{i}, w_{l}) ⩾_{S} p (m_{i}, w_{j})$ , or

$j = l$ and $p (w_{j}, m_{k}) ⩾_{S} p (w_{j}, m_{i})$

and each argument

(m_{i}, w_{j})

in the obtained framework is labelled with a preference given by

f (p (m_{i}, w_{j}), p (w_{j}, m_{i})

Having defined a framework as in the above definition, we now declare how to reach optimality according to the different proposed criteria.

Proposition 5.2 (Modelling criteria with c-semirings).

The best solution according to ⊕, found by composing the preference values of arguments using ⊗ on the stable extensions found by Definition 5.3 , optimises the egalitarian cost:

by using $f \equiv +$ and the Weighted c-semiring;

regret cost:

by using $f \equiv max$ and the Fuzzy c-semiring;

man-optimality:

by using $f \equiv f_{mo}$ and the Weighted c-semiring;

woman-optimality:

by using $f \equiv f_{wo}$ and the Weighted c-semiring.

Proof.
While adding attacks as suggested in Definition 5.3 let us obtain stable extensions which correspond to weakly-stable solutions (see Theorem 4.5), optimisation is built on top of stable extensions, and it is achieved by construction given $S$ and f. □

Note that sex-equalness (Equation (3)) cannot be locally modelled by costs on single arguments, since it is the global satisfaction of men and women whose difference is minimised. In this case, arguments can be labelled with a couple $⟨ p (m_{i}, w_{j}), p (w_{j}, m_{i}) ⟩$ . By composing such a preference with a Cartesian product of two Weighted c-semirings,12
¹²
The Cartesian product of c-semirings is still a c-semiring (see [4]).

in the end all stable extensions will have a cost of $\begin{matrix} ⟨ \sum_{(m_{i}, w_{j}) \in MT} p (m_{i}, w_{j}), \sum_{(m_{i}, w_{j}) \in MT} p (w_{j}, m_{j}) ⟩, \end{matrix}$ which can be finally optimised to find the sex-equalness cost. The global nature of this criterion is what makes its solution NP-hard (see Section 3.1).

We consider again the four weakly-stable matchings obtained on the example represented by the preferences in Fig. 10:

${MT}_{1} = {(m_{1}, w_{1}), (m_{2}, w_{2}), (m_{3}, w_{4}), (m_{4}, w_{5}), (m_{5}, w_{6}), (m_{6}, w_{3})}$ ,

${MT}_{2} = {(m_{1}, w_{1}), (m_{2}, w_{2}), (m_{3}, w_{4}), (m_{4}, w_{6}), (m_{5}, w_{5}), (m_{6}, w_{3})}$ ,

${MT}_{3} = {(m_{1}, w_{1}), (m_{2}, w_{2}), (m_{3}, w_{4}), (m_{4}, w_{3}), (m_{5}, w_{6}), (m_{6}, w_{5})}$ ,

${MT}_{4} = {(m_{1}, w_{1}), (m_{2}, w_{6}), (m_{3}, w_{4}), (m_{4}, w_{2}), (m_{5}, w_{5}), (m_{6}, w_{3})}$ .

Table 1 shows the egalitarian, regret, sex-equalness, man-optimal, and woman-optimal costs obtained for these four matchings on the example in Fig. 10. These values were obtained by using a Python script that, besides building the .apx file with the framework as given in Definition 5.3, also runs the dockerised13
¹³
Docker: https://www.docker.com.

version of ConArg.14
¹⁴
The Docker image of ConArg is downloadable from the repository with command docker pull iccma19/conarg.

In this way, it is possible to run ConArg on any platform (Linux, Mac OSX, Windows) and then use a Python library15
¹⁵
Docker SDK for Python: https://docker-py.readthedocs.io.

to talk with the ConArg container and enumerate all the stable extensions in the given framework.

The best matching for both the egalitarian and sex-equalness criteria is ${MT}_{1}$ , while according to the regret cost, all the four matchings optimise this criterion. The best matching according to only men’s preference (i.e., man-optimality) is ${MT}_{4}$ , and for women’s preference is ${MT}_{3}$ . As expected, man-optimality corresponds to the worst preference possible for women, and vice-versa.

Table 1
The egalitarian, regret, and sex-equalness cost obtained for the four matchings of the example in Fig. 10. Moreover, we report the man-optimal and woman-optimal costs. In bold, the best solution according to the specific criterion. We compute and report also the sex-equalness cost even if it cannot be straightforwardly generalised with C-semirings by using Term (1)

Egalitarian Regret Sex-equalness Man-optimal Woman-optimal

${MT}_{1}$ 29 6 3 16 13

${MT}_{2}$ 32 6 4 14 18

${MT}_{3}$ 30 6 12 21 9

${MT}_{4}$ 32 6 8 12 20

5.2. Preference values on attacks

	Egalitarian	Regret	Sex-equalness	Man-optimal	Woman-optimal
${MT}_{1}$	29	6	3	16	13
${MT}_{2}$	32	6	4	14	18
${MT}_{3}$	30	6	12	21	9
${MT}_{4}$	32	6	8	12	20

Finally, we show how to use the WAAFs proposed in [5,8] and summarised in Section 2 with the purpose to use weights on attacks instead of arguments. In this way we manage to encode optimisation criteria directly in the model and solve them by using ConArg, without performing an optimisation step after having searched for stable extensions.

First we need to label attacks in a proper way: for example, self-attacks on arguments are associated with the cost of a couple according to one of the criteria proposed in the literature, e.g., the egalitarian one. The cost of attacks between arguments impose the constraint to never match the same man/woman with two women/men. Attacks need to be directed from the couple with the better to the argument with the worse preference, as proposed in all the other previous definitions, including Dung’s original proposal. The cost of these attacks is ⊥: this means these constraints cannot ever be broken.

The formal description of the proposed construction is given in Definition 5.3. Since the definition uses $⩾_{S}$ , it consequently models weakly-stable marriages.

Definition 5.3 (OSMTI to WAAFs).

Given an ${SMTI}_{S}$ problem over $S = ⟨ S, \oplus, \otimes, ⊥, ⊤ ⟩$ and preference composition operator $f : S \times S \to S$ , a corresponding WAAF described by $WF = ⟨ A_{rgs}, R, W, S ⟩$ is composed by:

$A_{rgs} = {(m \times w) ∣ m \in M, w \in W, p (m, w) ↓ \land p (w, m) ↓}$ , and

$R^{'} \subseteq A_{rgs} \times A_{rgs}$ such that $R^{'} ((m_{k}, w_{l}), (m_{i}, w_{j}))$ with $W ((m_{k}, w_{l}), (m_{i}, w_{j})) = ⊥$ iff

$i = k$ and $p (m_{i}, w_{l}) ⩾_{S} p (m_{i}, w_{j})$ , or

$j = l$ and $p (w_{j}, m_{k}) ⩾_{S} p (w_{j}, m_{i})$ .

$R^{″} \subseteq A_{rgs} \times A_{rgs}$ such that $\forall (m_{i}, w_{j}) \in A_{rgs}$ then $R^{″} ((m_{i}, w_{j}), (m_{i}, w_{j}))$ : $R^{″}$ contains all and only self-attacks on the arguments in $A_{rgs}$ . The cost of self attacks is $W ((m_{i}, w_{j}), (m_{i}, w_{j})) = f (p (m_{i}, w_{j}), p (w_{j}, m_{i}))$

where

R = R^{'} \cup R^{″}

In Fig. 12 we show an example of OSMTI problem, while Fig. 13 represents its encoding as WAAF using Definition 5.3. Even in this example we suppose to use the Weighted c-semiring.

Fig. 12.

An OSMTI problem (i.e., with ties and incomplete lists), with men preferences on the left and women preferences on the right.

Fig. 13.

The WAAF encoding of the OSMTI problem in Fig. 12. The value of self-attacks is computed by using the egalitarian cost of the couple represented by each argument.

By relaxing the internal inconsistency α,16

¹⁶

See Section 2.1: α limits the cost of all the attacks included in an extension (aggregated through ⊗).

each returned

α^{⊤}

-stable extension represents a weakly-stable OSMTI problem with an optimisation cost better or equal than α. Therefore, α represents the e.g. egalitarian cost of the corresponding matching, if Term (1) is used with the Weighted c-semiring and

p \equiv +

. Proposition 5.2 holds for the WAAF obtained from Definition 5.3 as well: it is possible to achieve men-optimality, women-optimality, optimise the egalitarian and regret costs as accomplished with weights on arguments in Section 5.1.

We can now formally show how $α^{⊤}$ -stable extensions are related to stable matchings.

Theorem 5.4.

Being $WF = ⟨ A_{rgs}, R, W, S ⟩$ a WAAF representing an ${OSMTI}_{S}$ problem obtained through Definition 5.3 , $B$ is a weakly-stable solution of the problem with cost better/equal than α iff $B$ is an $α^{⊤}$ -stable extension in $WF$ .

Proof.

Attacks are oriented as in the formalisation given by Dung [16]: they represent preferences in the same way, but they are associated with ⊥. Therefore, there is not possibility to include two attacking arguments, if not allowing $α = ⊥$ . The cost of each stable extension is thus represented by the aggregation (with ⊗) of all the values labelling-self attacks, which correspond to the result of the f function, taken from Proposition 5.2 to optimise the desired criterion. □

The choice of labelling attacks instead of arguments is also preferred from the point of view of implementation: ConArg uses such a threshold to cut the search space as soon as a partial solution has a cost which is already above α.

Figure 14 highlights the single $29^{0}$ -stable extension on the WAAFs created according to Definition 5.3, and obtained from the OSMTI problem in Fig. 10. Clearly, by setting $α = 32$ we obtain two more weakly-stable matchings, ${MT}_{2}$ and ${MT}_{3}$ in Table 1, whose cost is 32 and 30 respectively ( ${MT}_{4}$ is super-stable instead).

Fig. 14.

The matching minimising the egalitarian cost on the problem in Fig. 10, solved in ConArg by using a model as suggested in Definition 5.3. Its cost is 29, as shown in the right-menu checkbox. We use a value of 1000 to represent ⊥ in the Weighted c-semiring (i.e., $+ \infty$ ).

5.3. On relaxing marriages

Still within the model represented by WAAFs in Section 2, the last achievement follows the relaxation of constraints enforcing stability of matchings by worsening γ, which in Section 5.2 is always ⊤.17

¹⁷
See Section 2.1: γ represents a penalty that can be paid if an argument is not “completely” defended: Section 5.2 uses $α^{⊤}$ -semantics, that is where $γ = ⊤$ .

By also adding an attack from the worse to the better preference value between two couples, it is then possible to allow non-preferred strategies. By gradually worsening γ we can then accept more and more marriages, since stability constraints are consequently relaxed.

A similar approach is proposed in [33] using Constraint Programming. There the authors provide a generalisation of the classical notion of stability, requiring that there are not two people that prefer with at least degree α (where α is a natural number) to be married to each other rather than to their current partners. The fact that α-stability leads to a larger number of stable marriages with respect to the classical case is important to allow new stable marriages where some men, for example, the most popular ones or the least popular ones, may be married with partners better than all the feasible ones according to the classical notion of stability.

In the approach we describe in this paper instead, attacks from better to worse preference values are labelled with $\bar{γ}$ : this value is computed in such a way to enforce marriages as final results, that is a man/woman cannot be matched with more than one woman/man. In our approach, we define $\bar{γ}$ as the ⊗-aggregation of all self-attack costs in a framework, that is of all preference scores related to arguments, as in Section 5.2. Hence, to include two connected arguments a penalty of $\bar{γ}$ needs to be paid, and this value is definitely worse than each possible matching, which contains no more than half of the arguments: therefore, $\bar{γ}$ results in a milder threshold with respect to ⊥ used in Section 5.2.

As previously introduced, for each of these attacks we also add an inverse attack, from the worse to better preference score. The value associated with this attack is $\bar{γ}$ composed (using ⊗) with the difference (using ⊘) between the worse and the better preference values: $\bar{γ} \otimes (p (m_{i}, w_{j}) ⊘ p (m_{i}, w_{l}))$ . To formally (and parametrically) define this cost we use the weak inverse of ⊗, i.e., ⊘, which is used to remove one value from another in a c-semiring (see Section 2). The obtained value represents the cost to be tolerated to take a worse couple in the final matching. Such a relaxation is achieved by increasing γ.

A simple example of this construction is represented by the problem in Fig. 15, and its corresponding WAAF in Fig. 16. This example uses the egalitarian cost, hence $\bar{γ}$ is 24, which is equal to the sum of self-attacks. The formal description of it is instead represented by Definition 5.5.

Fig. 15.

An example of an OSMTI problem. We suppose to use the Weighted c-semiring.

Fig. 16.

The WAAF encoding of the matching problem in Fig. 15. The value of self-attacks is computed by using the egalitarian cost; $\bar{γ}$ is the sum of them: 24.

Definition 5.5 (From relaxed OSMTI to WAAFs).

Given an ${SMTI}_{S}$ problem over $S = ⟨ S, \oplus, \otimes, ⊥, ⊤ ⟩$ and preference composition operator $f : S \times S \to S$ , a corresponding WAAF $WF = ⟨ A_{rgs}, R, W, S ⟩$ is composed by:

$A_{rgs} = {(m \times w) ∣ m \in M, w \in W, p (m, w) ↓ \land p (w, m) ↓}$ , and

$R^{'} \subseteq A_{rgs} \times A_{rgs}$ such that $R^{'} ((m_{k}, w_{l}), (m_{i}, w_{j}))$ with $W ((m_{k}, w_{l}), (m_{i}, w_{j})) = \bar{γ}$ iff

$i = k$ and $p (m_{i}, w_{l}) ⩾_{S} p (m_{i}, w_{j})$ , or

$j = l$ and $p (w_{j}, m_{k}) ⩾_{S} p (w_{j}, m_{i})$ .

$R^{″} \subseteq A_{rgs} \times A_{rgs}$ such that for each $R^{'} ((m_{k}, w_{l}), (m_{i}, w_{j}))$ there exists $R ((m_{i}, w_{j}), (m_{k}, w_{l}))$ , and $W ((m_{i}, w_{j}), (m_{k}, w_{l})) =$

$\bar{γ} \otimes (p (m_{i}, w_{j}) ⊘ p (m_{i}, w_{l}))$ iff $i = k$ , or

$\bar{γ} \otimes (p (m_{j}, m_{j}) ⊘ p (w_{j}, m_{k}))$ iff $j = l$ .

$R^{‴} \subseteq A_{rgs} \times A_{rgs}$ such that $\forall (m_{i}, w_{j}) \in A_{rgs}$ there exists $R^{‴} ((m_{i}, w_{j}), (m_{i}, w_{j}))$ such that $W ((m_{i}, w_{j}), (m_{i}, w_{j})) = f (p (m_{i}, w_{j}), p (w_{j}, m_{i})$

where

R = R^{'} \cup R^{″} \cup R^{‴}

and

\bar{γ} = ⨂_{((m_{i}, w_{j}), (m_{i}, w_{j})) \in R^{‴}} W ((m_{i}, w_{j}), (m_{i}, w_{j}))

Figure 17 reports the results obtained by ConArg on the WAAF created according to Definition 5.5 from the OSMTI problem in Fig. 10. Even in this example we set values on arguments to represent the egalitarian cost. The tool returns three $29^{2}$ -stable-extensions, that is with $α = 29$ and $γ = 2$ (in this example, we have that $\bar{γ} = 211$ ):

${(m_{1}, w_{1}), (m_{2}, w_{2}), (m_{3}, w_{4}), (m_{4}, w_{5}), (m_{5}, w_{6}), (m_{6}, w_{3})}$ with an egalitarian cost of 29,

${(m_{1}, w_{1}), (m_{2}, w_{5}), (m_{3}, w_{4}), (m_{4}, w_{2}), (m_{5}, w_{6}), (m_{6}, w_{3})}$ with an egalitarian cost of 27,

${(m_{1}, w_{1}), (m_{2}, w_{5}), (m_{3}, w_{4}), (m_{4}, w_{6}), (m_{5}, w_{3})}$ with an egalitarian cost of 26.

Fig. 17.

The relaxed matchings related to the OSMTI problem in Fig. 10, with $α = 29$ and $γ = 2$ ( $\bar{γ} = 211$ ).

The third matching is not perfect: by adding inverse attacks with respect to Section 5.2, clearly it is easier to reach stability even with less arguments. In addition to the first matching, which is ${MT}_{1}$ (the matching optimising the egalitarian cost), the proposed relaxation also brings a totally new (and perfect) matching, whose cost of 27 is better than the one of ${MT}_{1}$ . In the future we will explore different notions of relaxation and formalise a distance from classical unrelaxed solutions (see Section 7).

6. Related work

In [16, Section 3], Dung shows how his theory can be used to investigate the logical structure of the solutions to important practical problems, thus supporting the correctness of the proposed approach. The first application example is about Argumentation in n-person Games [31], while the second relates Argumentation and the SM problem. In particular, Dung extends the problem by considering same-sex marriages (x loves y if x prefers y to all others), whose solution is given by finding preferred extensions in this new AAF. In case of a set of people $P = {m, w, p_{1}, p_{2}, p_{3}}$ , if there is a love triangle between $p_{1}$ , $p_{2}$ , and $p_{3}$ ( $p_{1}$ loves $p_{2}$ , who loves $p_{3}$ , who loves $p_{1}$ ), then it follows it is not possible to arrange a marriage among these three people, and the corresponding AAF has exactly one preferred extension containing only the pair $(m, w)$ . Such a reasoning is used to support the fact that it is natural to expect that any knowledge system may not have a stable semantics: in this extended problem, the preferred semantics can be used to find a solution given the absence of a stable extension.

Apart from this paper, to the best of our knowledge no other work has been committed along the same line of research, as we instead aim at in this paper. Nevertheless, from a game theoretical point of view, stable matching problems are equivalent to the problem of finding a core element in some corresponding Cooperative Game with or without transferable utility.18

¹⁸
Transferable utility is a key concept in Cooperative Game Theory: it is transferable if one player can losslessly transfer part of its utility to another player.

The SM problem can be considered as a basic game without transferable utility [1]. Cooperative Game Theory (mostly developed, as the SM problem itself, by Lloyd S. Shapley) is based on coalition building and usage of transferable utility [39]. Coalitions consist of players who wish to play or work together with the purpose to increase their benefits: a Cooperative Game should bring more benefit than playing alone. It is a principle of stability that makes coalitions attractive. The importance of this principle is also depicted in the first part of [16, Section 3], when Dung presents cooperative n-person Game as AAFs, as previously introduced. Even in this case, an n-person Game may not have a stable solution, but preferred extensions represent a rational behaviour to follow if this happens. An n-person Game can be seen as a framework

⟨ A_{rgs}, R ⟩

, where

A_{rgs}

represents the set of possible outcomes u of a Cooperative Game, and where u represents a vector of utilities, one per agent. The set of attacks is instead given by

R = {(u, u^{'}) ∣ u dominates u^{'}}

Because of the aforementioned motivations, the remainder of this section is thus dedicated to the two branches of research strictly related to this paper. The first one adopts Cooperative Game approaches to measure an acceptability score of arguments in coalitions (sometimes also used in ranking-based semantics), while the second one collects works that link Argumentation and Game Theory. A survey of what Game Theory can do for Argumentation and vice-versa is presented in [40, Ch. 16]: an agent may use Game Theory to analyse a given argumentative situation in order to choose the best strategy, and, on the other hand, it is possible to design the rules (e.g., and Argumentation protocol) in such a way as to promote good argumentative behaviour.19

¹⁹

In the aim of Mechanism Design is to design game-rules in such a way that self-interested agents behave in some desirable manner (e.g. tell the truth).

Papers measuring the strength of arguments are reported in the following. In [30] the authors propose a two-person Strategic Game between a “proponent” and an “opponent”, where the strategies of the players are subsets of arguments, and the pay-offs of the game are based on the structure of the directed graph associated to the AAF. The players need to compute a strength value for the argument to play: the obtained score satisfies a number of appealing properties that can be derived mathematically from the minimax theorem from Von Neumann’s theory.

In [13] the authors propose a way to compute the relative relevance of arguments by merging Abstract Argumentation [16] into a Game Theoretic coalitional setting. In their framework, the worth of a collection of arguments can be seen as the combination of the information concerning the defeat relation and the preferences. Then, the Shapley Value is applied to elicit a relevance values for the single arguments from scores obtained for sets of arguments.

In [3] some of the authors of this paper deploy a Game-theoretic approach for analysing the acceptability of arguments in a generic AAF. The result is a ranking-based semantics, which sorts arguments from the most to the least acceptable. In the computation of such a ranking, the authors again adopt the Shapley Value formula, in order to fairly distribute costs among several entities in coalitions.

Papers on Argumentation more broadly related to Game Theory are presented in the following. In [36] the authors introduce a Game-theoretic Argumentation Mechanism Design, which enables the design and analysis of Argumentation mechanisms for self-interested agents. They then design a particular direct mechanism and prove that it is strategy proof under specific conditions: the computed strategy profile in which each agent reveals its arguments truthfully is a dominant strategy equilibrium. The work in [32] extends [36] by exploiting the preferred semantics to compute outcomes, instead of the grounded one.

The authors of [35] are interested in the dynamics of an Argumentation. They map Dung’s frameworks into Extensive-form Games of perfect information, and present algorithms for determining equilibria for the Argumentation Fames that are guaranteed to terminate.

Utility functions are also studied in [37], where Strategic Argumentation20

²⁰

In Strategic Argumentation, an agent employs a strategy, typically in the form of a heuristic, which selects appropriate arguments given some contextual knowledge.

is studied by using opponent models, that is recursive representations of agent’s knowledge and beliefs regarding the opponent’s knowledge.

Strategies and utilities are often used in persuasion dialogues, where a generic persuader presents arguments to convince a user to change her behaviour. Some examples are works as [11,21].

7. Conclusion

In this paper we have worked along one of the several directions pioneered in the ’95 seminal work by P.M. Dung [16], more precisely, on the strong ties between Abstract Argumentation and the Stable Marriage problem. As far as we know, except for Dung’s paper, this topic was not studied in successive studies, as suggested by the literature reported in Section 6.

We started by showing how possible variants of the classical problem can be modelled and solved: incomplete lists and ties in men/women preferences. After this, we have shown how to model different optimality criteria in the literature of the OSM problem, e.g., the egalitarian cost. We achieved optimisation by first labelling arguments with preference values, and then labelling attacks, thus reconnecting to c-semiring WAAFs presented in [5,8]. By tolerating an internal relaxation (we call α) it is possible to consider and limit the cost of a matching. We have used a parametric structure of costs, that is a c-semiring, with the purpose to generalise the results to different optimisation criteria: in this paper we model the egalitarian and regret costs, men and women optimality. Finally, in the same WAAF setting, we have introduced a possible relaxation of marriages, by playing on a defence-based threshold that measures the strength of defence (we call this relaxation γ).

The formalism provided by Abstract Argumentation is rich enough to model all the aforementioned problems, even if it is sometimes necessary to refine the obtained matchings by checking further side conditions, e.g., if a marriage has n couples in presence of incomplete lists in classical SM problems.

In the future we plan to further investigate related topics. For instance, we plan to use Weighted Abstract Argumentation to study and model strategies in Cooperative Games, from a more general approach than just focusing on marriages. We think of using weights on arguments/attacks to study (strictly or weakly) dominant strategies: many simple games can be solved using dominance. Iterated Elimination of Dominated Strategies [17] (IESDS) is a common technique for solving games that involves iteratively removing dominated strategies: we would like to check how we can simplify the corresponding abstract framework in order to obtain the same solutions (as extensions). We believe using WAAFs can capture more properties than just classical Argumentation, since we can directly embed pay-offs of players in the model and optimise according to different criteria. In general, we aim to proceed in the study of Cooperative Games with Argumentation by taking advantage of the stability of sets, and optimising the pay-off of the obtained coalition. Some initial steps towards this direction, whose goal was to define ranking semantics using the Shapley value obtained from a given coalition of arguments, were proposed in [3].

Additional problems, strictly related to the SM one, are the Stable Roommates (all participants belong to a single pool, not divided into different sexes), the hospitals/residents (a hospital can accept more than one resident), or the assignment problem, which consists of finding, in a weighted bipartite graph, a matching in which the sum of weights of the edges is as large as possible. Our intent is to apply the same Argumentation-based approach presented in this paper to these problems as well.

Moreover, we would like to investigate how to represent strong-stability, in which super-stability is requested only for one of the partners in a blocking pair, and not both of them (otherwise just super-stability is requested).

Finally, we would like to investigate possible relaxations of the SM problem through formalisations in Abstract Argumentation, as the one proposed in Section 5.3. This can be helpful in case a matching problem has no solution, and nevertheless it is desirable to have something very close to it, even if it requires a small sacrifice of some couples in the matching. Other representations not constrained by the use of WAAFs can be used to explore different notions of relaxation and their effect.

Note also that other weighted defences can be used in the formalisation of the OSM problem in Section 5: we plan to generalise the presented results by using [15] and [29].

Footnotes

Acknowledgements

This work has been supported by the following two projects funded by the authors’ Department: Argumentation 360 (“Ricerca di Base” 2017–2019) and “Rappresentazione della Conoscenza e Apprendimento Automatico (RACRA) (“Ricerca di base” 2018–2020).

References

Biró , The stable matching problem and its generalizations: An algorithmic and game theoretical approach, PhD thesis, Budapest University of Technology and Economics, 2007.

Bistarelli ,

S.N.

Foley ,

O’Sullivan and

Santini , From marriages to coalitions: A soft CSP approach, in: Recent Advances in Constraints, 13th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP, LNCS, Vol. 5655, Springer, 2008, pp. 1–15.

Bistarelli ,

Giuliodori ,

Santini and

Taticchi , A cooperative-game approach to share acceptability and rank arguments, in: Proceedings of the 2nd Workshop on Advances in Argumentation in Artificial Intelligence, AI ³ @AI*IA , CEUR Workshop Proceedings, Vol. 2296, CEUR-WS.org, 2018, pp. 86–90.

Bistarelli ,

Montanari and

Rossi , Semiring-based constraint satisfaction and optimization, Journal of the ACM44(2) (1997), 201–236. doi:10.1145/256303.256306.

Bistarelli ,

Rossi and

Santini , A relaxation of internal conflict and defence in weighted argumentation frameworks, in: European Conference on Logics in Artificial Intelligence, JELIA, LNCS, Vol. 10021, 2016, pp. 127–143. doi:10.1007/978-3-319-48758-8_9.

Bistarelli ,

Rossi and

Santini , ConArg: A tool for classical and weighted argumentation, in: Computational Models of Argument – Proceedings of COMMA, FAIA, Vol. 287, IOS Press, 2016, pp. 463–464.

Bistarelli ,

Rossi and

Santini , A ConArg-based library for abstract argumentation, in: 29th IEEE International Conference on Tools with Artificial Intelligence, ICTAI, IEEE Computer Society, 2017, pp. 374–381.

Bistarelli ,

Rossi and

Santini , A novel weighted defence and its relaxation in abstract argumentation, Int. J. Approx. Reasoning92 (2018), 66–86. doi:10.1016/j.ijar.2017.10.006.

Bistarelli and

Santini , A common computational framework for semiring-based argumentation systems, in: ECAI – European Conference on Artificial Intelligence, FAIA, Vol. 215, IOS, 2010, pp. 131–136.

10.

Bistarelli and

Santini , ConArg: A constraint-based computational framework for argumentation systems, in: IEEE 23rd International Conference on Tools with Artificial Intelligence, ICTAI, IEEE Computer Society, 2011, pp. 605–612.

11.

Black and

Atkinson , Choosing persuasive arguments for action, in: 10th International Conference on Autonomous Agents and Multiagent Systems AAMAS, IFAAMAS, 2011, pp. 905–912.

12.

T.S.

Blyth and

M.F.

Janowitz , Residuation Theory, Vol. 102, Pergamon Press, Oxford, 1972.

13.

Bonzon ,

Maudet and

Moretti , Coalitional games for abstract argumentation, in: Computational Models of Argument – Proceedings of COMMA 2014, Frontiers in Artificial Intelligence and Applications, Vol. 266, IOS Press, 2014, pp. 161–172.

14.

Caminada ,

W.A.

Carnielli and

P.E.

Dunne , Semi-stable semantics, J. Log. Comput.22(5) (2012), 1207–1254. doi:10.1093/logcom/exr033.

15.

Coste-Marquis ,

Konieczny ,

Marquis and

M.A.

Ouali , Weighted attacks in argumentation frameworks, in: Principles of Knowledge Representation and Reasoning (KR), AAAI, 2012, pp. 593–597. ISBN 978-1-57735-560-1.

16.

P.M.

Dung , On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artif. Intell.77(2) (1995), 321–357. doi:10.1016/0004-3702(94)00041-X.

17.

Fudenberg and

Tirole , Game Theory, MIT Press, Cambridge, MA, 1991.

18.

Gale and

L.S.

Shapley , College admissions and the stability of marriage, The American Mathematical Monthly69(1) (1962), 9–15. doi:10.1080/00029890.1962.11989827.

19.

Gusfield , Three fast algorithms for four problems in stable marriage, SIAM J. Comput.16(1) (1987), 111–128. doi:10.1137/0216010.

20.

Gusfield and

R.W.

Irving , The Stable Marriage Problem: Structure and Algorithms, MIT Press, Cambridge, MA, USA, 1989. ISBN 0-262-07118-5.

21.

Hunter , Modelling the persuadee in asymmetric argumentation dialogues for persuasion, in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI, AAAI Press, 2015, pp. 3055–3061.

22.

R.W.

Irving , Stable marriage and indifference, Discrete Applied Mathematics48(3) (1994), 261–272. doi:10.1016/0166-218X(92)00179-P.

23.

R.W.

Irving and

Leather , The complexity of counting stable marriages, SIAM J. Comput.15(3) (1986), 655–667. doi:10.1137/0215048.

24.

R.W.

Irving ,

Leather and

Gusfield , An efficient algorithm for the “optimal” stable marriage, J. ACM34(3) (1987), 532–543. doi:10.1145/28869.28871.

25.

Iwama and

Miyazaki , A survey of the stable marriage problem and its variants, in: International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008), IEEE Computer Society, 2008, pp. 131–136. doi:10.1109/ICKS.2008.7.

26.

Iwama ,

Miyazaki and

Yanagisawa , Approximation algorithms for the sex-equal stable marriage problem, in: Algorithms and Data Structures, 10th International Workshop, WADS, LNCS, Vol. 4619, Springer, 2007, pp. 201–213. doi:10.1007/978-3-540-73951-7_18.

27.

D.E.

Knuth , Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms, American Mathematical Society, 1997. ISBN 0821806033.

28.

B.M.

Maggs and

R.K.

Sitaraman , Algorithmic nuggets in content delivery, Computer Communication Review45(3) (2015), 52–66. doi:10.1145/2805789.2805800.

29.

D.C.

Martínez ,

A.J.

García and

G.R.

Simari , An abstract argumentation framework with varied-strength attacks, in: Principles of Knowledge Representation and Reasoning (KR), AAAI, 2008, pp. 135–144. ISBN 978-1-57735-384-3.

30.

Matt and

Toni , A game-theoretic measure of argument strength for abstract argumentation, in: Logics in Artificial Intelligence, 11th European Conference, JELIA, Lecture Notes in Computer Science, Vol. 5293, Springer, 2008, pp. 285–297. doi:10.1007/978-3-540-87803-2_24.

31.

Morgenstern and

Von Neumann , Theory of Games and Economic Behavior, Princeton University Press, 1953.

32.

Pan ,

Larson and

Rahwan , Argumentation mechanism design for preferred semantics, in: Computational Models of Argument: Proceedings of COMMA, Frontiers in Artificial Intelligence and Applications, Vol. 216, IOS Press, 2010, pp. 403–414.

33.

M.S.

Pini ,

Rossi ,

K.B.

Venable and

Walsh , Stability, optimality and manipulation in matching problems with weighted preferences, Algorithms6(4) (2013), 782–804. doi:10.3390/a6040782.

34.

Pittel , The average number of stable matchings, SIAM J. Discrete Math.2(4) (1989), 530–549. doi:10.1137/0402048.

35.

A.D.

Procaccia and

J.S.

Rosenschein , Extensive-form argumentation games, in: EUMAS 2005 – Proceedings of the Third European Workshop on Multi-Agent Systems, Koninklijke Vlaamse Academie van Belie voor Wetenschappen en Kunsten, 2005, pp. 312–322.

36.

Rahwan and

Larson , Mechanism design for abstract argumentation, in: 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), IFAAMAS, 2008, pp. 1031–1038.

37.

Rienstra ,

Thimm and

Oren , Opponent models with uncertainty for strategic argumentation, in: Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI, IJCAI/AAAI, 2013, pp. 332–338.

38.

Rossi ,

van Beek and

Walsh (eds), Handbook of Constraint Programming, Foundations of Artificial Intelligence, Vol. 2, Elsevier, 2006.

39.

A.E.

Roth , The Shapley Value: Essays in Honor of Lloyd S. Shapley, Cambridge University Press, 1988.

40.

G.R.

Simari and

Rahwan (eds), Argumentation in Artificial Intelligence, Springer, 2009. ISBN 78-0-387-98196-3. doi:10.1007/978-0-387-98197-0.

Abstract argumentation and (optimal) stable marriage problems

Abstract

Keywords

1. Introduction

2. Weighted Abstract Argumentation with C-semirings

Definition 2.1 (Abstract Frameworks [16]).

Definition 2.2 (Conflict-free sets [16]).

Definition 2.3 (Defence [16]).

Definition 2.4 (Admissible sets).

Definition 2.5 (Stable semantics [16]).

Definition 2.6 (C-semirings [4]).

Definition 2.7 (Semiring-based WAAF [9]).

1 Boolean c-semirings can be used to model Abstract Argumentation à-la-Dung [8].

Definition 2.9 (w-defence ( D w )).

2 Note that, when considering the partial order of a generic c-semiring, we will often use “worse” or “better” because “greater” or “lesser” would be misleading: in the Weighted c-semiring, 7 ⩽ S 3 , i.e., lesser means better.

3 S is complete if it is closed with respect to infinite sums, and the distributivity law holds also for an infinite number of summands.

Definition 2.13 (γ-defence ( D γ )).

2.1. α γ -stable semantics and properties

Definition 2.14 (α-conflict-free sets).

Definition 2.15 ( α γ -admissible sets).

Definition 2.16 ( α γ -stable semantics).

3.1. Stable matchings

Definition 3.1 (C-semiring-based SM/OSM).

4 Conversely, p ( m i , w j ) ↓ and/or p ( w j , p i ) ↓ if p is defined on that couple.

6 | M | · | W | = n 2 in case their cardinality n is the same.

Theorem 3.3 (Stability [16]).

Corollary 3.4 (Existence of stable extensions).

Proof. An SM problem always have one solution at least, hence a stable extensions always exists. □ From well-founded frameworks and their absence of cycles [16] we can derive sufficient conditions for the uniqueness of a stable matching. Corollary 3.5 (Unicity).

Proof. Counting the number of stable matchings in an SM problem is ♯P-complete [23]. □ From Corollary 3.4 and the results in [14], it is possible to relate stable and semi-stable extensions. Corollary 3.7 (Stable and semi-stable).

4.1. Argumentation frameworks and incomplete lists

Definition 4.1 (SMI and AAFs).

7 Note that the proposed formalisation is equivalent to removing an argument representing a couple that is never preferred, i.e., which is only attacked without attacking any other couple.

8 In mathematical logic, the ∃ ! quantification is known as uniqueness quantification or unique existential quantification.

9 Strong-stability is left to future work (see Section 7).

Definition 4.5 (Weakly-stable SMTI and AAFs).

Corollary 4.6 (Equivalence, incomplete lists, and weak-stability).

5.1. Preferences on arguments

Definition 5.1 (OSMTI to weighted frameworks).

Proposition 5.2 (Modelling criteria with c-semirings).

Definition 5.3 (OSMTI to WAAFs).

17 See Section 2.1: γ represents a penalty that can be paid if an argument is not “completely” defended: Section 5.2 uses α ⊤ -semantics, that is where γ = ⊤ .

18 Transferable utility is a key concept in Cooperative Game Theory: it is transferable if one player can losslessly transfer part of its utility to another player.

Footnotes

Acknowledgements

References

¹
Boolean c-semirings can be used to model Abstract Argumentation à-la-Dung [8].

Definition 2.9 (w-defence ( $D_{w}$ )).

²
Note that, when considering the partial order of a generic c-semiring, we will often use “worse” or “better” because “greater” or “lesser” would be misleading: in the Weighted c-semiring, $7 ⩽_{S} 3$ , i.e., lesser means better.

³
$S$ is complete if it is closed with respect to infinite sums, and the distributivity law holds also for an infinite number of summands.

Definition 2.13 (γ-defence ( $D_{γ}$ )).

2.1. $α^{γ}$ -stable semantics and properties

Definition 2.15 ( $α^{γ}$ -admissible sets).

Definition 2.16 ( $α^{γ}$ -stable semantics).

⁴
Conversely, $p (m_{i}, w_{j}) ↓$ and/or $p (w_{j}, p_{i}) ↓$ if p is defined on that couple.

⁶
$| M | \cdot | W | = n^{2}$ in case their cardinality n is the same.

Proof.
An SM problem always have one solution at least, hence a stable extensions always exists. □

From well-founded frameworks and their absence of cycles [16] we can derive sufficient conditions for the uniqueness of a stable matching.
Corollary 3.5 (Unicity).

Proof.
Counting the number of stable matchings in an SM problem is ♯P-complete [23]. □

From Corollary 3.4 and the results in [14], it is possible to relate stable and semi-stable extensions.
Corollary 3.7 (Stable and semi-stable).

⁷
Note that the proposed formalisation is equivalent to removing an argument representing a couple that is never preferred, i.e., which is only attacked without attacking any other couple.

⁸
In mathematical logic, the $\exists!$ quantification is known as uniqueness quantification or unique existential quantification.

⁹
Strong-stability is left to future work (see Section 7).

¹⁷
See Section 2.1: γ represents a penalty that can be paid if an argument is not “completely” defended: Section 5.2 uses $α^{⊤}$ -semantics, that is where $γ = ⊤$ .

¹⁸
Transferable utility is a key concept in Cooperative Game Theory: it is transferable if one player can losslessly transfer part of its utility to another player.