An Introduction to Optimal Stable Marriage Problems and Argumentation Frameworks?

Abstract

In the Stable Marriage (SM) problem, given two sets of individuals partitioned into men and women, a matching is stable when there does not exist any matching man-woman by which both man and woman would be individually better off than they are with the person to which they are currently matched. In 1995, P.M. Dung modelled stable matchings as stable extensions in Abstract Argumentation Frameworks. In this paper we elaborate on the original formulation by using Weighted Abstract Argumentation to also represent optimality criteria in Optimal SM problems, where some matchings are better than others: criteria may consider only the preference of either men, or women, or a more balanced view obtained by differently combining the preferences of both of them.

Introduction

Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons

License Attribution 4.0 International (CC BY 4.0).

Optimal Stable Marriage Problems

The classical SM problem was extended [ 4 ] in order to find an SM problem under a more equitable measure of optimality, thus defining an Optimal SM problem [ 5, 7, 8, 10 ]. For example, in [ 7 ] the authors maximise the global satisfaction by summing together the preferences of both men and women in a matching. This sum has to be minimised, since p(mi, w j) represents the rank of w j in mi’s list of preferences. Therefore, we need to minimise this egalitarian cost1 [ 7 ] in Eq. 1: min

max (mi,w j)2 MT

max{p(mi, w j), p(w j, mi)} A third criterion consists in minimising the sex-equalness cost [ 9 ]: 0

 (mi,w j)2 MT p(mi, w j) +

 (mi,w j)2 MT p(w j, mi)A 1 Such an optimisation problem was originally posed by D. Knuth [ 7 ]. Other optimisation criteria are represented by minimizing the regret cost [ 5 ], as represented in Eq. 2: (1) (2) (3) min

 (mi,w j)2 MT p(mi, wi)

 (mi,w j)2 MT p(w j, mi)

Finding a solution satisfying Eq. 1 and Eq. 2 already found their solution in polynomial time by using ad-hoc algorithms, such as [ 5 ] and [ 7 ], respectively. On the contrary, reaching the optimality represented by Eq. 3 was proved to be an NP-hard problem for which approximation algorithms are proposed [ 9 ].

An SM problem formulation has incomplete lists (SMI) if an individual can exclude a partner whom she/he does not want to be matched with [ 8 ] (some preferences are omitted). In this case, a (perfect) matching of all men or women may not exist. A further extension is represented by problems where it is possible to express the same preference for more than one possible partner: the problem is usually named as “SM with ties” [ 8 ] (SMT). In this case, three stability notions are proposed in the literature [ 8 ]: – given (mi, w j) and (mk, wz), in a super stable matching a pair (mi, wz) is blocking iff p(mi, wz) S p(mi, w j) ^ p(wz, mi) S p(wz, mk);2 – in a strongly stable matching a pair (mi, wz) is blocking iff p(mi, wz) >S p(mi, w j) ^ p(wz, mi) S p(wz, mk) or p(mi, wz) S p(mi, w j) ^ p(wz, mi) >S p(wz, mk); – in a weakly stable matching a pair (mi, wz) is blocking iff p(mi, wz) >S p(mi, w j) ^ p(wz, mi) >S p(wz, mk).

The solution of SMTI problems is proved to be an NP-complete problem [ 8 ]. 1 Simply a cost that combines the preferences of both men and women. 2 S means “better than”, according to a c-semiring S (see Sect. 3).

Preference on Arguments

In this section we model the three optimality criteria in Sect. 2 by labelling arguments with weights as performed in [ 1 ]. We use c-semirings and their operators to model preference values and find the best stable extension.

A c-semiring is an algebraic structure to model preferences, generically defined by the tuple S = hS, , ⌦ , ? , >i. 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 t = t, and returns the least upper bound of s and t. This intuitively means that t is “better” than s. is used to compose values, while ? , > 2 S represent the best and worst preference respectively [ 1 ].

All criteria can be captured by using a c-semiring and a side function f : S ⇥ S ! S that we use to compose p(mi, w j) and p(w j, mi). We use f to find the overall preference if we match mi with w j, i.e., if (mi, w j) 2 MT, that is the combined man-woman/womanman preference. The general parametric formula is:

M 0

