Efficient Mechanisms for Peer Grading and Dueling Bandits

Chuang-Chieh Lin, Chi-Jen Lu
Proceedings of The 10th Asian Conference on Machine Learning, PMLR 95:740-755, 2018.

Abstract

Many scenarios in our daily life require us to infer some ranking over items or people based on limited information. In this paper, we consider two such scenarios, one for ranking student papers in massive online open courses and one for identifying the best player (or team) in sports tournaments. For the peer grading problem, we design a mechanism with a new way of matching graders to papers. This allows us to aggregate partial rankings from graders into a global one, with an accuracy rate matching the best in previous works, but with a much simpler analysis. For the winner selection problem in sports tournaments, we cast it as the well-known dueling bandit problem and identify a new measure to minimize: the number of parallel rounds, as one normally would not like a large tournament to last too long. We provide mechanisms which can determine the optimal or an almost optimal player in a small number of parallel rounds and at the same time using a small number of competitions.

Cite this Paper


BibTeX
@InProceedings{pmlr-v95-lin18a, title = {Efficient Mechanisms for Peer Grading and Dueling Bandits}, author = {Lin, Chuang-Chieh and Lu, Chi-Jen}, booktitle = {Proceedings of The 10th Asian Conference on Machine Learning}, pages = {740--755}, year = {2018}, editor = {Zhu, Jun and Takeuchi, Ichiro}, volume = {95}, series = {Proceedings of Machine Learning Research}, month = {14--16 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v95/lin18a/lin18a.pdf}, url = {https://proceedings.mlr.press/v95/lin18a.html}, abstract = {Many scenarios in our daily life require us to infer some ranking over items or people based on limited information. In this paper, we consider two such scenarios, one for ranking student papers in massive online open courses and one for identifying the best player (or team) in sports tournaments. For the peer grading problem, we design a mechanism with a new way of matching graders to papers. This allows us to aggregate partial rankings from graders into a global one, with an accuracy rate matching the best in previous works, but with a much simpler analysis. For the winner selection problem in sports tournaments, we cast it as the well-known dueling bandit problem and identify a new measure to minimize: the number of parallel rounds, as one normally would not like a large tournament to last too long. We provide mechanisms which can determine the optimal or an almost optimal player in a small number of parallel rounds and at the same time using a small number of competitions.} }
Endnote
%0 Conference Paper %T Efficient Mechanisms for Peer Grading and Dueling Bandits %A Chuang-Chieh Lin %A Chi-Jen Lu %B Proceedings of The 10th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jun Zhu %E Ichiro Takeuchi %F pmlr-v95-lin18a %I PMLR %P 740--755 %U https://proceedings.mlr.press/v95/lin18a.html %V 95 %X Many scenarios in our daily life require us to infer some ranking over items or people based on limited information. In this paper, we consider two such scenarios, one for ranking student papers in massive online open courses and one for identifying the best player (or team) in sports tournaments. For the peer grading problem, we design a mechanism with a new way of matching graders to papers. This allows us to aggregate partial rankings from graders into a global one, with an accuracy rate matching the best in previous works, but with a much simpler analysis. For the winner selection problem in sports tournaments, we cast it as the well-known dueling bandit problem and identify a new measure to minimize: the number of parallel rounds, as one normally would not like a large tournament to last too long. We provide mechanisms which can determine the optimal or an almost optimal player in a small number of parallel rounds and at the same time using a small number of competitions.
APA
Lin, C. & Lu, C.. (2018). Efficient Mechanisms for Peer Grading and Dueling Bandits. Proceedings of The 10th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 95:740-755 Available from https://proceedings.mlr.press/v95/lin18a.html.

Related Material