Peer review, evaluation, and selection is a fundamental aspect of modern science. Funding bodies the world over employ experts to review and select the best proposals of those submitted for funding. The problem of peer selection, however, is much more general: a professional society may want to give a subset of its members awards based on the opinions of all members; an instructor for a MOOC or online course may want to crowdsource grading; or a marketing company may select ideas from group brainstorming sessions based on peer evaluation. We make three fundamental contributions to the study of procedures or mechanisms for peer selection, a specific type of group decision-making problem, studied in computer science, economics, and political science. First, we propose a novel mechanism that is strategyproof, i.e., agents cannot benefit by reporting insincere valuations. Second, we demonstrate the effectiveness of our mechanism by a comprehensive simulation-based comparison with a suite of mechanisms found in the literature. Finally, our mechanism employs a randomized rounding technique that is of independent interest, as it solves the apportionment problem that arises in various settings where discrete resources such as parliamentary representation slots need to be divided proportionally.
Both and examine the selection problem in which agents simply approve (nominate) a subset of agents. , , and restrict their attention to a setting in which exactly one agent is selected ( @math ). also present a new permutation'' mechanism that achieves the same bound as the Partition mechanisms (those presented in , involving a division of agents into groups) for @math . and showed that for the peer selection problem, deterministic impartial mechanisms are extremely limited, and must sometimes select an agent with zero nominations even though other agents receive nominations, or an agent with one nomination when another agent receives @math nominations @cite_2 . built on this work to show that allowing a mechanism where agents simply approve of some subset of agents to select fewer than @math agents allows the mechanism to guarantee some bounds on the selected items---they are within about @math from the optimal selection. present a more general mechanism called Credible Subset that is strategyproof but may select with non-zero probability. Credible Subset performs well when each agent reviews a few other agents, and this number is considerably smaller than @math .
@cite_2
2093375346 2063004177 181649221 2047179339
We consider the special case of approval voting when the set of agents and the set of alternatives coincide. This captures situations in which the members of an organization want to elect a president or a committee from their ranks, as well as a variety of problems in networked environments, for example in internet search, social networks like Twitter, or reputation systems like Epinions. More precisely, we look at a setting where each member of a set of n agents approves or disapproves of any other member of the set and we want to select a subset of k agents, for a given value of k, in a strategyproof and approximately efficient way. Here, strategyproofness means that no agent can improve its own chances of being selected by changing the set of other agents it approves. A mechanism is said to provide an approximation ratio of α for some α ≥ 1 if the ratio between the sum of approval scores of any set of size k and that of the set selected by the mechanism is always at most α. We show that for k ∈ 1, 2,..., n − 1 , no deterministic strategyproof mechanism can provide a finite approximation ratio. We then present a randomized strategyproof mechanism that provides an approximation ratio that is bounded from above by four for any value of k, and approaches one as k grows. We study the House Allocation problem (also known as the Assignment problem), i.e., the problem of allocating a set of objects among a set of agents, where each agent has ordinal preferences (possibly involving ties) over a subset of the objects. We focus on truthful mechanisms without monetary transfers for finding large Pareto optimal matchings. It is straightforward to show that no deterministic truthful mechanism can approximate a maximum cardinality Pareto optimal matching with ratio better than 2. We thus consider randomized mechanisms. We give a natural and explicit extension of the classical Random Serial Dictatorship Mechanism (RSDM) specifically for the House Allocation problem where preference lists can include ties. We thus obtain a universally truthful randomized mechanism for finding a Pareto optimal matching and show that it achieves an approximation ratio of eovere-1. The same bound holds even when agents have priorities (weights) and our goal is to find a maximum weight (as opposed to maximum cardinality) Pareto optimal matching. On the other hand we give a lower bound of 18 over 13 on the approximation ratio of any universally truthful Pareto optimal mechanism in settings with strict preferences. In the case that the mechanism must additionally be non-bossy, an improved lower bound of eovere-1 holds. This lower bound is tight given that RSDM for strict preference lists is non-bossy. We moreover interpret our problem in terms of the classical secretary problem and prove that our mechanism provides the best randomized strategy of the administrator who interviews the applicants. We examine strategy-proof elections to select a winner amongst a set of agents, each of whom cares only about winning. This impartial selection problem was introduced independently by Holzman and Moulin [5] and [1]. Fischer and Klimm [4] showed that the permutation mechanism is impartial and ( )-optimal, that is, it selects an agent who gains, in expectation, at least half the number of votes of the most popular agent. Furthermore, they showed the mechanism is ( 7 12 )-optimal if agents cannot abstain in the election. We show that a better guarantee is possible, provided the most popular agent receives at least a large enough, but constant, number of votes. Specifically, we prove that, for any e > 0, there is a constant N e (independent of the number n of voters) such that, if the maximum number of votes of the most popular agent is at least N e then the permutation mechanism is (( 3 4 - ) )-optimal. This result is tight. We study the problem of selecting a member of a set of agents based on impartial nominations by agents from that set. The problem was studied previously by and by Holzman and Moulin and has important applications in situations where representatives are selected from within a group or where publishing or funding decisions are made based on a process of peer review. Our main result concerns a randomized mechanism that in expectation selects an agent with at least half the maximum number of nominations. Subject to impartiality, this is best possible.