Optimal Impartial Mechanisms

Lead Research Organisation: Queen Mary University of London
Department Name: Sch of Mathematical Sciences

Abstract

In many settings of practical concern a close connection exists between the expertise held within a group of individuals and individuals' selfish interests, which may prevent the expertise from being offered in an impartial way. Examples of this phenomenon can be found in scientific peer review, which is based on the very idea that the quality of scientific work is best judged by peers of the scientist or scientists carrying out the work, in peer grading, where students on a course assess the work of other students and thus relieve pressure on teachers and enable better quality teaching or larger class sizes, and in the appraisal of employee performance, which relies on reports from other employees to make decisions regarding bonus payments or promotions. In all of these examples we are interested in aggregating individuals' impartial assessment concerning other members of the group into a collective judgment, but honest reporting may be compromised by selfish interests: the interest of a scientist to receive funding for scientific work and publish the results of this work, the interest of a student to do well on a course, or the desire of an employee to receive a bonus payment or be promoted. As it is often reasonable to assume that individuals will provide impartial assessments as long as they cannot influence the resulting judgment about themselves, it makes sense to consider what we call impartial mechanisms for aggregating individuals' reports, procedures that select an outcome in such a way that truthful reporting is in each individual's best interest. The mathematical study of impartial mechanisms is part of the area of mechanism design in microeconomic theory, and specializes the larger class of incentive-compatible mechanisms to settings where reports amount to an assessment of the members of a group and the preferences of an individual only concern the collective judgment of that individual. The study of impartial mechanisms is relatively new and only a small literature exists on such mechanisms, specifically for the allocation of a fixed amount of a divisible resource and the selection of a fixed number of individuals. The proposed project sets out to rigorously study optimal impartial mechanisms for a larger class of settings: selection with and without abstentions and with or without intensities, assignment, and ranking. An impartial mechanism is called optimal in this context if among all impartial mechanisms it maximizes the overall quality of the solution. New mathematical insights regarding impartiality will be used to develop new practical mechanisms for real-world problems of peer review, peer grading, and performance appraisal. These mechanisms will be tested and made available to the public as part of a free online service, which will also be used to investigate real-world impartiality requirements and new application areas.

Planned Impact

The project seeks to advance the theory and practice of optimal impartial mechanisms, and due to the high practical relevance of such mechanisms promises significant direct benefits to society and the economy. Intriguingly some of the most compelling applications of impartial mechanisms are in research and higher education, where they have a potential to further increase impact in the future.

An assumption of impartiality is at the core of scholarly peer review, but the mechanisms used in peer review today do almost nothing to guarantee impartiality and in principle are vulnerable to both deliberate manipulation and unconscious biases. While the impact of such vulnerabilities is difficult to assess, impartial mechanisms for scientific peer review have the potential to significantly improve the allocation of a scarce resource. As a consequence the most qualified individuals will work on the research problems most important for society, and the outcomes of this research will be disseminated more quickly. Impartial mechanisms for peer grading can help to ensure that the increase in the number of students taught and in the diversity of the student population offered by massive open online courses do not come at the cost of a lower quality of teaching and assessment. In public services and business, impartial mechanisms for performance appraisals have the potential to improve recruitment, retention, and staff-project scheduling, and thus to increase motivation and happiness of staff as well as overall productivity.

In all these applications impartial mechanisms will allow organizational knowledge held by individuals within an organization to be shared more freely and without consideration of selfish interests. In addition to a more effective and more efficient use of knowledge and resources, such increased freedom and openness can also help more generally to improve the processes, practices, and culture of organizations. While a better use of knowledge and resources will benefit research, higher education, public services, and businesses throughout the world, it is of particular importance for the UK due to its world leading position in research and higher education and the high relative contribution of services industries to its economic output.

An integral component of the project is the development of a free online service that will be used for mechanism prototyping and evaluation as well as for public engagement. The service will allow members of the public to apply impartial mechanisms to real-world problems and gain a better understanding of the role of incentives in decision-making and of existing and future mechanisms that mediate these incentives. We hope that it will also raise the profile of mathematical research at the boundary of economics and optimization, and will guide this research toward new application areas. Our efforts in this context will expand on the existing services Spliddit and RoboVote in terms of new application areas and provide new functionality for testing mechanisms on real-world data, engaging with the public on mechanism design and impartiality, and identifying new applications of impartial mechanisms and new research questions.
 
Description Significant new knowledge and techniques were obtained regarding mechanisms for impartial selection and rank aggregation. Impartial selection is the selection of individuals from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. Impartial rank aggregation is the aggregation of a set of rankings of the individuals into a single ranking, in such a way that no individual can influence their position in the ranking.

Our results for impartial selection concern additive performance guarantees achievable by deterministic mechanisms, tradeoffs between quality and quantity of selected individuals, and the tight analysis of a known mechanism in an important special case.

We obtained a new deterministic mechanism achieving additive performance guarantees, and a new impossibility result regarding such mechanisms. The mechanism is parameterised by the number of nominations submitted by each individual; when this number is constant, the new mechanism matches the performance of the best known randomised mechanism. The impossibility result shows that without restrictions on the number of nominations submitted by each individual, no non-trivial guarantee can be achieved.

Lifting the restricting on the number of selected individuals leads to the setting of impartial correspondences. Here we established that no impartial mechanism is able to select only individuals with a maximum number of nominations. When each individual submits at most d nominations, it is possible to select at most d+1 individuals that all receive a number of nominations within one of the maximum number of nominations for any individual.

The optimal mechanism for impartial selection of a single individual is the so-called permutation mechanism. We obtained a tight performance guarantee for this mechanism in the important special case where each individual submits a single nomination, and established that the mechanism is not the optimal mechanism in this case.

In impartial rank aggregation, we established that two properties concerning the quality of the output in relation to the input can be achieved in addition to impartiality: individual full rank, which requires that each individual can appear in any position of the output ranking; and monotonicity, which requires that an individual cannot move down in the output ranking if it moves up in an input ranking; if monotonicity is dropped it is possible to strengthen individual full rank to weak unanimity, which requires that a ranking submitted by every individual must be chosen as the output ranking.

The results were obtained via a combination of techniques from combinatorics, applied probability and optimisation. These techniques will likely find wider application in algorithmic mechanism design and contribute to a more systematic understanding of the foundations of the area.
Exploitation Route Project outcomes include new results and techniques, and new research directions. These outcomes form the foundation of ongoing research on impartial mechanisms, both by us and by others. All problems considered in the project are motivated by applications, and results will in the medium term inform the design and use of social and economic mechanisms such as voting rules and credit allocation mechanisms.
Sectors Digital/Communication/Information Technologies (including Software)

Financial Services

and Management Consultancy

Government

Democracy and Justice

URL https://webspace.maths.qmul.ac.uk/felix.fischer/publications.html
 
Description Impartial selection and rank aggregation are part of the theoretical foundations of peer evaluation, which in turn comprises a number of important applications such as peer review and allocation of credit (see Olckers and Walsh, Manipulation and Peer Mechanisms: A Survey, arXiv:2210.01984). The project is concerned with basic research. It seeks, and has begun to, achieve impact by influencing the research agenda in the wider area of algorithmic mechanism design, and by identifying salient features of good practical mechanisms that hold across a range of applications.