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 contribution

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

Keywords

  • Budget constraint
  • Crowdsourcing
  • Rank aggregation

Fingerprint Dive into the research topics of 'Pairwise Ranking Aggregation by Non-interactive Crowdsourcing with Budget Constraints'. Together they form a unique fingerprint.

  • 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