An Abstract Argumentation Based Study Of Stable Matching Problems

The stable matching problem (hereafter referred to as SM) has been a hot issueinareas such as mathematics, operational research, economics and sociology. It is often presented as matrix, which determines that its computation approaches are mostly combinatorial, relying very much on its order and only suitable for computing a single stable matching which is men-optimal (all men get their best choice) or women-optimal (all women get their best choice). Graph theory is also used to analyse SM and compute stable matchings, mainly focusing on the structure of SM and computing by finding bipartite subgraphes with certain characteristics. Both combinatorial and graph approaches lack logically strict formalizations and the computation are highly abstract. Besides, they cannot judge the status of single pairs, for a pair is stable when it isina stable matching, we cannot decide its stability until computing a whole stable matching. SM problems are prone to nonmonotonicity, previous approaches mainly analyse which agent will get better or worse, while they have not touched upon and are not flexible to the recomputation of stable mathcings.Abstract argumentation theory is ideal to improve the above situations. Stable matching problem is a select-evaluate-reselect-reevaluate process among conflict choices, which can well be captured and formalized by the abstract argumentation framework.Compared with combinatorials and graph theory, abstract argumentation theory is more close to our reasoning process. We abstract single pairs to arguments and the preference parameters among agents to binary attacks between arguments, thus we can start from any argument. There are several ready computational approaches of argumentation semantics, for example, the answer-set-programming based approach (ASP), the labelling-based approach (MC), the strongly connected components approach (SCC) and the mostly rejected arguments approach (MSR). We can improve the computation of stable matching by improving semantics algorithms or adopting existing efficient approaches. For instance, SCC-based approach divides an argumentation framework to small SCCs, computes the partial semantics of each SCCs and finally combines them, improving the computational efficiency a lot for argumentation frameworks within a certain density; the MSR approach reduces computational size by deleting the mostly rejected arguments from the very beginning of computation, which strengthens the high efficiency of SCC approaches. By argumentation frameworks, we can compute all stable matchings of an SM problem and these matchings are not sex-optimal for the stable marriage problem (of course, the men-optimal and women optimal matchings are alsoinall stable matchings). For single pairs, we can decide their stability by argumentation dispute trees: whether a pair belongs to at least one stable matching or belongs to all stable matchings. When there are changes to SM problems:addition or deletion of pairs, change of preference lists, we can analyse differencesinthe number and content of stable matchings and can recompute stable matchings efficiently by results of argumentation dynamics.Our research is structured accordingly. The abstract argumentation framework (hereafter to referred as AF) is first introducedina certain depth, including argumentation semantics and two different definitions-the extension-based and the labelling-based approaches. In the second part, we use AAF to formalize SM problems and restrict our research to the following types:stable marriage problems and stable roommate problems with complete and non-indifferent preference lists (hereafter referred to as sm and sr respectively), stable marriage problems and stable roommate problemswith complete and indifferent preference lists (hereafter referred to as smt and srt respectively), stable marriage problems and stable roommate problems with incomplete and non-indifferent preference lists (hereafter referred to as smi and sri respectively), stable marriage problems and stable roommate problems with incomplete and indifferent preference lists (hereafter referred to as smti and srti respectively).The argumentation frameworks may have odd cycles and may not have stable semantics, while the argumentation frameworks of SM problems with complete preference lists have no odd cycles. Besides computing a whole stable matching, we can decide the stability of single pairs by dispute trees. Based on the static analysis and computation, we study the dynamics of SM problems: how the number and the content of stable matchings vary according to the addition, deletion and change of preference lists, and finally the recomputation of stable matchings.From analysis, we proved that stable extensions and preferred extensions are stable matchings of the corresponding SMs and we can always compute stable matchings by argumentation semanticsincase there are stable matchings. For single pairs, if the corresponding arguments are not credulously justified under certain semantics, then they belong to no stable matchings. The argumentation frameworks of SMs have their own characteristics:each pair relates to all the others directly or indirectly, thus it is hardly for us to divide them into SCCs ; and with the labelling-based approach we have to go between the argument sets of different status to judge whether they are legally labelled, while the computing of non- SM frameworks only has to move illegally justified arguments from the justified set to the unjustified set and the illegally unjustified arguments to undetermined set. We try the extension-based MSR approach, starting from each argument and see whether there is a maximal admissible set. For the recomputation of dynamic SM problems, we propose an argument-status-based way based on the division approach to further reduce the size that needs recomputation.