Algorithmic Contract Design for Crowdsourced Ranking: Warm-up: Agents With Known Equal Disutility

Table of Links

Abstract and Introduction

Warm-up: Agents with known equal disutility

Agents with unknown disutilites

Experiments

Conclusions and future directions, References

A Summary of notation

B Omitted proofs from Section 2

C Omitted proofs from Section 3

D Additional Information about Experiments

2 Warm-up: Agents with known equal disutility

As a warm up to our main result, in this section, we propose a contract assuming that (a) the principal knows the agents’ disutilites and (b) every agent experiences the same value of per-comparison disutility (assumptions we relax in Section 3). We begin with a formal model in Section 2.1 and define the optimal payment in Section 2.2. In Sections 2.3 and 2.4, we present our main algorithm CrowdSort for computing the correct sorting. Section 2.5 identifies conditions under which the principal gets higher utility when implementing our proposed contract than when performing all pairwise comparisons herself. The full proofs of all results in this section are in Appendix B.

2.1 Model and notation

The interaction proceeds as follows:

1. The principal fixes a payment p∗ ∈ R+ that she will pay agents in order to incentivize them to exert effort.

2. The principal verifies a subset of the comparisons and announces the size of this set to the agents.

3. Agents choose whether to exert effort, which fixes their type upfront.

4. Agents are assigned verified and unverified comparisons.

2.2 Agents’ incentives

2.3 Peer grading algorithm

2.4 Allocation of items

2.4.1 Assigning verified comparisons.

Lemma 2.3. If each item in V appears in exactly one pair, then no pair in V is redundant.

2.4.2 Assigning unverified comparisons.

We now define findWset. First, we bound the number of agents each comparison must be assigned to in order to retrieve the ground-truth sorting.

Details about the social golfer problem. In the social golfer problem, the goal is to determine whether m golfers can play together in g groups of p (where m = gp) for w days in such a way that (1) no two golfers play in the same group more than once, and (2) each golfer plays exactly once each day. Thus, an instance of this problem is defined by integers (g, p, w). For us, the golfers correspond to the items, the days correspond to the partitions, and the groups of golfers correspond to the sets in the partitions. Thus, we aim to solve this problem with g, p, and w all approximately equal to √n.

2.5 Principal’s incentives

We synthesize our results in the following theorem, in which we additionally prove that if the principal’s disutility ψ¯ is sufficiently larger than the agents’ disuility ψ, then it is in the principal’s best interest to use our mechanism rather than perform all pairwise comparisons herself. This is a natural assumption, which implies that the principal would have to be compensated sufficiently more per comparison than the agents for their work to be profitable to the principal.

This paper is available on Arxiv under CC 4.0 license.