An improved algorithm for testing substitutability of weak preferences

Susumu Kawanaka, Naoyuki Kamiyama

Research output: Contribution to journalArticlepeer-review


In this paper, we consider the problem of testing substitutability of weak preferences. For this problem, Aziz, Brill, and Harrenstein proposed an O(ℓ 3 u 2 +ℓ 2 u 2 s 2 )-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(ℓ 3 u+ℓ 2 u 2 s)-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.

Original languageEnglish
Pages (from-to)1-4
Number of pages4
JournalMathematical Social Sciences
Publication statusPublished - May 2019

All Science Journal Classification (ASJC) codes

  • Sociology and Political Science
  • General Social Sciences
  • General Psychology
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'An improved algorithm for testing substitutability of weak preferences'. Together they form a unique fingerprint.

Cite this