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.
In his seminal paper on Abstract Argumentation , 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  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 and a woman form a blocking pair for if prefers to his partner in and prefers to her partner in . A matching that involves no blocking pair (included in ) 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 . More in particular, we investigate to what extent a simple formalisation as the one provided by Abstract Argumentation Frameworks (AAFs)  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 that encompasses a weight function W with domain in R, and a c-semiring to be parametrically instantiated to a specific metric of weights (see Section 2). The first steps in the direction were performed in , 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 , with the purpose to parametrise them with the notion of weighted attack and c-semiring . 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 , 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 ).
An Abstract Argumentation Framework (AAF) is a pair of a set of arguments and a binary relation R on , called attack relation. , (or ) means that attacks (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 of an AAF is simply a subset of . In Definition 2.2 we define conflict-free sets:
Definition 2.2(Conflict-free sets ).
A set is conflict-free iff no two arguments a and b in exist such that a attacks b.
All the semantics proposed in  rely (explicitly or implicitly) upon the concept of defence:
Definition 2.3(Defence ).
An argument b is defended by a set (or defends b) iff for any argument , if then such that .
An admissible set of arguments  must be a conflict-free set that defends all its elements. Formally:
Definition 2.4(Admissible sets).
A conflict-free set is admissible iff each argument in is defended by .
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 ).
A conflict-free set is a stable extension iff for each argument which is not in , there exists an argument in 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 for short, where is a c-semiring:
Definition 2.6(C-semirings ).
A commutative semiring is a tuple such that S is a set, , and are binary operators making the triples and commutative monoids (semi-groups with identity), satisfying (i) (distributivity), and (ii) (annihilator). If , the semiring is said to be absorptive. In short, c-semirings are defined as commutative and absorptive semirings.
Definition 2.7(Semiring-based WAAF ).
A c-semiring based Weighted AAF () is a tuple , where is a c-semiring , is a set of arguments, R the attack binary-relation on , and is a binary function. Given and , then means that a attacks b with a weight . We require that iff .
The idempotency of ⊕ leads to the definition of a partial ordering over the set S (S is a poset). Such a partial order is defined as if and only if , 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 : (i) both ⊕ and ⊗ are monotone over , (ii) ⊗ is intensive (i.e., ), and (iii) 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) is a distributive lattice.
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, in Fig. 1 corresponds to . Note that, whenever there is an attack between two arguments, its weight is different from ⊤: for example, 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 on a set of values:
Definition 2.8(Attacks to/from sets of arguments).
Given a , ,
a set of arguments attacks an argument a with a weight of if
an argument a attacks a set of arguments with a weight of if
a set of arguments attacks a set of arguments with a weight if .
For example, in Fig. 1 we have that , , and . We can now define our version of weighted defence, i.e., w-defence:
Definition 2.9(w-defence ()).
Given a , , w-defends iff such that , we have that .
As previously advanced, a set w-defends an argument b from a, if the ⊗ of all attack weights from to a is worse2 (w.r.t. ) than the ⊗ of the attacks from a to . For example, the set in Fig. 1 defends c from d because , i.e., (). On the other hand, in Fig. 1 does not w-defend d because .
Moreover, in the following proposition classical defence  and w-defence collapse one into the other in case we adopt the boolean c-semiring:
Given a , , where (i.e., the boolean c-semiring), “ w-defends a” ⟺ “ 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 , a standard tool on tropical arithmetic (studying c-semirings with an idempotent +), which allows for obtaining a “weak” inverse of ⊗.
Let be a tropical c-semiring. is residuated if the set admits a maximum for all elements , such that . The maximal element among solutions is denoted as .
Since a complete3 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 such that for all elements such that . is uniquely invertible if r is unique whenever .
Definition 2.12(Unique invertibility).
If is absorptive and invertible, then it is uniquely invertible iff it is cancellative, i.e., .
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:
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 :
Definition 2.13(γ-defence ()).
Given and , γ-defends iff such that we have that and
Considering the example in Fig. 1, for instance 1-defends d from c (i.e., ): , since and (using the Weighted c-semiring).
2.1.-stable semantics and properties
In this section we redefine the classical stable semantics  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 .
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 , , a subset of arguments is α-conflict-free iff .
With respect to the in Fig. 1, while the set 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), is instead 15-conflict-free because (as a a reminder, we are using the Weighted c-semiring).
We now introduce -admissible sets:
Definition 2.15(-admissible sets).
Given , an α-conflict-free set is -admissible iff the arguments in are γ-defended by from the arguments in .
Still considering Fig. 1, the set is -admissible, since it is 11-conflict-free, and d defends from c with .
Definition 2.16 proposes Dung’s stable semantics revisited in a .
Definition 2.16(-stable semantics).
Given , an -admissible set is also an -stable extension iff , , and is not -admissible.
For example, considering Fig. 1, the set corresponds to the single -stable extension, since satisfies (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  for more extended results).
Given , and such that and , then
the set of ⊤-conflict-free sets in is equal to the set of conflict-free sets in F;
the set of ⊤-conflict-free sets in is equal to the set of conflict-free sets in F;
the set of -conflict-free sets is a subset of the set of -conflict-free sets.
the set of -admissible sets in is equal to the set of admissible sets in F;
the set of -admissible sets in is a subset of the set of admissible sets in F;
the set of -admissible sets is a subset of the set of -admissible sets;
the set of -stable extensions in is equal to the set of stable extensions in F;
for each -stable extension in , there exists a stable extension in F, such that ;
for each -stable extension , there exists an -stable extension , such that .
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 . 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.
An instance of the classical SM problem  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 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 .
In the original formalisation of the problem , it is supposed to have two sets of cardinality n: and , with (i.e., the sets are disjoint). Associated with each element in is a strictly ordered preference list containing all the elements in the other set: means that prefers to , where is a strict total order on W (i.e., a total ranking on W). We define a matching as . A pair is blocking in a matching iff , such that and . is stable if , is not blocking.
We initially define (with and ): is a function that returns the ordinal position of y in the preference list of x, e.g., if is the most preferred woman, while if is the least preferred woman: 1 represents the best position in the ranking. Same considerations hold for , that is the preference of for .
The SM problem was first studied by Gale and Shapley . They showed that there always exists at least one stable MT in any problem instance as previously described. In addition, they also proposed a -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 , 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 . The problem of counting the number of stable matchings in a given instance is ♯P-complete . Readers can refer to  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  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  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 represents the rank of in ’s list of preferences. Therefore, we need to minimise the egalitarian cost  in Equation (1):
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  and , 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 .
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 . 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 problem is defined by a tuple , where M and W are two non-overlapping sets of elements both of the same cardinality, , and .
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, 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  (some preferences are omitted). Therefore, function p is partial: there exists some for which p is not defined, i.e., and/or .4 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”  (SMT). In this case, three stability notions are proposed in the literature :
given any two couples and , in a super stable matching a pair is blocking iff ;
in a strongly stable matching a pair is blocking iff or ;5
in a weakly stable matching a pair is blocking iff .
Hence, if a matching is super stable then it is also strongly stable; if it is strongly stable then it is weakly stable . A weakly stable matching always exists and can be found in polynomial time  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 , unless .
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 .
In Fig. 2 we present a small example of an problem with two men and two women, as a bipartite graph. We suppose to use the Weighted c-semiring: . The lists of preference are complete and with ties (that is an SMT problem): shows the same preference for and . For instance, the matching is not weakly (then neither strongly nor super) stable because is a blocking pair: , i.e. .
3.2.Stable marriages as abstract argumentation frameworks
In  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 as follows: represents a threat to a marriage if prefers to . In other words, a hypothetical marriage of to poses an attack to the couple . But this attack is eliminated if is married to someone whom prefers to .
To assemble a framework representing a SM problem, the set of arguments has cardinality ,6 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 problem with complete preference lists and no tie, a corresponding AAF is , and such that iff
and , or
In  it is also proved that the set of stable extensions and the set of stable marriages correspond.
Theorem 3.3(Stability ).
A set represents a solution to the SM problem iff 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 always has one stable extension at least.
An SM problem always have one solution at least, hence a stable extensions always exists. □
From well-founded frameworks and their absence of cycles  we can derive sufficient conditions for the uniqueness of a stable matching.
In obtained from an SM problem, if F is well-founded then there exists a unique stable matching.
A framework F is well-founded  if there exists no infinite sequence such that . 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 is ♯P-complete.
Counting the number of stable matchings in an SM problem is ♯P-complete . □
Corollary 3.7(Stable and semi-stable).
In obtained from an SM problem, the set of stable and semi-stable extensions always coincide.
Theorem 3 in  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.
Given a obtained from an SM problem, an argument where / prefers / than all other partners, is (sceptically) accepted in all the stable extensions, and it consequently belongs to all stable matchings.
If there exists such that , , then 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 .
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  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 problem, a corresponding AAF is , and such that iff
and , or
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 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
Figure 5 presents an example of an incomplete list for , 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.
Theorem 4.2(Equivalence and incomplete lists).
Being a framework representing an problem, is a stable solution of the problem iff there exists a stable extension such that s.t. , and such that .8
Attacks are added to the AAF in the same way as in  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 cannot represent a (perfect) matching. The proof then proceeds in the same way as in . □
As an example of non-existence, if we consider the preference lists in Fig. 3 and we remove the entry between and , the only stable extension is , 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 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 a framework representing an problem and using in Definition 3.2, is a weakly-stable solution of the problem iff is a stable extension in F.
If (a tie with respect to , or a tie with respect to ), a symmetric attack10 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 . □
Theorem 4.4(Equivalence and super-stability).
Being a framework representing an problem and using in Definition 3.2, is a weakly-stable solution of the problem iff is a stable extension such that such that , and such that always exists.
If (a tie with respect to , or a tie with respect to ), 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 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 and , and between and . 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 as a non-valid solution, as a result that framework has no super-stable matching.
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 problem, a corresponding AAF is , and such that iff
and , or
Corollary 4.6(Equivalence, incomplete lists, and weak-stability).
Being a framework representing an problem and assembled as in Definition 4.5, is a weakly-stable solution of the problem iff is a stable extension in F.
As as result of Theorem 4.4, by only replacing with we can find super-stable matchings. The tables of preferences in Fig. 10 represent an example of problem with six men and six women. We still suppose to use the Weighted c-semiring () to model preferences in 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., ): , , , , miss because of incomplete preference lists. This framework has 128 attacks. We computed the stable extensions by using ConArg11 [6,7,10]: the obtained graph is represented in Fig. 11, within the ConArg Web-interface environment. ConArg returns three stable extensions:
The three solutions are the same as what obtained on the same case-study by using an Integer Logic Programming approach in , hence validating the result in the practice.
If we assemble the framework with the purpose to model weak stability (hence using instead of ), we obtain one more matching (for a total of four weakly-stable matchings):
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 and a function that we use to compose and . We use f to find the overall preference if we match with , i.e., if , 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).
By embedding the Weighted c-semiring and with (the arithmetic addition) we obtain the egalitarian cost in Equation (1). By instead using the Fuzzy c-semiring and , we can model the regret cost in Equation (2).
Moreover, we can also represent man and woman optimality by using the Weighted c-semiring , 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: ,
while for women-optimality: .
We now formally describe what introduced above:
Definition 5.1(OSMTI to weighted frameworks).
Given an problem, a c-semiring , and preference composition operator , a corresponding weighted framework is , and such that iff
and , or
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
by using and the Weighted c-semiring;
by using and the Fuzzy c-semiring;
by using and the Weighted c-semiring;
by using and the Weighted c-semiring.
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 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 . By composing such a preference with a Cartesian product of two Weighted c-semirings,12 in the end all stable extensions will have a cost of
We consider again the four weakly-stable matchings obtained on the example represented by the preferences in Fig. 10:
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 version of ConArg.14 In this way, it is possible to run ConArg on any platform (Linux, Mac OSX, Windows) and then use a Python library15 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 , 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 , and for women’s preference is . As expected, man-optimality corresponds to the worst preference possible for women, and vice-versa.
5.2.Preference values on attacks
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 , it consequently models weakly-stable marriages.
Definition 5.3(OSMTI to WAAFs).
Given an problem over and preference composition operator , a corresponding WAAF described by is composed by:
such that with iff
∗ and , or
∗ and .
such that then : contains all and only self-attacks on the arguments in . The cost of self attacks is
By relaxing the internal inconsistency α,16 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 . 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.
Being a WAAF representing an problem obtained through Definition 5.3, is a weakly-stable solution of the problem with cost better/equal than α iff is an -stable extension in .
Attacks are oriented as in the formalisation given by Dung : 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 -stable extension on the WAAFs created according to Definition 5.3, and obtained from the OSMTI problem in Fig. 10. Clearly, by setting we obtain two more weakly-stable matchings, and in Table 1, whose cost is 32 and 30 respectively ( is super-stable instead).
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 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  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 : 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 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 needs to be paid, and this value is definitely worse than each possible matching, which contains no more than half of the arguments: therefore, 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 composed (using ⊗) with the difference (using ⊘) between the worse and the better preference values: . 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 is 24, which is equal to the sum of self-attacks. The formal description of it is instead represented by Definition 5.5.
Definition 5.5(From relaxed OSMTI to WAAFs).
Given an problem over and preference composition operator , a corresponding WAAF is composed by:
such that with iff
∗ and , or
∗ and .
such that for each there exists , and
∗ iff , or
∗ iff .
such that there exists such that
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 -stable-extensions, that is with and (in this example, we have that ):
with an egalitarian cost of 29,
with an egalitarian cost of 27,
with an egalitarian cost of 26.
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 (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 . In the future we will explore different notions of relaxation and formalise a distance from classical unrelaxed solutions (see Section 7).
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 , 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 , if there is a love triangle between , , and ( loves , who loves , who loves ), 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 . 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 The SM problem can be considered as a basic game without transferable utility . Cooperative Game Theory (mostly developed, as the SM problem itself, by Lloyd S. Shapley) is based on coalition building and usage of transferable utility . 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 , where 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 .
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
Papers measuring the strength of arguments are reported in the following. In  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  the authors propose a way to compute the relative relevance of arguments by merging Abstract Argumentation  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  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  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  extends  by exploiting the preferred semantics to compute outcomes, instead of the grounded one.
The authors of  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 , where Strategic Argumentation20 is studied by using opponent models, that is recursive representations of agent’s knowledge and beliefs regarding the opponent’s knowledge.
In this paper we have worked along one of the several directions pioneered in the ’95 seminal work by P.M. Dung , 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  (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 .
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.
1 Boolean c-semirings can be used to model Abstract Argumentation à-la-Dung .
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, , i.e., lesser means better.
3 is complete if it is closed with respect to infinite sums, and the distributivity law holds also for an infinite number of summands.
4 Conversely, and/or if p is defined on that couple.
5 Note that, since the set of preferences is in general partially ordered in a c-semiring, a strict 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.
6 in case their cardinality n is the same.
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).
10 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.
11 ConArg Website: http://www.dmi.unipg.it/conarg/.
12 The Cartesian product of c-semirings is still a c-semiring (see ).
13 Docker: https://www.docker.com.
14 The Docker image of ConArg is downloadable from the repository with command docker pull iccma19/conarg.
15 Docker SDK for Python: https://docker-py.readthedocs.io.
16 See Section 2.1: α limits the cost of all the attacks included in an extension (aggregated through ⊗).
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.
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).
20 In Strategic Argumentation, an agent employs a strategy, typically in the form of a heuristic, which selects appropriate arguments given some contextual knowledge.
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).
P. Biró, The stable matching problem and its generalizations: An algorithmic and game theoretical approach, PhD thesis, Budapest University of Technology and Economics, 2007.
S. Bistarelli, S.N. Foley, B. O’Sullivan and F. 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.
S. Bistarelli, P. Giuliodori, F. Santini and C. Taticchi, A cooperative-game approach to share acceptability and rank arguments, in: Proceedings of the 2nd Workshop on Advances in Argumentation in Artificial Intelligence, AI3@AI*IA, CEUR Workshop Proceedings, Vol. 2296, CEUR-WS.org, 2018, pp. 86–90.
S. Bistarelli, U. Montanari and F. Rossi, Semiring-based constraint satisfaction and optimization, Journal of the ACM 44(2) (1997), 201–236. doi:10.1145/256303.256306.
S. Bistarelli, F. Rossi and F. 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.
S. Bistarelli, F. Rossi and F. 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.
S. Bistarelli, F. Rossi and F. 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.
S. Bistarelli, F. Rossi and F. Santini, A novel weighted defence and its relaxation in abstract argumentation, Int. J. Approx. Reasoning 92 (2018), 66–86. doi:10.1016/j.ijar.2017.10.006.
S. Bistarelli and F. 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.
S. Bistarelli and F. 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.
E. Black and K. Atkinson, Choosing persuasive arguments for action, in: 10th International Conference on Autonomous Agents and Multiagent Systems AAMAS, IFAAMAS, 2011, pp. 905–912.
T.S. Blyth and M.F. Janowitz, Residuation Theory, Vol. 102, Pergamon Press, Oxford, 1972.
E. Bonzon, N. Maudet and S. 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.
M. Caminada, W.A. Carnielli and P.E. Dunne, Semi-stable semantics, J. Log. Comput. 22(5) (2012), 1207–1254. doi:10.1093/logcom/exr033.
S. Coste-Marquis, S. Konieczny, P. 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.
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.
D. Fudenberg and J. Tirole, Game Theory, MIT Press, Cambridge, MA, 1991.
D. Gale and L.S. Shapley, College admissions and the stability of marriage, The American Mathematical Monthly 69(1) (1962), 9–15. doi:10.1080/00029890.1962.11989827.
D. Gusfield, Three fast algorithms for four problems in stable marriage, SIAM J. Comput. 16(1) (1987), 111–128. doi:10.1137/0216010.
D. Gusfield and R.W. Irving, The Stable Marriage Problem: Structure and Algorithms, MIT Press, Cambridge, MA, USA, 1989. ISBN 0-262-07118-5.
A. 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.
R.W. Irving, Stable marriage and indifference, Discrete Applied Mathematics 48(3) (1994), 261–272. doi:10.1016/0166-218X(92)00179-P.
R.W. Irving and P. Leather, The complexity of counting stable marriages, SIAM J. Comput. 15(3) (1986), 655–667. doi:10.1137/0215048.
R.W. Irving, P. Leather and D. Gusfield, An efficient algorithm for the “optimal” stable marriage, J. ACM 34(3) (1987), 532–543. doi:10.1145/28869.28871.
K. Iwama and S. 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.
K. Iwama, S. Miyazaki and H. 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.
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.
B.M. Maggs and R.K. Sitaraman, Algorithmic nuggets in content delivery, Computer Communication Review 45(3) (2015), 52–66. doi:10.1145/2805789.2805800.
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.
P. Matt and F. 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.
O. Morgenstern and J. Von Neumann, Theory of Games and Economic Behavior, Princeton University Press, 1953.
S. Pan, K. Larson and I. 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.
M.S. Pini, F. Rossi, K.B. Venable and T. Walsh, Stability, optimality and manipulation in matching problems with weighted preferences, Algorithms 6(4) (2013), 782–804. doi:10.3390/a6040782.
B. Pittel, The average number of stable matchings, SIAM J. Discrete Math. 2(4) (1989), 530–549. doi:10.1137/0402048.
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.
I. Rahwan and K. Larson, Mechanism design for abstract argumentation, in: 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), IFAAMAS, 2008, pp. 1031–1038.
T. Rienstra, M. Thimm and N. 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.
F. Rossi, P. van Beek and T. Walsh (eds), Handbook of Constraint Programming, Foundations of Artificial Intelligence, Vol. 2, Elsevier, 2006.
A.E. Roth, The Shapley Value: Essays in Honor of Lloyd S. Shapley, Cambridge University Press, 1988.
G.R. Simari and I. Rahwan (eds), Argumentation in Artificial Intelligence, Springer, 2009. ISBN 78-0-387-98196-3. doi:10.1007/978-0-387-98197-0.