Abstract argumentation and (optimal) stable marriage problems

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:

With respect to the WAAFS 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:

Still considering Fig. 1, the set {d,e} is 111-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 WAAFS.

For example, considering Fig. 1, the set {a,d} corresponds to the single 01-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).

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={m1,m2,…,mn} and W={w1,w2,…,wn}, with M∩W=∅ (i.e., the sets are disjoint). Associated with each element in M∪W is a strictly ordered preference list containing all the elements in the other set: wk≻miwj means that mi prefers wk to wj, where ≻mi is a strict total order on W (i.e., a total ranking on W). We define a matching as MT⊆{(m,w)∣m∈M,w∈W} such that each x∈M∪W appears exactly once in MT. A pair (mi,wj) is blocking in a matching MT iff ∃mk, wl such that wl≻miwj and mk≻wjmi. MT is stable if ∀(mi,wj)∈MT, (mi,wj) is not blocking.

We initially define p:M∪W×M∪W→Nn (with n=|M|=|W| and Nn={1,…,n}): p(x,y) is a function that returns the ordinal position of y in the preference list of x, e.g., p(mi,wj)=1 if wj is the most preferred woman, while p(mi,wk)=n if wk is the least preferred woman: 1 represents the best position in the ranking. Same considerations hold for p(wj,mi), that is the preference of wj for mi.

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(n2)-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−1nlnn [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(mi,wj) represents the rank of wj in mi’s list of preferences. Therefore, we need to minimise the egalitarian cost [24] in Equation (1):

A third criterion consists in minimising the sex-equalness cost [26], as represented in Equation (3):

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:

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, SMS 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 (mi,wj) for which p is not defined, i.e., p(mi,wj)↑ and/or p(wj,mi)↑.44 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]:

Fig. 2.

An OSM problem represented as a bipartite graph. Preference lists are complete and with ties (w.r.t. m2).

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 SMS problem with two men and two women, as a bipartite graph. We suppose to use the Weighted c-semiring: S=⟨R+∪{+∞},min,+,+∞,0⟩. The lists of preference are complete and with ties (that is an SMT problem): m2 shows the same preference for w1 and w2. For instance, the matching {(m1,w2),(m2,w1)} is not weakly (then neither strongly nor super) stable because (m1,w1) is a blocking pair: p(m1,w1)>Sp(m1,w2)∧p(w1,m1)>Sp(w1,m2), i.e. 1>S4∧1>S5.

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=⟨Args,R⟩ as follows: wz represents a threat to a marriage (mi,wj) if mi prefers wz to wj. In other words, a hypothetical marriage of mi to wz poses an attack to the couple (mi,wj). But this attack is eliminated if wz is married to someone whom wz prefers to mi.

To assemble a framework representing a SM problem, the set of arguments Args has cardinality |M|·|W|,66 and each argument is labelled by using an element from the set of men, and one from the set of women:

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

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.

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

The following corollary derives from the complexity of enumerating stable matchings.

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

In addition, the following statement relates the presence of some pairs in all possible matchings.

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 {(m1,w2),(m2,w1)}.

Fig. 3.

An SM problem given in tabular form, with men preferences on the left and women preferences on the right, e.g., p(m1,w1)=1 and p(w2,m1)=2.

Fig. 4.

The AAF encoding of the SM problem in Fig. 3. The only stable extension is {(m1,w2),(m2,w1)}.

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.

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 n2 arguments if the preference lists are incomplete. On the other hand, the attack relation R is defined as for the case with complete lists.77

Figure 5 presents an example of an incomplete list for m2, 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 m2 expresses no preference for w1.

Fig. 6.

The AAF encoding of the SM problem in Fig. 5. The only stable extension is {(m1,w1),(m2,w2)}. Argument (m2,w1) does not belong to the framework because of the missing preference.

As an example of non-existence, if we consider the preference lists in Fig. 3 and we remove the entry between m1 and w2, the only stable extension is {(m2,w1)}, 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).99 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.

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).

An example of SMTS 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 (m1,w1) and (m2,w1), and between (m2,w1) and (m2,w2). 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 {(m1,w1),(m2,w1),(m2,w2)} 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 m2 and w1), 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 {(m1,w1),(m2,w2)} and {(m1,w2),(m2,w1)}.

Fig. 9.

The AAF encoding of the SMT problem in Fig. 7, using super-stability. The only stable extension {(m1,w1),(m2,w1),(m2,w2)}, 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.

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 SMTIS problem with six men and six women. We still suppose to use the Weighted c-semiring (S=⟨R+∪{+∞},min,+,+∞,0⟩) to model preferences in SMTIS 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., n2): (m1,w3), (m3,w2), (m3,w5), (m5,w4), (m6,w2) miss because of incomplete preference lists. This framework has 128 attacks. We computed the stable extensions by using ConArg1111 [6,7,10]: the obtained graph is represented in Fig. 11, within the ConArg Web-interface environment. ConArg returns three stable extensions:

Fig. 10.

A larger SMTIS 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):

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,⊕,⊗,⊥,⊤⟩ and a function f:S×S→S that we use to compose p(mi,wj) and p(wj,mi). We use f to find the overall preference if we match mi with wj, i.e., if (mi,wj)∈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).

By embedding the Weighted c-semiring ⟨R+∪{+∞},min,+,+∞,0⟩ and with f≡+ (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≡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+∪{+∞},min,+,+∞,0⟩, and a function f that always return the first (man-optimal) or second (woman-optimal) component of the considered couple of preferences.

We now formally describe what introduced above:

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

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(mi,wj),p(wj,mi)⟩. By composing such a preference with a Cartesian product of two Weighted c-semirings,1212 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 dockerised1313 version of ConArg.1414 In this way, it is possible to run ConArg on any platform (Linux, Mac OSX, Windows) and then use a Python library1515 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 MT1, 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 MT4, and for women’s preference is MT3. As expected, man-optimality corresponds to the worst preference possible for women, and vice-versa.