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

数学テクノロジー先端研究部門

研究成果: ジャーナルへの寄稿 › 学術誌 › 査読

抄録

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.

本文言語	英語
ページ（範囲）	1-4
ページ数	4
ジャーナル	Mathematical Social Sciences
巻	99
DOI	https://doi.org/10.1016/j.mathsocsci.2019.02.003
出版ステータス	出版済み - 5月 2019

!!!All Science Journal Classification (ASJC) codes

社会学および政治科学
社会科学一般
心理学一般
統計学、確率および不確実性

文献へのアクセス

10.1016/j.mathsocsci.2019.02.003

他のファイルとリンク

引用スタイル

@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/pages/publications/85062870733#tab=citedBy

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

抄録

!!!All Science Journal Classification (ASJC) codes

文献へのアクセス

他のファイルとリンク

フィンガープリント

引用スタイル