Pairwise Ranking Aggregation by Non-interactive Crowdsourcing with Budget Constraints

Changjiang Cai, Haipei Sun, Boxiang Dong, Bo Zhang, Ting Wang, Hui Wang

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

Crowdsourced ranking algorithms ask the crowd to compare the objects and infer the full ranking based on the crowdsourced pairwise comparison results. In this paper, we consider the setting in which the task requester is equipped with a limited budget that can afford only a small number of pairwise comparisons. To make the problem more complicated, the crowd may return noisy comparison answers. We propose an approach to obtain a good-quality full ranking from a small number of pairwise preferences in two steps, namely task assignment and result inference. In the task assignment step, we generate pairwise comparison tasks that produce a full ranking with high probability. In the result inference step, based on the transitive property of pairwise comparisons and truth discovery, we design an efficient heuristic algorithm to find the best full ranking from the potentially conflictive pairwise preferences. The experiment results demonstrate the effectiveness and efficiency of our approach.

Original languageEnglish
Title of host publicationProceedings - IEEE 37th International Conference on Distributed Computing Systems, ICDCS 2017
EditorsKisung Lee, Ling Liu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2567-2568
Number of pages2
ISBN (Electronic)9781538617915
DOIs
StatePublished - 13 Jul 2017
Event37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017 - Atlanta, United States
Duration: 5 Jun 20178 Jun 2017

Publication series

NameProceedings - International Conference on Distributed Computing Systems

Other

Other37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017
CountryUnited States
CityAtlanta
Period5/06/178/06/17

Fingerprint

Heuristic algorithms
Agglomeration
Experiments

Keywords

  • Budget constraint
  • Crowdsourcing
  • Rank aggregation

Cite this

Cai, C., Sun, H., Dong, B., Zhang, B., Wang, T., & Wang, H. (2017). Pairwise Ranking Aggregation by Non-interactive Crowdsourcing with Budget Constraints. In K. Lee, & L. Liu (Eds.), Proceedings - IEEE 37th International Conference on Distributed Computing Systems, ICDCS 2017 (pp. 2567-2568). [7980235] (Proceedings - International Conference on Distributed Computing Systems). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDCS.2017.102
Cai, Changjiang ; Sun, Haipei ; Dong, Boxiang ; Zhang, Bo ; Wang, Ting ; Wang, Hui. / Pairwise Ranking Aggregation by Non-interactive Crowdsourcing with Budget Constraints. Proceedings - IEEE 37th International Conference on Distributed Computing Systems, ICDCS 2017. editor / Kisung Lee ; Ling Liu. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 2567-2568 (Proceedings - International Conference on Distributed Computing Systems).
@inproceedings{4fb495f8d37043f98345ff567644904f,
title = "Pairwise Ranking Aggregation by Non-interactive Crowdsourcing with Budget Constraints",
abstract = "Crowdsourced ranking algorithms ask the crowd to compare the objects and infer the full ranking based on the crowdsourced pairwise comparison results. In this paper, we consider the setting in which the task requester is equipped with a limited budget that can afford only a small number of pairwise comparisons. To make the problem more complicated, the crowd may return noisy comparison answers. We propose an approach to obtain a good-quality full ranking from a small number of pairwise preferences in two steps, namely task assignment and result inference. In the task assignment step, we generate pairwise comparison tasks that produce a full ranking with high probability. In the result inference step, based on the transitive property of pairwise comparisons and truth discovery, we design an efficient heuristic algorithm to find the best full ranking from the potentially conflictive pairwise preferences. The experiment results demonstrate the effectiveness and efficiency of our approach.",
keywords = "Budget constraint, Crowdsourcing, Rank aggregation",
author = "Changjiang Cai and Haipei Sun and Boxiang Dong and Bo Zhang and Ting Wang and Hui Wang",
year = "2017",
month = "7",
day = "13",
doi = "10.1109/ICDCS.2017.102",
language = "English",
series = "Proceedings - International Conference on Distributed Computing Systems",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "2567--2568",
editor = "Kisung Lee and Ling Liu",
booktitle = "Proceedings - IEEE 37th International Conference on Distributed Computing Systems, ICDCS 2017",

}

