We show how different multi-dimensional extensions of the stable matching (or marriage) problem can be represented by Abstract Argumentation frameworks: the set of stable extensions exactly corresponds to the set of solutions in the original problem. We show how to allow incomplete preference lists and ties in the same problems, and consequently frameworks. All the proposed problems are NP-Complete or NP-Hard: efficient stable-semantics solvers can help their solutions, and in general cross-fertilisation can benefit both the fields.
Multi-dimensional Stable Matching Problems in Abstract Argumentation
Santini F.
2020
Abstract
We show how different multi-dimensional extensions of the stable matching (or marriage) problem can be represented by Abstract Argumentation frameworks: the set of stable extensions exactly corresponds to the set of solutions in the original problem. We show how to allow incomplete preference lists and ties in the same problems, and consequently frameworks. All the proposed problems are NP-Complete or NP-Hard: efficient stable-semantics solvers can help their solutions, and in general cross-fertilisation can benefit both the fields.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
