An improved algorithm for testing substitutability of weak preferences

Susumu Kawanaka; Naoyuki Kamiyama

doi:10.1016/j.mathsocsci.2019.02.003

An improved algorithm for testing substitutability of weak preferences

Susumu Kawanaka, Naoyuki Kamiyama

Division of Advanced Mathematics Technology

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper, we consider the problem of testing substitutability of weak preferences. For this problem, Aziz, Brill, and Harrenstein proposed an O(ℓ ³ u ² +ℓ ² u ² s ² )-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(ℓ ³ u+ℓ ² u ² 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 language	English
Pages (from-to)	1-4
Number of pages	4
Journal	Mathematical Social Sciences
Volume	99
DOIs	https://doi.org/10.1016/j.mathsocsci.2019.02.003
Publication status	Published - May 2019

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1016/j.mathsocsci.2019.02.003

Cite this

@article{9022a8b870a94daa9adaa1fe1e2dfaa8,

title = "An improved algorithm for testing substitutability of weak preferences",

abstract = " 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.",

author = "Susumu Kawanaka and Naoyuki Kamiyama",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier B.V.",

year = "2019",

month = may,

doi = "10.1016/j.mathsocsci.2019.02.003",

language = "English",

volume = "99",

pages = "1--4",

journal = "Mathematical Social Sciences",

issn = "0165-4896",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - An improved algorithm for testing substitutability of weak preferences

AU - Kawanaka, Susumu

AU - Kamiyama, Naoyuki

PY - 2019/5

Y1 - 2019/5

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85062870733

UR - https://www.scopus.com/inward/citedby.url?scp=85062870733&partnerID=8YFLogxK

U2 - 10.1016/j.mathsocsci.2019.02.003

DO - 10.1016/j.mathsocsci.2019.02.003

M3 - Article

AN - SCOPUS:85062870733

SN - 0165-4896

VL - 99

SP - 1

EP - 4

JO - Mathematical Social Sciences

JF - Mathematical Social Sciences

ER -

An improved algorithm for testing substitutability of weak preferences

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this