By embedding the Weighted c-semiring hR+ [ { +• }, min, +, +• , 0i and with f ⌘ + (the arithmetic addition) we obtain the egalitarian cost in Eq. 1. By instead using the Fuzzy c-semiring h[ 0, 1 ], max, min, 0, 1i and f ⌘ max, we can exactly model the regret cost in Eq. 2. Moreover, we can also represent man and woman optimality (thus obtaining the best solution for either men or women) by using the Weighted c-semiring hR+ [ { +• }, min, +, +• , 0i, 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: fmo(p(mi, w j), p(w j, mi)) ! p(mi, w j), and for womenoptimality: fwo(p(mi, w j), p(w j, mi)) ! p(w j, mi).

We formally encode OSMTI to weighted AFs in Def. 1. In Tab. 1 we represent a SMTIS problem in tabular form, considering a (Weighted) semiring S: Definition 1 (OSMTI to weighted frameworks). Given a SMTIS, a c-semiring S = hS, , ⌦ , ? , >i, and preference composition operator f : S ⇥ S ! S, a correspondw1 w2 w3 w4 w5 w6 m1 1 4 - 5 5 3 m2 3 4 6 1 5 2 m3 1 - 4 2 3 5 m4 6 1 3 4 2 1 m5 3 1 2 4 5 6 m6 3 3 1 6 5 4 ing weighted argumentation framework is Args = {(m ⇥ w) | m 2 M, w 2 W, p(m, w) # ^ p(w, m) #}, and R ✓ Args ⇥ Args s.t. R((mk, wl ), (mi, w j)) iff – i = k and p(mi, wl ) S p(mi, w j), or – j = l and p(w j, mk) S p(w j, mi). and each argument (mi, w j) in the obtained framework is labelled with a preference given by f (p(mi, w j), p(w j, mi).

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

Proposition 1 (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 1, optimises the egalitarian cost: by using f ⌘ + and the Weighted c-semiring; regret cost: by using f ⌘ max and the Fuzzy c-semiring; man-optimality: by using f ⌘ fmo and the Weighted c-semiring; woman-optimality: by using f ⌘ fwo and the Weighted c-semiring.

Note that sex-equalness 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 hp(mi, w j), p(w j, mi)i. By composing such preference with a Cartesian product of two Weighted c-semiring,3 in the end all stable extensions will have a cost of h (mi,w j)2 MT p(mi, w j),  (mi,w j)2 MT p(w j, m j)i, which can be finally optimised to find the sex-equalness cost.

Four weakly-stable matchings (see Sect. 3) can be found the example in Fig. 1: – MT1 = {(m1, w1), (m2, w2), (m3, w4), (m4, w5), (m5, w6), (m6, w3)}, – MT2 = {(m1, w1), (m2, w2), (m3, w4), (m4, w6), (m5, w5), (m6, w3)}, – MT3 = {(m1, w1), (m2, w2), (m3, w4), (m4, w3), (m5, w6), (m6, w5)}, – MT4 = {(m1, w1), (m2, w6), (m3, w4), (m4, w2), (m5, w5), (m6, w3)}.

Conclusion

In this paper we elaborated one of the directions pioneered in the ’95 seminal work by P.M. Dung [ 3 ]: the strong ties between Abstract Argumentation (and better, the stable semantics) and the Stable Marriage problem. As far as we know, except for Dung’s paper, this topic was not investigated in successive studies.

In the future we plan to study closely related problems: examples 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. A connection to previous works on the formation of argument coalitions is also possible [ 2 ].

References

1. Bistarelli , S. , Pirolandi , D. , Santini , F. : Solving weighted argumentation frameworks with soft constraints . In: Recent Advances in Constraints, Revised Selected Papers. LNCS , vol. 6384 , pp. 1 - 18 . Springer ( 2009 )

2. Bistarelli , S. , Santini , F. : Coalitions of arguments: An approach with constraint programming . Fundam. Inform . 124 ( 4 ), 383 - 401 ( 2013 )

3. Dung , P.M. : On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games . Artif. Intell . 77 ( 2 ), 321 - 357 ( 1995 )

4. Gale , D. , Shapley , L.S.: College admissions and the stability of marriage . The American Mathematical Monthly 69 ( 1 ), 9 - 15 ( 1962 )

5. Gusfield , D. : Three fast algorithms for four problems in stable marriage . SIAM J. Comput . 16 ( 1 ), 111 - 128 ( 1987 )

6. Gusfield , D. , Irving , R.W.: The stable marriage problem: structure and algorithms . MIT Press, Cambridge, MA, USA ( 1989 )

7. Irving , R.W. , L., P. , Gusfield , D.: An efficient algorithm for the “optimal” stable marriage . J. ACM 34 ( 3 ), 532 - 543 ( 1987 )

8. Iwama , K. , Miyazaki , S.: A survey of the stable marriage problem and its variants . In: International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008 ). pp. 131 - 136 . IEEE Computer Society ( 2008 )

9. Iwama , K. , Miyazaki , S. , Yanagisawa , H.: Approximation algorithms for the sex-equal stable marriage problem . In: Algorithms and Data Structures , 10th International Workshop, WADS. LNCS, vol. 4619 , pp. 201 - 213 . Springer ( 2007 )

10. Knuth , D.E. : Stable marriage and its relation to other combinatorial problems: An introduction to the mathematical analysis of algorithms . American Mathematical Society ( 1997 )