Ordinal dominance with binary interactions for subset choice: axiomatic analysis and complexity issues

Ravier, Ariane; Gilbert, Hugo; Ozturk, Meltem; Spanjaard, Olivier

Ravier, Ariane; Gilbert, Hugo; Ozturk, Meltem; Spanjaard, Olivier (2022), Ordinal dominance with binary interactions for subset choice: axiomatic analysis and complexity issues, M-pref 2022: 13th Multidisciplinary Workshop on Advances in Preference Handling, 2022-07, Vienna, Austria

Type

Communication / Conférence

External document link

https://hal.archives-ouvertes.fr/hal-03812006

Date

2022

Conference title

M-pref 2022: 13th Multidisciplinary Workshop on Advances in Preference Handling

Conference date

2022-07

Conference city

Vienna

Conference country

Austria

Metadata

Show full item record

Author(s)

Ravier, Ariane
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Gilbert, Hugo
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ozturk, Meltem
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Spanjaard, Olivier
LIP6

Abstract (EN)

The article focuses on a subset comparison model introduced by Fishburn and LaValle [1996], called ordinal dominance (with binary interactions). After giving an axiomatic analysis pointing out several differences between the studied model and one without interactions, we investigate the problem of determining non-dominated subsets from an algorithmic point of view, with a complexity result (determining if a given subset is non-dominated is co-NP-complete), and present an algorithm to determine a non-dominated subset in polynomial time.