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.

Abstract argumentation and (optimal) stable marriage problems

Bistarelli S.;Santini F.
2020

Abstract

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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1479751
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact