Lifting preferences over alternatives to preferences over sets of alternatives: The complexity of recognizing desirable families of sets

Jan Maly*

*Korrespondierende*r Autor*in für diese Arbeit

Publikation: Beitrag in Buch/KonferenzbandBeitrag in Konferenzband

Abstract

The problem of lifting a preference order on a set of objects to a preference order on a family of subsets of this set is a fundamental problem with a wide variety of applications in AI. The process is often guided by axioms postulating properties the lifted order should have. Well-known impossibility results by Kannai and Peleg and by Barberà and Pattanaik tell us that some desirable axioms - namely dominance and (strict) independence - are not jointly satisfiable for any linear order on the objects if all non-empty sets of objects are to be ordered. On the other hand, if not all non-empty sets of objects are to be ordered, the axioms are jointly satisfiable for all linear orders on the objects for some families of sets. Such families are very important for applications as they allow for the use of lifted orders, for example, in combinatorial voting. In this paper, we determine the computational complexity of recognizing such families. We show that it is Πp2-complete to decide for a given family of subsets whether dominance and independence or dominance and strict independence are jointly satisfiable for all linear orders on the objects if the lifted order needs to be total. Furthermore, we show that the problem remains coNP-complete if the lifted order can be incomplete. Additionally, we show that the complexity of these problem can increase exponentially if the family of sets is not given explicitly but via a succinct domain restriction.

OriginalspracheEnglisch
Titel des SammelwerksProceedings of the 34th AAAI Conference on Artificial Intelligence
Untertitel des SammelwerksAAAI-20 Technical Tracks 2
ErscheinungsortWashington, DC
VerlagAAAI Press
Seiten2152-2159
Seitenumfang8
ISBN (elektronisch)9781577358350
DOIs
PublikationsstatusVeröffentlicht - 2020
Extern publiziertJa
Veranstaltung34th AAAI Conference on Artificial Intelligence, AAAI 2020 - New York, USA/Vereinigte Staaten
Dauer: 7 Feb. 202012 Feb. 2020

Publikationsreihe

ReiheProceedings of the AAAI Conference on Artificial Intelligence
Nummer2
Band34
ISSN2159-5399

Konferenz

Konferenz34th AAAI Conference on Artificial Intelligence, AAAI 2020
Land/GebietUSA/Vereinigte Staaten
OrtNew York
Zeitraum7/02/2012/02/20

Bibliographische Notiz

Publisher Copyright:
Copyright © 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Zitat