Algorithmic Contract Design for Crowdsourced Ranking: Omitted Proofs From Section 2

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

B Omitted proofs from Section 2

With Bayes’ rule and simplifying we get:

We similarly handle the second case, in which the agent does not exert effort, this time noting that the agent does not experience disutility:

For the agent to be incentivized to exert effort, the payment needs to be such that:

We use the quantities from above to get:

To satisfy individual rationality, we require that:

which holds if and only if:

and by simplifying we get:

which is always satisfied if constraint 10 is satisfied.

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

Lemma 2.5. Suppose v ≥ log (2(1 − π)s/δ). Let

be the number of agents each comparison is assigned to. Then with probability 1 − δ,

CrowdSort(T, s, v, r, δ) returns the ground-truth ordering.

For every subset that the agent is asked to fully sort, the agent can sort items adaptively so the number of pairwise comparisons he will perform is O(q log q). Therefore:

Theorem 2.7. Suppose that the principal pays agents p∗ and runs CrowdSort(T, s, v∗, r∗, δ). Then:

If the principal decides to set the price to 0, then no agents will induce effort and the principal will need to perform all pairwise comparisons on her own. The expected number of comparisons she will need to perform is 2n log n. Therefore, the disutility of the principal in this case is:

For the principal to decide to propose a contract, her expected utility when inducing effort from the agents must be greater than or equal to her utility when she does not. In other words, we require that:

This paper is available on Arxiv under CC 4.0 license.