Optimal impartial mechanisms

点击翻译按钮获取中文摘要

This project considers the problem of selecting or ranking individuals from a set based on nominations from within the set. This is a standard problem of computation social choice that has many applications, e.g., in peer review for conferences and journals, peer grading for massive online courses (MOOCs), voting in committees or the leader electing problem for autonomous self-interested agents. A common issue in all these applications is that some agents may be willing to misreport their opinion about who of the other agents is eligible to be selected in order to increase their chances of being selected. This motivates the study of impartial mechanisms that have the special property that the nominations cast by an agent have no influence on the selection probability of that agent. In the last years, impartial mechanisms for the task to select a single agent has been fairly well understood. In light of the applications above, this project sets out to enhance the understanding of several important generalizations of the problem of selecting a singe agent. Specifically, we will design mechanisms that select several agents in an impartial way and analyze them in terms of the worst-case approximation guarantee, i.e., the sum of the nominations received by the selected agents divided by the maximal number of nominations of agents that can be selected. Motivated by applications in peer review and peer grading, we will further study a generalization of the model where nominations have a weight or rating. Generalizing further, we will study a model where agents are ranked in an impartial way based on individual rankings submitted by the agents. This is important, e.g., for peer grading applications where agents receive grades based on their relative performance in the peer group. In addition to the theoretical analysis, we will also test and evaluate our algorithms on real-world preference data and provide the designed algorithms to the scientific community.