Weighted partial order oriented three-way decisions under score-based common voting rules

Lei Li*, Xindong Wu, Huanhuan Chen, Chuan Zhou, Guanfeng Liu, Yongkang Jiang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Recently, with the trisecting and acting models of human cognitive behaviors, three-way decisions are introduced to deal with uncertain decisions in many applications. To define and conduct the three-way decisions on the possible or necessary loser or co-loser and/or winner or co-winner, we first define the score-based common voting rules, where a score-based function is introduced to evaluate certain utility, including positional scoring rules, maximin, Bucklin, and so on. Then on one hand, it has been proved that under certain conditions three-way decisions on the possible loser or co-loser and/or winner or co-winner are NP-complete with positional scoring rules, maximin, and Bucklin, respectively. On the other hand, we have presented algorithms whose time complexity is polynomial to conduct three-way decisions on the necessary winner or co-winner and/or necessary loser or co-loser with positional scoring rules, maximin, and Bucklin in time O(nm2), O(nm3), and O(nm2), respectively, which has been validated experimentally.

Original languageEnglish
Pages (from-to)41-54
Number of pages14
JournalInternational Journal of Approximate Reasoning
Volume123
DOIs
Publication statusPublished - Aug 2020

Keywords

  • Three-way decisions
  • Weighted partial orders
  • Common voting rules

Fingerprint Dive into the research topics of 'Weighted partial order oriented three-way decisions under score-based common voting rules'. Together they form a unique fingerprint.

Cite this