Cai, C, Sun, H, Dong, B, Zhang, B, Wang, T & Wang, H 2017, Pairwise Ranking Aggregation by Non-interactive Crowdsourcing with Budget Constraints. in K Lee & L Liu (eds), Proceedings - IEEE 37th International Conference on Distributed Computing Systems, ICDCS 2017., 7980235, Proceedings - International Conference on Distributed Computing Systems, Institute of Electrical and Electronics Engineers Inc., pp. 2567-2568, 37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017, Atlanta, United States, 5/06/17. https://doi.org/10.1109/ICDCS.2017.102

Pairwise Ranking Aggregation by Non-interactive Crowdsourcing with Budget Constraints. / Cai, Changjiang; Sun, Haipei; Dong, Boxiang; Zhang, Bo; Wang, Ting; Wang, Hui.

Proceedings - IEEE 37th International Conference on Distributed Computing Systems, ICDCS 2017. ed. / Kisung Lee; Ling Liu. Institute of Electrical and Electronics Engineers Inc., 2017. p. 2567-2568 7980235 (Proceedings - International Conference on Distributed Computing Systems).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

T1 - Pairwise Ranking Aggregation by Non-interactive Crowdsourcing with Budget Constraints

AU - Cai, Changjiang

AU - Sun, Haipei

AU - Dong, Boxiang

AU - Zhang, Bo

AU - Wang, Ting

AU - Wang, Hui

PY - 2017/7/13

Y1 - 2017/7/13

N2 - Crowdsourced ranking algorithms ask the crowd to compare the objects and infer the full ranking based on the crowdsourced pairwise comparison results. In this paper, we consider the setting in which the task requester is equipped with a limited budget that can afford only a small number of pairwise comparisons. To make the problem more complicated, the crowd may return noisy comparison answers. We propose an approach to obtain a good-quality full ranking from a small number of pairwise preferences in two steps, namely task assignment and result inference. In the task assignment step, we generate pairwise comparison tasks that produce a full ranking with high probability. In the result inference step, based on the transitive property of pairwise comparisons and truth discovery, we design an efficient heuristic algorithm to find the best full ranking from the potentially conflictive pairwise preferences. The experiment results demonstrate the effectiveness and efficiency of our approach.

AB - Crowdsourced ranking algorithms ask the crowd to compare the objects and infer the full ranking based on the crowdsourced pairwise comparison results. In this paper, we consider the setting in which the task requester is equipped with a limited budget that can afford only a small number of pairwise comparisons. To make the problem more complicated, the crowd may return noisy comparison answers. We propose an approach to obtain a good-quality full ranking from a small number of pairwise preferences in two steps, namely task assignment and result inference. In the task assignment step, we generate pairwise comparison tasks that produce a full ranking with high probability. In the result inference step, based on the transitive property of pairwise comparisons and truth discovery, we design an efficient heuristic algorithm to find the best full ranking from the potentially conflictive pairwise preferences. The experiment results demonstrate the effectiveness and efficiency of our approach.

KW - Budget constraint

KW - Crowdsourcing

KW - Rank aggregation

UR - http://www.scopus.com/inward/record.url?scp=85027256394&partnerID=8YFLogxK

U2 - 10.1109/ICDCS.2017.102

DO - 10.1109/ICDCS.2017.102

M3 - Conference contribution

T3 - Proceedings - International Conference on Distributed Computing Systems

SP - 2567

EP - 2568

BT - Proceedings - IEEE 37th International Conference on Distributed Computing Systems, ICDCS 2017

A2 - Lee, Kisung

A2 - Liu, Ling

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Cai C, Sun H, Dong B, Zhang B, Wang T, Wang H. Pairwise Ranking Aggregation by Non-interactive Crowdsourcing with Budget Constraints. In Lee K, Liu L, editors, Proceedings - IEEE 37th International Conference on Distributed Computing Systems, ICDCS 2017. Institute of Electrical and Electronics Engineers Inc. 2017. p. 2567-2568. 7980235. (Proceedings - International Conference on Distributed Computing Systems). https://doi.org/10.1109/ICDCS.2017.102