Given a set U of alternatives, a choice (correspondence) onU is a contractivemap c defined on a family W of nonempty subsets of U. Semantically, a choice c associates to each menu A ∈ W a nonempty subset c(A) ⊆ A comprising all elements of A that are deemed selectable by an agent. A choice on U is total if its domain is the powerset of U minus the empty set, and partial otherwise. According to the theory of revealed preferences, a choice is rationalizable if it can be retrieved from a binary relation on U by taking all maximal elements of each menu. It is well-known that rationalizable choices are characterized by the satisfaction of suitable axioms of consistency, which codify logical rules of selection within menus. For instance, WARP (Weak Axiom of Revealed Preference) characterizes choices rationalizable by a transitive relation. Here we study the satisfiability problem for unquantified formulae of an elementary fragment of set theory involving a choice function symbol c, the Boolean set operators and the singleton, the equality and inclusion predicates, and the propositional connectives. In particular, we consider the cases in which the interpretation of c satisfies any combination of two specific axioms of consistency, whose conjunction is equivalent to WARP. In two cases we prove that the related satisfiability problem is NP-complete, whereas in the remaining cases we obtain NP-completeness under the additional assumption that the number of choice terms is constant.

The satisfiability problem for boolean set theory with a choice correspondence

CANTONE, Domenico;GIARLOTTA, Alfio;
2017-01-01

Abstract

Given a set U of alternatives, a choice (correspondence) onU is a contractivemap c defined on a family W of nonempty subsets of U. Semantically, a choice c associates to each menu A ∈ W a nonempty subset c(A) ⊆ A comprising all elements of A that are deemed selectable by an agent. A choice on U is total if its domain is the powerset of U minus the empty set, and partial otherwise. According to the theory of revealed preferences, a choice is rationalizable if it can be retrieved from a binary relation on U by taking all maximal elements of each menu. It is well-known that rationalizable choices are characterized by the satisfaction of suitable axioms of consistency, which codify logical rules of selection within menus. For instance, WARP (Weak Axiom of Revealed Preference) characterizes choices rationalizable by a transitive relation. Here we study the satisfiability problem for unquantified formulae of an elementary fragment of set theory involving a choice function symbol c, the Boolean set operators and the singleton, the equality and inclusion predicates, and the propositional connectives. In particular, we consider the cases in which the interpretation of c satisfies any combination of two specific axioms of consistency, whose conjunction is equivalent to WARP. In two cases we prove that the related satisfiability problem is NP-complete, whereas in the remaining cases we obtain NP-completeness under the additional assumption that the number of choice terms is constant.
2017
Axioms of choice consistency; Choice; Decidability; NP-completeness; WARP; Software
File in questo prodotto:
File Dimensione Formato  
CantoneGiarlottaWatson2017.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Documento in Post-print
Dimensione 211.67 kB
Formato Adobe PDF
211.67 kB Adobe PDF Visualizza/Apri

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/20.500.11769/313011
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 0
social impact