An improved algorithm for testing substitutability of weak preferences

Susumu Kawanaka and Naoyuki Kamiyama

Mathematical Social Sciences, 2019, vol. 99, issue C, 1-4

Abstract: In this paper, we consider the problem of testing substitutability of weak preferences. For this problem, Aziz, Brill, and Harrenstein proposed an O(ℓ3u2+ℓ2u2s2)-time algorithm, where u is the size of the ground set, ℓ is the number of acceptable sets, and s is the maximum size of an equivalent class. In this paper, we propose an O(ℓ3u+ℓ2u2s)-time algorithm for this problem. Our algorithm is based on a generalization of the characterization of substitutability of strict preferences given by Croitoru and Mehlhorn.

Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165489619300150
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matsoc:v:99:y:2019:i:c:p:1-4

DOI: 10.1016/j.mathsocsci.2019.02.003

Access Statistics for this article

Mathematical Social Sciences is currently edited by J.-F. Laslier

More articles in Mathematical Social Sciences from Elsevier
Bibliographic data for series maintained by Catherine Liu ().