* [39] Slepchenko BM, Terasaki M.  Cyclin aggregation and robustness of bio-switching.  Mol Biol Cell. 2003;14(11):4695–4706.
  * [40] Tyson JJ, Chen K, Novak B.  Network dynamics and cell physiology.  Nat Rev Mol Cell Biol. 2001;2(12):908–916.
  * [41] Kothamachu VB, Feliu E, Cardelli L, Soyer OS.  Unlimited multistability and Boolean logic in microbial signalling.  J Roy Soc Interface. 2015;12(108):215–234.
  * [42] Salazar C, Hofer T.  Multisite protein phosphorylation–from molecular mechanisms to kinetic models.  FEBS J. 2009;276(12):3177–3198.
  * [43] Thomson M, Gunawardena J.  Unlimited multistability in multisite phosphorylation systems.  Nature. 2009;406:274–277.
  * [44] Wang L, Sontag ED.  On the number of steady states in a multiple futile cycle.  J Math Biol. 2008;57:29–52.
  * [45] Giaroli M, Rischter R, Pérez Millán M, Dickenstein A.  Parameter regions that give rise to 2[n/2] +1 positive steady states in the n-site phosphorylation system.  Math Biosci Eng. 2019;16(6):7589–7615.
  * [46] Conradi C, Flockerzi D, Raisch J.  Multistationarity in the activation of a MAPK: parametrizing the relevant region in parameter space.  Math Biosc. 2008;211(1):105–131.
  * [47] Feliu E, Rendall AD, Wiuf C.  A proof of unlimited multistability for phosphorylation cycles.  Nonlinearity. 2020;33(11):5629–5658.  doi:10.1088/1361-6544/ab9a1e.
  * [48] Flockerzi D, Holstein K, Conradi C.  N-site Phosphorylation Systems with 2N-1 Steady States.  Bull Math Biol. 2014;76(8):1892–1916.  doi:10.1007/s11538-014-9984-0.
  * [49] Feliu E, Kaihnsa N, de Wolff T, Yürück O.  The Kinetic Space of Multistationarity in Dual Phosphorylation.  J Dyn Differ Equ. 2022;34:825–852.
  * [50] Gunawardena J.  Distributivity and processivity in multisite phosphorylation can be distinguished through steady-state invariants.  Biophys J. 2007;93:3828–3834.
  * [51] Gunawardena J.  Multisite protein phosphorylation makes a good threshold but can be a poor switch.  Proc Natl Acad Sci USA. 2005;102:14617–14622.
  * [52] Bihan F, Dickenstein A, Giaroli M.  Sign conditions for the existence of at least one positive solution of a sparse polynomial system.  Adv Math. 2020;375:107412.  doi:10.1016/j.aim.2020.107412.
  * [53] Feliu E, Kaihnsa N, de Wolff T, Yürük O.  Parameter region for multistationarity in $n-$site phosphorylation networks.  SIAM J Appl Dyn Syst. 2023;To appear.
  * [54] Cohen P.  The regulation of protein function by multisite phosphorylation–a 25 year update.  Trends Biochem Sci. 2000;25(12):596–601.
  * [55] Xiao L, Gong LL, Yuan D, Deng M, Zeng XM, Chen LL, et al.  Protein phosphatase-1 regulates Akt1 signal transduction pathway to control gene expression, cell survival and differentiation.  Cell Death Differ. 2010;17(9):1448–1462.
  * [56] Markevich NI, Hoek JB, Kholodenko BN.  Signaling switches and bistability arising from multisite phosphorylation in protein kinase cascades.  J Cell Biol. 2004;164:353–359.
  * [57] Zhao Y, Zhang ZY.  The mechanism of dephosphorylation of extracellular signal-regulated kinase 2 by mitogen-activated protein kinase phosphatase 3.  J Biol Chem. 2001;276(34):32382–32391.
  * [58] Shaul YD, Seger R.  The MEK/ERK cascade: From signaling specificity to diverse functions.  BBA-Mol Cell Res. 2007;1773(8):1213–1226.  doi:10.1016/j.bbamcr.2006.10.005.
  * [59] Futran AS, Link AJ, Seger R, Shvartsman SY.  ERK as a model for systems biology of enzyme kinetics in cells.  Curr Biol. 2013;23(21):R972–R979.
  * [60] Rubinstein BY, Mattingly HH, Berezhkovskii AM, Shvartsman SY.  Long-term dynamics of multisite phosphorylation.  Mol Biol Cell. 2016;27(14):2331–2340.
  * [61] Obatake N, Shiu A, Tang X, A T.  Oscillations and bistability in a model of ERK regulation.  J Math Biol. 2019;79:1515–1549.
  * [62] Conradi C, Obatake N, Shiu A, Tang X.  Dynamics of ERK regulation in the processive limit.  J Math Biol. 2021;82(32).  doi:10.1007/s00285-021-01574-6.
  * [63] Huang CY, Ferrell JE.  Ultrasensitivity in the mitogen-activated protein kinase cascade.  Proc Natl Acad Sci USA. 1996;93:10078–10083.
  * [64] Brustenga L. Package “SymbolicCRN.jl” for reaction networks in Julia; 2021.  Available from: https://github.com/LauraBMo/SymbolicCRN.jl.
  * [65] Leon M, Woods ML, Fedorec AJ, Barnes CP.  A computational method for the investigation of multistable systems and its application to genetic switches.  BMC Syst Biol. 2016;10(1):130.
  * [66] Otero-Muras I, Banga JR.  Multicriteria global optimization for biocircuit design.  BMC Syst Biol. 2014;8(1):113.  doi:10.1186/s12918-014-0113-3.
  * [67] Gawrilow E, Joswig M.  Polymake: a framework for analyzing convex polytopes.  In: Polytopes—combinatorics and computation (Oberwolfach, 1997). vol. 29 of DMV Sem. Birkhäuser, Basel; 2000. p. 43–73.
  * [68] Polymake;  Available from: https://polymake.org.
  * [69] The Oscar Computer Algebra System for Julia;  Available from: https://oscar.computeralgebra.de/.
  * [70] Klapper I, Szyld DB, Zhao K.  Metabolic Networks, Elementary Flux Modes, and Polyhedral Cones.  Philadelphia, PA: Society for Industrial and Applied Mathematics; 2021\.  Available from: https://epubs.siam.org/doi/abs/10.1137/1.9781611976533.
  * [71] Gerstenhaber M.  Theory of convex polyhedral cones.  In: Koopmans TC, editor. Activity analysis of production and allocation. Wiley; 1951. p. 298–317.
  * [72] Müller S, Regensburger G.  Elementary Vectors and Conformal Sums in Polyhedral Geometry and their Relevance for Metabolic Pathway Analysis.  Front Genet. 2016;7:90.
  * [73] Gagneur J, Klamt S.  Computation of elementary modes: A unifying framework and the new binary approach.  BMC bioinform. 2004;5:175.  doi:10.1186/1471-2105-5-175.
  * [74] Fukuda K, Prodon A.  Double description method revisited.  In: Deza M, Euler R, Manoussakis I, editors. Combinatorics and Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg; 1996. p. 91–111.
  * [75] Singh TB.  Introduction to Topology.  Springer Singapore; 2019.
  * [76] Łojasiewicz S.  On semi-analytic and subanalytic geometry.  Banach Cent Publ. 1995;34(1):89–104.
  * [77] Feliu E, Wiuf C.  Simplifying biochemical models with intermediate species.  J R Soc Interface. 2013;10(87):20130484.  doi:10.1098/rsif.2013.0484.


kfblue evpurple alred

# Algorithmic Contract Design for Crowdsourced Ranking

Kiriaki Frangias, Andrew Lin, Ellen Vitercik, Manolis Zampetakis

###### Abstract

Ranking is fundamental to many areas, such as search engine and recommender
system optimization, as well as peer grading. Crowdsourcing, which is often
used for these tasks, requires proper incentivization to ensure accurate
inputs. In this work, we draw on the field of _contract theory_ from Economics
to propose a novel mechanism that enables a _principal_ to accurately rank a
set of items by incentivizing agents to provide pairwise comparisons of the
items. Our mechanism implements these incentives by verifying a subset of each
agent’s comparisons with a ground-truth ordering, a task we assume to be
costly. The agent is compensated (for example, monetarily or with class
credit) based on the accuracy of these comparisons. Our mechanism achieves the
following guarantees: (1) it only requires the principal to verify $O(\log s)$
comparisons, where $s$ is the total number of agents, and (2) it provably
achieves higher total utility for principal compared to ranking the items
herself with no crowdsourcing.

##  1 Introduction

Ranking is a central task across a wide range of applications including search
engine optimization, recommender systems, and peer grading: search engines
rank pages by relevance, recommender systems rank content by entertainment
value, and peer graders rank submissions by quality. Platforms often use
crowdsourcing to determine rankings [9, 15, 7], especially when ranking many
alternatives. In many such cases, it is often more feasible and accurate for
agents to provide pairwise comparisons than cardinal evaluations [26, 27].
However, rational agents will only invest the effort necessary to provide
accurate comparisons when properly incentivized. In many real-world scenarios,
such as peer grading, these incentives involve a _principal_ (the ranking’s
end-user) verifying a selection of an agent’s comparisons against a ground-
truth sorting. The agent’s payment depends on these verified comparisons’
accuracy.

We propose a novel mechanism that enables a principal to rank a set of items
from pairwise comparisons while minimizing the requisite payments and number
of verifications, which are costly for the principal. To model the principal
and agents, we draw on _contract theory_ , a classical field in economics [16]
that has become increasingly relevant in computer science [e.g., 14, 10, 6,
32]. The principal assigns comparisons to each agent and verifies a subset of
these comparisons against a ground-truth ordering. The agent does not know the
subset’s identity. The principal will compensate each agent for correctly
evaluating all verified pairs.

Given the principal’s offered payment, the agent decides whether they will
exert effort. As in the standard model of contract theory, if the agent exerts
effort, they will be “good” at the task with some probability and “bad” at the
task with some smaller probability. If they decide not to exert effort, they
will be “bad” with certainty. A “good” agent will return the correct
comparisons, but a “bad” agent will not. When modeling the agents, we
introduce heterogeneity through differing values of the per-comparison
disutility that they experience. We therefore assume that every agent can
potentially be “good”, but might require more or less compensation to be
incentivized to exert effort. As we show, this also allows the principal to
incentivize and pay only agents with small disutilities, even though these
values are not _a priori_ known to the principal.

##### Key challenges.

The primary obstacle we face in designing a mechanism for this problem lies in
determining how to distribute the comparisons among the agents while
satisfying several critical requirements:

  1. (a)

The number of items assigned to each agent (i.e., the subset of items that
make up their pairwise comparisons) should be small, minimizing the agent’s
workload.

  2. (b)

Every comparison must be evaluated by at least one “good” agent with high
probability.

In other words, we want each agent’s comparisons to cover as few items as
possible to satisfy (a). However, we need the union of all agents’ comparisons
to have sufficiently high redundancy to satisfy (b). These conditions are
fundamentally at odds, so satisfying both requires care.

###  1.1 Our contributions

We summarize our four primary contributions below.

  1. 1.

Distributing comparisons. We provide an algorithm for distributing comparisons
among agents while ensuring conditions (a) and (b) above are satisfied. We
uncover a surprising connection to a classic combinatorial problem, the
_social golfer problem_ , which we use to design our algorithm. Letting $n$ be
the number of items to be sorted and $s$ be the number of agents, each agent
is assigned only $\tilde{\mathscr{O}}(n^{3/2}/s)$ items and
$\tilde{\mathscr{O}}(n^{3/2}/s)$ pairwise comparisons among those items.

  2. 2.

Aggregating the noisy comparisons. Next, we present an algorithm for
identifying “bad” agents and aggregating comparisons from “good” agents. Our
algorithm returns the correct ranking with high probability.

  3. 3.

Determining payments. We identify the payments necessary to ensure enough
agents are “good” to recover the ground-truth sorting. This depends on the
_disutility_ it costs agents to make comparisons. We study a range of
settings, from a warm-up where the principal knows the disutilities (as is
typical in contract theory), to a setting where the disutilities are drawn
from a distribution about which the principal has limited information.

  4. 4.

Principal’s utility. We show that it suffices for the principal to verify
$O(\log{s})$ comparisons to ensure that the ground-truth sorting is recovered.
We also identify natural conditions under which, by implementing our proposed
contract, the principal achieves higher total utility than she would if she
performed all pairwise comparisons herself.

  5. 5.

Experiments. In experiments, we stress-test our results by relaxing our model
along several axes. We demonstrate that even when the assumed model is
inaccurate, with a sufficient increase in the payment the principal can
recover the ground-truth ranking.

###  1.2 Related work

##### Rank Aggregation.

Ranking via pairwise comparisons can be considered as a subfield of rank
aggregation [28, 19, 22, 2]. Recent work on rank aggregation with pairwise
comparisons has built upon and extended these techniques [8, 18, 4, 5, 30].
Lin [17] provides an extensive introduction. Rank aggregation differs from our
work, which models the data sources as agents with differing reliability.

##### Crowdsourcing.

Crowdsourcing offers a cost-effective and efficient way to consolidate
feedback from a large number of non-experts. With the rise of crowdsourcing
platforms, such as Amazon Mechanical Turk, crowdsourcing has been commonly
used in a variety of applications, including sorting [4, 25, 1]. A central
task in crowdsourcing is modeling the reliability of annotators [4, 25]. Chen
et al. [4], for example, use the Bradley-Terry model for ranking aggregation,
assuming that annotators are either perfect or spammers (comparisons are
correct with probability 0.5). In contrast, we study a dynamic setting in
which annotators can be _incentivized_ to exert effort and therefore increase
the accuracy of their work.

##### Ordinal peer grading.

This area is most related to our work. With the rise of massive online open
courses (MOOCs), it has become increasingly important to decentralize the
grading process in an efficient manner that comes at a low cost to teaching
staff [21]. Peer grading can be a solution to this technical hurdle. Ordinal
peer grading (in which students are asked to rank other students’ work) is an
inexpensive, accurate, and robust way to assess performance [27]. However,
many works on ordinal peer grading draw on probabilistic methods to estimate
grader reliability and lack perspective on strategic interactions [24, 23,
20]. In contrast, works relating to aggregating feedback from strategic data
sources focus mostly on regression or cardinal evaluations of items [13, 12,
11, 31, 3]. Our work aims to bridge this gap using a contract between the
principal and the agents. The contract structures their interaction and
leverages their strategic behavior by incentivizing agents to perform accurate
comparisons. It also comes at a low cost to the principal while provably
retrieving the correct ranking of items.

##  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

In our model, there is one principal, $s$ agents $a_{1},\dots,a_{s}$, and a
set of $n$ items $T=\\{T_{1},\dots,T_{n}\\}$. Each item has an unknown ground-
truth score that measures some comparable feature that the principal wishes to
know. Based on these scores, there is a ground-truth permutation
$\mu^{*}:T\rightarrow[s]$ that sorts the items in ascending order. The
principal’s goal is to find $\mu^{*}$ by leveraging the agents’ ability to
estimate ground-truth scores and compare items based on that estimate.
However, agents’ comparisons can be unreliable. The principal can check the
accuracy of the agents’ work by verifying whether an agent’s returned
comparison is correct.

The principal proposes a contract to each agent, in which agent $a_{i}$ will
be assigned a set of pairs of items
$C_{i}=\\{(T_{k},T_{k}^{\prime})\\}_{k=1}^{|C_{i}|}$ and will be asked to
order each pair and return the result of every comparison. The principal will
verify the accuracy of a subset of the comparisons $a_{i}$ returns, but
$a_{i}$ does not know which subset. Through the contract, the principal
commits to providing some fixed compensation to each agent that correctly
compares all verified pairs of items. However, if at least one of them is
compared incorrectly, the agent does not receive any payment. The principal’s
goal is to retrieve the ground-truth ordering $\mu^{*}$ while minimizing
agents’ payment and the number of verifications she performs.

Each agent $a_{i}$ has a type $t_{i}\in$ {“good”, “bad”}, which captures his
ability to compare items. The principal does not observe $t_{i}$. If the agent
is “good”, then all comparisons he returns are correct with regards to
$\mu^{*}.$ If the agent is “bad” then he chooses a uniformly random
permutation $\mu\in M_{T}$, where $M_{T}$ is the set of all permutations
$\mu:T\to[n]$. He then returns all pairwise comparisons to be consistent with
the permutation chosen. More formally, if according to the permutation $\mu$,
the ground truth score of item $T_{j}$ is smaller than the ground-truth score
of item $T_{k}$, we denote:

$T_{j}<_{\mu}T_{k}=\mathbb{1}\\{\mu(T_{j})<\mu(T_{k})\\}$

An agent’s type depends on his strategic behavior, which the principal does
not observe. Each agent chooses whether to exert effort when comparing items
and commits to this choice upfront. We denote agent $a_{i}$’s effort using
$e_{i}\in\\{0,1\\}$. If $a_{i}$ exerts effort ($e_{i}=1$), then

$\mathbb{P}[t_{i}=\text{``good''}|e_{i}=1]=\pi$

Otherwise, $\mathbb{P}[t_{i}=\text{``good''}|e_{i}=0]=0$. We assume $\pi$ is
known to the principal, as is standard in contract theory.

The interaction proceeds as follows:

  1. 1.

The principal fixes a payment $p^{*}\in\mathbb{R}^{+}$ that she will pay
agents in order to incentivize them to exert effort.

  2. 2.

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

  3. 3.

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

  4. 4.

Agents are assigned verified and unverified comparisons.

  5. 5.

If agent $a_{i}$ returns at least one incorrect verified pair, he is
identified as “bad” and not compensated. We denote $c_{i}=\mathbb{1}\\{a_{i}$
is identified as “bad”$\\}$ and $\hat{\pi}=\mathbb{P}[c_{i}=1\mid
t_{i}=\text{``bad''}]$. (Identifying an agent depends on their type and is
independent of their effort conditioned on their type.)

  6. 6.

All agents not identified as “bad” receive payment $p^{*}$.

The principal obtains utility $u_{\mu^{*}}\geq 0$ which scales with the number
of comparisons returned by agents not identified as “bad”. She also
experiences disutility $\bar{\psi}\geq 0$ from performing each verification.
Meanwhile, agents who exert effort experience a per-comparison disutility of
$\psi\geq 0$. In this section, $\psi$ is common among all agents and known to
the principal. Section 3 relaxes thes assumptions.

Appendix A includes a table with our notation.

###  2.2 Agents’ incentives

We first determine the smallest amount the principal can pay the agents to
incentivize them to exert effort. We use the notation $\mathbb{E}[|C_{i}|]\leq
d$ to denote a bound on the expected number of comparisons that each agent
$a_{i}$ is asked to perform.

######  Lemma 2.1.

If the principal pays each agent $p^{*}\geq\frac{d\psi}{\hat{\pi}\pi},$ then
every agent is incentivized to exert effort.

For the remainder of this section, we set

$p^{*}=\frac{d\psi}{\hat{\pi}\pi}$ (1)

so for each agent $a_{i}$, $t_{i}=$ “good” with probability $\pi$.

###  2.3 Peer grading algorithm

We next present Algorithm 1, which, with high probability, returns all
comparisons needed to yield the ground-truth sorting. Algorithm 1 takes as
input the set of items $T$, the number of agents $s$, the number of pairs of
items $v=|V|$ to be verified by the principal, and the number of agents $r$
that each comparison is assigned to. Algorithm 1 partitions all $\binom{n}{2}$
pairs of items into disjoint subsets
$V,\\{W_{i}\\}_{i=1}^{s}\subseteq[n]\times[n]$, by calling algorithms findVset
and findWset respectively. We define $V$ as the set of pairwise comparisons
that the principal verifies and $W_{i}$ as the set of unverified comparisons
assigned to agent $a_{i}$. Algorithm 1 assigns to agent $a_{i}$ the set
$C_{i}=V\cup W_{i}$. Each agent returns sets $R_{V}$ and $R_{W_{i}}$, which
are the pairwise comparisons of the sets $V$ and $W_{i}$ respectively. If the
agent returns an incorrect verified comparison, Algorithm 1 adds the agent to
the set $B$ of “bad” agents that have been identified. The algorithm then
returns $B$ along with all comparisons returned by agents not identified as
“bad”.

Algorithm 1 CrowdSort($T,s,v,r,\delta$)

1:Let $B=\emptyset$

2:$V=\textsc{findVset}(T,v)$ $\triangleright$ choose comparisons to verify

3:$\\{W_{i}\\}_{i=1}^{s}=\textsc{findWset}(T,s,r)$ $\triangleright$ split
$[n]^{2}$ into subsets

4:for $i\in[s]$ do

5: Assign $C_{i}=V\cup W_{i}$ to agent $a_{i}$ and obtain the set of returned
comparisons $R_{V}$ and $R_{W_{i}}$

6: if there exists incorrect element in $R_{V}$ then

7: $B\leftarrow B\cup\\{i\\}$

8:return $B$, $\bigcup_{i\in[s]\setminus B}(R_{V}\cup R_{W_{i}})$

###  2.4 Allocation of items

In this section, we describe our algorithms for assigning verified and
unverified pairs of items to agents (findVset and findWset, respectively) and
show that: (1) for every verified pairwise comparison $(T_{i},T_{j})\in V$
assigned to a “bad” agent, the agent outputs $(T_{i}<_{\mu}T_{j})=1$ with
probability $1/2$, and (2) a “bad” agent performs each verified pairwise
comparison independently from all others. In Lemma 2.4 we use these two
properties to prove that with high probability, Algorithm 1 identifies all
“bad” agents, using the fact that each “bad” agent is not identified with
probability $\frac{1}{2^{|V|}}$.

####  2.4.1 Assigning verified comparisons.

In order to guarantee that a “bad” agent will be identified through Algorithm
1 with probability $1-1/2^{|V|}$, it suffices to create the sets $V$ and
$\\{W_{i}\\}_{i=1}^{s}$ such that each “bad” agent can only sample the output
of each verified comparison independently from Bernoulli$(1/2)$. We say a
verified comparison is _redundant_ if a “bad” agent does not sample the result
of the comparison from Bernoulli($1/2$) conditioned on the realization of all
other comparisons in $V$.

######  Definition 2.2.

Let $a_{i}$ be an agent such that $t_{i}=$ “bad” and $E_{i,m,m^{\prime}}$ be
the event that agent $a_{i}$ with $t_{i}=$ “bad” reports that the ground truth
score of item $T_{m}$ is smaller than that of item $T_{m^{\prime}}$. We say
that $C_{i}\subseteq T\times T$ contains a _redundant pair_
$(T_{j},T_{j^{\prime}})$ if:

$\mathbb{P}\left[E_{i,j,j^{\prime}}\mid
E_{i,k,k^{\prime}}\;\forall(T_{k},T_{k^{\prime}})\in
V\setminus\\{(T_{j},T_{j^{\prime}})\\}\right]\neq\frac{1}{2}.$

######  Lemma 2.3.

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

###### Proof sketch.

We prove that when verified pairs are disjoint, the number of permutations
assigning $(T_{j}<_{\mu}T_{j}^{\prime})$ conditioned on all other verified
comparisons is exactly $|M_{T}|/2$. Therefore, no information can be inferred
about it. ∎

Based on Lemma 2.3, findVset$(T,v)$ chooses $2v$ arbitrary items and
arbitrarily pairs them. We next bound the number of verifications sufficient
to catch all “bad” agents.

######  Lemma 2.4.

If each item in $V$ appears in no more than one pair and
$|V|\geq\log\left(2(1-\pi)s/\delta\right)$, then with probability
$1-\frac{\delta}{2}$ over $t_{1},...,t_{s}\sim\textnormal{Bernoulli}(\pi)$,
CrowdSort($T,s,|V|,r,\delta$) returns

$B=\\{i\mid\forall a_{i}\;\text{s.t.}\;t_{i}=\text{``bad''}\\}.$

####  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.

######  Lemma 2.5.

Suppose $v\geq\log\left(2(1-\pi)s/\delta\right)$. Let

$r\geq\frac{1}{\log(1-\pi)}\log\left(\frac{\delta}{2n^{2}}\right)$

be the number of agents each comparison is assigned to. Then with probability
$1-\delta$, CrowdSort($T,s,v,r,\delta$) returns the ground-truth ordering.

Based on this lemma, we define

$r^{*}=\frac{\log\left(\frac{\delta}{3n^{2}}\right)}{\log(1-\pi)}\quad\text{
and }\quad v^{*}=\log\left(\frac{2(1-\pi)s}{\delta}\right).$ (2)

_Algorithm overview._ findWset (Algorithm 2) assigns each agent $rn/s$
disjoint subsets of items, each containing approximately $\sqrt{n}$ items. The
agent is asked for all comparisons within each subset—or in other words, a
total ordering of each subset. (Note that to compute a total ordering of a
subset, the agent only needs to manually perform $\tilde{O}(\sqrt{n})$
comparisons, leading to a total of $\tilde{O}(rn^{3/2}/s)$ comparisons.)

To create these subsets, findWset calls the algorithm SGP which is from the
literature on a classic combinatorial problem, the _social golfer problem_. We
include algorithm SGP for completeness in Appendix B (Algorithm 3). SGP
generates approximately $\sqrt{n}$ partitions of the items, where each
partition consists of approximately $\sqrt{n}$ disjoint subsets of equal size,
such that every pair of elements are in the same subset in exactly one
partition (Theorem B.2). findWset then round-robin assigns each agent $rn/s$
subsets.

Connecting to the social golfer problem guarantees that each agent will be
assigned as few as $O(rn^{3/2}/s)$ items. At the same time, SGP distributes
items into subsets such that every pair of items appears in the same subset
_exactly once_. This allows the principal to assign the corresponding pairwise
comparison to exactly $r$ agents.

_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 $\sqrt{n}.$

_Technical details about the algorithm._ A technical hurdle we face is that
SGP only returns a solution when the square root of the number of elements is
prime [29, see Theorem B.2 in Appendix B]. findWset therefore calls
findPrime$(\sqrt{n})$, which returns the smallest prime $q$ such that
$q\geq\sqrt{n}$. Then findWset generates a set $\tilde{T}$ of $q^{2}-n$
hallucinated items which, along with the set of existing items $T$, are passed
to SGP. Agents are not asked to sort any hallucinated items. Assuming Cramer’s
conjecture holds (a well-known conjecture which states that the difference
between consecutive prime numbers grows poly-logarithmically),
$q=\tilde{O}(\sqrt{n}),$ so this complication comes at minimal cost. We now
bound the number of items and comparisons assigned to each agent.

######  Lemma 2.6.

Assuming Cramer’s conjecture holds, each agent is assigned
$\tilde{\mathscr{O}}(n^{3/2}/s)$ items and $\tilde{\mathscr{O}}(n^{3/2}/s)$
comparisons.

Algorithm 2 findWset($T,s,r$)

1:$\\{W_{i}\\}_{i=1}^{s}=\emptyset^{s}$

2:$q=$ findPrime$(\sqrt{|T|})$

3:Generate a set $\tilde{T}$ of hallucinated papers s.t. $|\tilde{T}|=q^{2}-T$

4:$\\{P_{0},\dots,P_{q-1}\\}=$ SGP$(T\cup\tilde{T})$

5:Arbitrarily split agents into $G_{0},\dots,G_{s/r}$ groups

6:$k=0$

7:for $\ell=0,\dots,q-1$ do $\triangleright$ iterate over partitions

8: for $c=0,\dots,q/r$ do $\triangleright$ iterate over subsets

9: for $j$ s.t. $a_{j}\in G_{k}$ do

10: $W_{j}\leftarrow\ \\{(T_{i},T_{j})\;|\;T_{i},T_{j}\in
T\wedge(T_{i},T_{j})\in(P_{\ell})_{c(rn/s)+n}\times(P_{\ell})_{c(rn/s)+n}\\}_{n=0}^{rn/s-1}$$\triangleright$
assign to $rn/s$ agents

11: $k\leftarrow k+1$

12:Return $(\\{W_{1},\cdots,W_{s}\\})$

###  2.5 Principal’s incentives

We synthesize our results in the following theorem, in which we additionally
prove that if the principal’s disutility $\bar{\psi}$ is sufficiently larger
than the agents’ disuility $\psi$, 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.

######  Theorem 2.7.

Suppose that the principal pays agents $p^{*}$ and runs
CrowdSort($T,s,v^{*},r^{*},\delta$). Then:

  1. 1.

Assuming Cramer’s conjecture, each agent performs
$\tilde{\mathscr{O}}(n^{3/2}/s)$ pairwise comparisons.

  2. 2.

The principal verifies $\mathscr{O}(\log{(s/\delta)})$ comparisons.

  3. 3.

With probability $1-\delta$, the correct ranking is retrieved.

  4. 4.

Assume that $\delta<1/s^{2}$ and $\pi$ is bounded away from $1$. If
$\bar{\psi}/\psi=\Omega(\sqrt{n}\log{n})$, then the principal’s expected
utility is at least the utility she would get if she were to perform all
pairwise comparisons on her own.

##  3 Agents with unknown disutilites

We now significantly expand our model to study heterogeneous agents with
differing, unknown disutilities. The full proofs of all results in this
section are in Appendix C.

###  3.1 Model and notation

In this section, agent $a_{i}$ experiences per-comparison disutility
$\psi_{i}\in\mathbb{R}^{+}$ while exerting effort. Having different levels of
disutility is a natural extension to our model as they can capture differing
levels of difficulty agents find in comparing items. We assume that
$\psi_{1},\dots,\psi_{s}$ are independently and identically distributed
according to some distribution $\mathscr{D}$. The realized disutility of each
agent is known to the agent, but unknown to the principal and all other
agents. The principal has access to an estimate of the distribution
$\mathscr{D}$ by way of a function $\hat{F}(\psi),$ such that
$|\hat{F}(\psi)-F(\psi)|\leq\epsilon$ for all $\psi$, where $F(\psi)$ is the
CDF of $\mathscr{D}$. The function $\hat{F}$ could be the empirical CDF based
on $O(1/\epsilon^{2})$ samples, for example, as per the
Dvoretzky–Kiefer–Wolfowitz inequality. Without loss of generality, we assume
that $\psi_{1}<\psi_{2}<\cdots<\psi_{s}$ and make no further distributional
assumptions.

Some agents might experience high disutility when exerting effort, so it may
not be in the principal’s best interest to incentivize all agents to exert
effort. Therefore, the principal must set the payment so that the number of
agents incentivized is utility maximizing for the principal. For the rest of
this section, we denote by $g$ the number of agents that the principal aims to
incentivize; in Theorem 3.6, we describe an efficient optimization problem
that solves for the optimal value of $g$, denoted $g^{*}$. The principal
controls the number of incentivized agents only through the payment function.
Hence, the realized number of agents that exert effort, denoted $\hat{g}$, is
a random variable with a distribution that depends on the payment. Under this
model, the principal will:

  1. 1.

Calculate $g^{*}$, the optimal number of agents to incentivize.

  2. 2.

Announce the payment $p_{g^{*}}\in\mathbb{R}^{+}$ (based on $g^{*}$).

  3. 3.

Verify a subset of comparisons assigned to the agents.

  4. 4.

Assign each comparison to a total of $r$ agents.

  5. 5.

Pay $p_{g^{*}}$ to all agents not identified as “bad.”

###  3.2 Payment function

The following analysis provides a lower bound on the payment $p_{g}$ required
so that approximately $g$ agents exert effort. We denote the payment function
as $p_{i}(c_{i})=p_{g}\mathbb{1}\\{c_{i}\neq 1\\}$. The full proof of the
following lemma is in Appendix C.

######  Lemma 3.1.

Suppose $p_{g}\geq\frac{d\psi_{i}}{\hat{\pi}\pi}$, where $d$ denotes an upper
bound on the expected number of pairwise comparisons performed by an agent.
Then agent $a_{i}$ is incentivized to exert effort.

Given $d$, the number of agents incentivized to exert effort depends solely on
the disutilities $\psi_{i}$ of each agent, so the approximate distribution of
the number of agents exerting effort is known to the principal and can be used
to determine the payment function. In the following lemma, we upper bound the
probability that an agent exerts effort, which implies an upper bound on the
total payment.

In the following lemma, we denote $\tilde{F}$ to be the quantile function with
respect to $F$, i.e $\tilde{F}(p)=\inf\\{x\in\mathbb{R}:p\leq F(x)\\}$.

######  Lemma 3.2.

Suppose the principal decides to incentivize $g$ agents. If the principal sets
$p_{g}\leq\frac{d}{\hat{\pi}\pi}\tilde{F}_{N}\left(\frac{g}{s}\right)$, then
the probability that any agent will exert effort is at most $g/s+\epsilon$, or
in other words, $\Pr_{\psi_{i}\sim\mathscr{D}}[\psi_{i}\geq p_{g}]\leq
g/s+\epsilon.$

###### Proof.

Let $p_{g}$ be the payment function when the principal decides to incentivize
$g$ agents. Then any agent exerts effort independently of all other agents if
and only if $p_{g}\geq\frac{d\psi_{i}}{\hat{\pi}\pi}$. Equivalently, this
happens if and only if

$\displaystyle\psi_{i}\leq\frac{p_{g}\hat{\pi}\pi}{d}.$

Thus, each agent exerts effort with probability
$q=F\left(\frac{p_{g}\hat{\pi}\pi}{d}\right)$ and the realized number of
incentivized agents, $\hat{g}$, follows a Binomial$(s,q)$ distribution.

We want the probability that an agent is incentivized to be at most $q\leq
g/s+\epsilon$, so we require:

$\displaystyle
F\left(\frac{p_{g}\hat{\pi}\pi}{d}\right)\leq\frac{g}{s}+\epsilon$ (3)

Since we only have access to $\hat{F}$, which is increasing, it suffices that:

$\displaystyle\hat{F}\left(\frac{p_{g}\hat{\pi}\pi}{d}\right)\leq\frac{g}{s}$

which holds if:

$p_{g}\leq\frac{d}{\hat{\pi}\pi}\tilde{F}_{N}\left(\frac{g}{s}\right).$

∎

For the remainder of this section, we set

$p_{g}=\frac{d}{\hat{\pi}\pi}\tilde{F}_{N}\left(\frac{g}{s}\right).$ (4)

######  Remark 3.3.

Notice that if Equation (4) holds, then the probability that any agent exerts
effort is

$\frac{g}{s}-\epsilon\leq
F\left(\frac{p_{g}\hat{\pi}\pi}{d}\right)\leq\frac{g}{s}+\epsilon.$

###  3.3 Correctness of CrowdSort

After choosing the payment function $p_{g}$ the principal will choose to
verify a subset of the binary comparisons, $V$. The size of this set
$v_{g}=|V|$ must be such that with high probability, all agents of type “bad”
are identified by algorithm CrowdSort($T,s,v_{g},r_{g},\delta$). The following
lemma provides a sufficient lower bound on the value of $v_{g}$.

######  Lemma 3.4.

Suppose that the principal chooses to verify a set of pairs of items, V, such
that each item in V appears in no more than one pair. Let
$v_{g}\geq\log_{2}\left(\frac{2(s-\pi g+\pi s\epsilon)}{\delta}\right)$ and
$p_{g}$ be the payment function, set according to Equation (4). Then with
probability $1-\frac{\delta}{2}$ over the types of the agents,
$t_{1},...,t_{s}$, CrowdSort($T,s,v_{g},r_{g},\delta$) returns
$B=\\{i|t_{i}=$“bad”$\\}$.

###### Proof.

We have that for any agent $a_{i}$:

$\displaystyle\mathbb{P}[t_{i}=\text{``bad''}]$
$\displaystyle=\mathbb{P}[t_{i}=\text{``bad''}|e_{i}=1]\cdot\mathbb{P}[e_{i}=1]+\mathbb{P}[e_{i}=0]$
$\displaystyle=(1-\pi)\cdot\mathbb{P}\left[\psi_{i}\leq\frac{\hat{\pi}\pi
p_{g}}{d}\right]+1-\mathbb{P}\left[\psi_{i}\leq\frac{\hat{\pi}\pi
p_{g}}{d}\right]$
$\displaystyle=1-\pi\cdot\mathbb{P}\left[\psi_{i}\leq\frac{\hat{\pi}\pi
p_{g}}{d}\right].$

By Remark 3.3, we know that for any agent $a_{i}$ it holds that
$\mathbb{P}\left[\psi_{i}\leq\frac{\hat{\pi}\pi
p_{g}}{d}\right]\geq\frac{g}{s}-\epsilon$, which means that:

$\displaystyle\mathbb{P}[t_{i}=\text{``bad''}]$ $\displaystyle\leq
1-\pi\frac{g}{s}+\pi\epsilon$ (5)

We also know that $\mathbb{P}[i\not\in B|t_{i}=\text{``bad''}]=1/2^{|V|}$, so
by taking the union bound over all agents, we have:

$\displaystyle\mathbb{P}[\exists i\ \text{s.t.}\ (t_{i}=\text{``bad''}\cap
i\not\in B)]$
$\displaystyle\leq\frac{s}{2^{|V|}}\cdot\left(1-\pi\frac{g}{s}+\pi\epsilon\right)$
(6)

We then upper bound this probability by $\delta/2$ and solve for $|V|,$ giving
us the following lower bound:

$\displaystyle|V|\geq\log_{2}\left(\frac{2(s-\pi g+\pi
s\epsilon)}{\delta}\right).$ (7)

∎

Next, we bound the redundancy required to ensure that CrowdSort returns the
ground-truth ordering.

######  Lemma 3.5.

Assume

$v_{g}\geq\log_{2}\left(\frac{2(s-\pi g+\pi s\epsilon)}{\delta}\right)$

and let

$r_{g}\geq\frac{\log_{2}\left(\frac{\delta}{2n^{2}}\right)}{\log_{2}\left(1-\frac{\pi
g}{s}+\pi\epsilon\right)}$

be the number of agents each comparison is assigned to. With probability
$1-\delta$, CrowdSort($T,s,v_{g},r_{g},\delta$) returns the ground-truth
sorting.

###### Proof.

We know from Lemma 3.4 that if

$|V|\geq\log_{2}\left(\frac{2(s-\pi g+\pi s\epsilon)}{\delta}\right),$

then with high probability, the algorithm $\textsc{CrowdSort}(T,s,v,r,\delta)$
identifies all “bad” agents. Therefore, it suffices to assign each comparison
to at least one “good” agent for the true value of the comparison to be
returned. By Remark 3.3, we know that for any agent $a_{i}$,

$\mathbb{P}_{\psi_{i}\sim\mathscr{D}}\left[\psi_{i}\leq\frac{\hat{\pi}\pi
p_{g}}{d}\right]\geq\frac{g}{s}-\epsilon.$

So the probability that all $r$ agents assigned to a single comparison are
“bad” is at most:

$\displaystyle\mathbb{P}(t_{i}=\text{bad}\;\forall a_{i}\in[r])$
$\displaystyle\leq\left(1-\frac{\pi g}{s}+\pi\epsilon\right)^{r}.$ (8)

Taking the union bound over all comparisons, we have that the probability
there exists a comparison such that all agents assigned to it are “bad” is at
most

$n^{2}\left(1-\frac{\pi g}{s}+\pi\epsilon\right)^{r}.$

Upper-bounding the above probability by $\delta/2$, we get that:

$\displaystyle
r\geq\frac{\log_{2}\left(\frac{\delta}{2n^{2}}\right)}{\log_{2}\left(1-\frac{\pi
g}{s}+\pi\epsilon\right)}$ (9)

Finally, notice that the above inequality and Inequality (6) hold
simultaneously with probability at least $1-\delta/2$.

Now let $E_{1}$ be the event that $B=\\{i|\forall a_{i}$ s.t.
$t_{i}=$“bad”$\\}$ and $E_{2}$ be the event that every pairwise comparison is
assigned to at least one “good” agent. For CrowdSort($T,s,v,r,\delta$) to
return the items’ ground truth ordering with probability at least $1-\delta$,
it suffices that all pairwise comparisons are assigned to at least one “good”
agent and that all comparisons performed by “bad” agents are eliminated i.e.
all “bad” agents are identified. This holds if $\mathbb{P}[E_{1}\cap
E_{2}]\geq 1-\delta$.

By Lemma 3.4 we have that $\mathbb{P}[E_{1}]\geq 1-\frac{\delta}{2}$. We also
know that if 9 holds, then $\mathbb{P}[E_{2}]\geq 1-\frac{\delta}{2}$. We want
to show that $\mathbb{P}[E_{1}\cap E_{2}]\geq 1-\delta$. It suffices to show
that $\mathbb{P}[\neg E_{1}\cup\neg E_{2}]\leq\delta$. This holds because by
the union bound $\mathbb{P}[\neg E_{1}\cup\neg E_{2}]\leq\mathbb{P}[\neg
E_{1}]+\mathbb{P}[E_{2}]\leq 2\frac{\delta}{2}=\delta$. ∎

###  3.4 Principal’s incentives

We combine the results presented above in the following theorem, in which we
additionally prove that it is possible for the principal to efficiently
compute the optimal number of agents to incentivize. Based on Lemma 3.5, we
use the notation

$v_{g}\geq\log_{2}\left(\frac{2(s-\pi g+\pi s\epsilon)}{\delta}\right)$

and

$r_{g}\geq\frac{\log_{2}\left(\frac{\delta}{2n^{2}}\right)}{\log_{2}\left(1-\frac{\pi
g}{s}+\pi\epsilon\right)}.$

######  Theorem 3.6.

Suppose that the principal pays agents $p_{g}$ and runs
CrowdSort($T,s,v_{g},r_{g},\delta$). Then:

  1. 1.

Assuming Cramer’s conjecture holds, each agent performs
$\tilde{\mathscr{O}}(n^{3/2}/s)$ pairwise comparisons.

  2. 2.

The principal verifies $\mathscr{O}(\log{(s/\delta)})$ comparisons.

  3. 3.

With probability $1-\delta$, the correct ranking is retrieved.

  4. 4.

In $O(s)$ time, it is possible to compute the value $g^{*}\in\\{0,\dots,s\\}$
such that the principal’s expected utility is maximized compared to all
choices of $g\in[s]$.

In our experiments, we show that for $\bar{\psi}/\psi$ sufficiently large, it
is profitable for the principal to incentivize agents rather than sort all
items herself.

##  4 Experiments

In the following section, we present experiments that test our models and
algorithm. We evaluate the impact of our algorithm on the principal’s utility
compared to when she chooses not to incentivize agents, the efficacy of our
algorithm in returning correct pairwise comparisons, and the robustness of our
model to noisy values of $\psi$ and $\pi$.

##### Experimental procedure.

Unless otherwise specified, we keep the following set of hyperparameter values
across our experiments: $\pi=0.8$, $\delta=0.01$, $s=100$, $n=100$,
$\bar{\psi}=2$, and $\psi=0.01$. Peer grading is an example of a setting where
$s=n$ since the number of assignments is the same as the number of students.
In Appendix D, we include experiments with a broad variety of parameter
settings.

Since we add noise to our model in these experiments, CrowdSort may not catch
all bad agents and thus may return conflicting comparisons. We discard all
conflicting comparisons (see Algorithm 4 in Appendix D). Despite this
pessimistic post-processing strategy, our experiments show that we can recover
most comparisons even under noise.

###  4.1 Principal’s utility

(a) No noise added to $\psi$.

(b) Noise added to $\psi$.

Figure 1: Principal’s utility as a function of $\psi$.

In Figure 1(a), we plot the principal’s utility as a function of $\psi$111In
Appendix D, we plot the principal’s utility as $\pi$ varies.. The blue line
shows the principal’s utility when she runs CrowdSort with $p^{*}$, $v^{*}$,
and $r^{*}$ defined in Equations (1) and (2) (we describe this calculation in
more detail in the next paragraph). The blue shading is a 90% confidence
interval across 50 trials. The red line shows the principal’s utility if she
performed all comparisons herself. Finally, the green line shows the
theoretical threshold when $s=n$ is $\bar{\psi}/\psi=\Omega(\sqrt{s}\log{s})$
from Theorem 2.7 (we use the value of this threshold without big-Omega
notation: Equation (11) from the proof). This indicates the value of $\psi$
for which the principal is indifferent between running CrowdSort or performing
all comparisons herself.

The empirical utilities are calculated as follows. Let $m$ be the number of
agents not identified as “bad” by CrowdSort and $k$ be the number of
comparisons after post-processing. We set $\lambda=2$ to be the principal’s
per-comparison utility and define

$U_{p^{*}}=\lambda k-\bar{\psi}|V|-p^{*}m$

to be her empirical utility for running CrowdSort with $p^{*}$, $v^{*}$, and
$r^{*}$ defined in Equations (1) and (2). Similarly,

$U_{0}=\lambda\binom{n}{2}-2\bar{\psi}n\log n$

is her expected utility for performing all comparisons herself, where $2n\log
n$ is the expected number of comparisons required by quicksort (this value
could easily be adjusted for any sorting algorithm). For ease of comparison,
the y-axis is scaled by dividing all values by the baseline utility $U_{0}$.

We note that the size of the confidence interval decreases with $\pi$. For
small values of $\pi$, a small number of agents are “good”, even though all
agents exert effort. Then with higher probability, $k$ will be small. This
corresponds to higher variance in the principal’s utility across trials.

In Figure 1(b), we add noise to the parameter $\psi$ and analyze the effect on
the principal’s utility. We sample the disutility of each agent independently
and identically from the distribution Uniform($\psi-0.5\psi,\psi+0.5\psi$).
However, we still calculate $p^{*}$, $v^{*}$, and $r^{*}$ from Equations (1)
and (2) using $\psi$ itself instead of the noisy version. The blue shading
corresponds to a 90% confidence interval across 50 trials.

_Discussion._ Comparing Figures 1(a) and 1(b), we can see that even when noise
is added to our model, our theoretical threshold is close to the point at
which the principal’s utility from running CrowdSort dips below their utility
from performing all comparisons herself. This demonstrates that our
theoretical results are robust to noise in the model.

When adding noise to $\psi$, the principal must pay fewer agents because fewer
are incentivized to exert effort. Thus, we see a steeper decline in Figure
1(a) compared to 1(b).

###  4.2 Number of pairwise comparisons returned

We evaluate the ability of CrowdSort to return enough correct comparisons to
recover the ground-truth sorting after post-processing.

(a) Effect of noise in parameter $\psi$ on the number of comparisons returned
as a function of the payment.

(b) Effect of noise in parameter $\pi$ on the number of comparisons returned
as a function of the payment.

Figure 2: Plots showing the number of comparisons returned as a function of
$\pi$ and $\psi$. The heat plots indicate the support of uniformly sampled
noise added to $\psi$ and $\pi$.

Figures 2(a) and 2(b) show the number of pairwise comparisons the algorithm
returns as a function of the payment given to agents not identified as “bad”.
The horizontal lines equal $\binom{n}{2}=\binom{100}{2}=4950$. The vertical
line equals the payment $p^{*}$ from Equation (1), which is a lower bound,
above which agents are incentivized to exert effort.

The multi-colored plots in Figure 2(a) indicate the number of comparisons
returned when noise is added to $\psi$. Given a value $H$ from the heatmap,
each agent’s disutility equals $\psi+\eta_{i}$ where $\psi=0.01$ and
$\eta_{i}\sim\text{Uniform}(0,H)$. Lighter-colored plots correspond to larger
values of $H$, which means fewer binary comparisons are returned. Each plot
indicates the average number of comparisons returned across 50 trials.

Similarly, the multi-colored plots in Figure 2(b) indicate the number of
comparisons returned when noise is added to $\pi$. Given a value $H$ from the
heatmap, each agent’s probability $\pi_{i}=\Pr[t_{i}=\textnormal{``good''}\mid
e_{i}=1]$ equals $\pi-\eta_{i}$ where $\pi=0.8$ and
$\eta_{i}\sim\text{Uniform}(0,H).$ Each plot indicates the average number of
comparisons returned across 10 iterations.

##### Discussion.

These experiments show that our algorithm retrieves all comparisons in the
absence of noise. Moreover, even when a large amount of noise is added to
$\psi$ or $\pi$, our algorithm returns almost all of the comparisons with
sufficient payment, despite the post-processing phase excluding any
conflicting comparison, again illustrating our algorithm’s robustness.

###  4.3 Optimization problem

In Section 3, we relaxed the assumption that the principal knows the agents’
disutilities by letting each agent’s disutility be i.i.d drawn from a
distribution $\mathscr{D}$ the principal only has sample access to.

Figure 3: Principal’s utility as a function of the number of agents
incentivized $g$.

In Figure 3, we plot the principal’s utility as a function of the number of
agents incentivized. The horizontal line denotes the principal’s utility if
she were to perform all comparisons herself. The multicolored plots indicate
the principal’s utility for different sample sizes (namely, 40, 145, and 500)
drawn from $\mathscr{D}$, which in this case is $\mathscr{N}(0.03,0.01)$.

We use parameter values $\bar{\psi}=\lambda=3$. Each line indicates the
average number of comparisons returned across 50 trials. Notice that many
values of $g$ cannot be used as they cause the input to logarithms (e.g.,
defining $r^{*}$) to be negative.

_Discussion._ For suitable values of $g$, approximately $40$ samples are
required for the utility of the principal under our model to surpass the
utility she would get, if she were to perform all pairwise comparisons
herself. We also notice that the principal’s utility increases as we increase
either $g$ or the number of samples. This result is shown in the multi-colored
plots in Figure 3. Therefore, even for a small number of samples, the
principal’s utility when implementing CrowdSort is well above her utility if
she performed all comparisons on her own.

##  5 Conclusions and future directions

We studied the multifaceted problem of designing a crowdsourcing mechanism
that efficiently and accurately ranks a set of items using pairwise
comparisons from rational agents. We based our approach on the classic
principal-agent model from contract theory. To distribute comparisons among
agents, we used an unexpected connection to the social golfer problem which
allowed us to simultaneously minimize the agents’ workload and ensure enough
agents evaluate each comparison. We showed that by optimizing the payment
mechanisms, the principal can incentivize enough agents to exert effort,
ensuring our algorithm recovers the ground-truth ranking. Our experiments
showed that even when noise is added to our original model, our method
consistently aids the principal in retrieving the accurate ground-truth
ordering.

Our results open up a variety of questions for future research. We assumed
agents cannot collude, which allowed us to assign the same set of verified
comparisons to all agents. How should our mechanism change if agents can
collude? Moreover, we assumed that agents who do not exert effort will return
comparisons consistent with a uniformly-random permutation of the items. What
other models of agent behavior can we study under this framework? Finally, as
is standard in contract theory, we assumed that the principal knows the
probability $\pi$ that an effortful agent is good. How should we handle the
case where $\pi$ is unknown?

## References

  * Asudeh et al. [2015] Abolfazl Asudeh, Gensheng Zhang, Naeemul Hassan, Chengkai Li, and Gergely V. Zaruba.  Crowdsourcing pareto-optimal object finding by pairwise comparisons.  In _Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (CIKM)_ , 2015.
  * Bradley and Terry [1952] Ralph Allan Bradley and Milton E Terry.  Rank analysis of incomplete block designs: I. the method of paired comparisons.  _Biometrika_ , 39(3/4):324–345, 1952.
  * Cai et al. [2015] Yang Cai, Constantinos Daskalakis, and Christos Papadimitriou.  Optimum statistical estimation with strategic data sources.  In _Conference on Learning Theory (COLT)_ , 2015.
  * Chen et al. [2013] Xi Chen, Paul N Bennett, Kevyn Collins-Thompson, and Eric Horvitz.  Pairwise ranking aggregation in a crowdsourced setting.  In _Proceedings of the International Conference on Web Search and Data Mining_ , pages 193–202, 2013.
  * Chen and Suh [2015] Yuxin Chen and Changho Suh.  Spectral MLE: Top-k rank aggregation from pairwise comparisons.  In _International Conference on Machine Learning (ICML)_ , 2015.
  * Duetting et al. [2022] Paul Duetting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim.  Combinatorial contracts.  In _Symposium on Foundations of Computer Science (FOCS)_ , 2022.
  * Ghose et al. [2012] Anindya Ghose, Panagiotis G Ipeirotis, and Beibei Li.  Designing ranking systems for hotels on travel search engines by mining user-generated and crowdsourced content.  _Marketing Science_ , 31(3):493–520, 2012.
  * Guiver and Snelson [2009] John Guiver and Edward Snelson.  Bayesian inference for plackett-luce ranking models.  In _International Conference on Machine Learning (ICML)_ , 2009.
  * Guo et al. [2012] Stephen Guo, Aditya Parameswaran, and Hector Garcia-Molina.  So who won? dynamic max discovery with the crowd.  In _Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data_ , SIGMOD ’12, page 385–396, New York, NY, USA, 2012. Association for Computing Machinery.  ISBN 9781450312479.  doi: 10.1145/2213836.2213880.  URL https://doi.org/10.1145/2213836.2213880.
  * Guruganesh et al. [2021] Guru Guruganesh, Jon Schneider, and Joshua Wang.  Contracts under moral hazard and adverse selection.  In _ACM Conference on Economics and Computation (EC)_ , 2021.
  * Jurca and Faltings [2009] R. Jurca and B. Faltings.  Mechanisms for making crowds truthful.  _Journal of Artificial Intelligence Research_ , 34:209–253, mar 2009.  doi: 10.1613/jair.2621.  URL https://doi.org/10.1613%2Fjair.2621.
  * Jurca and Faltings [2006a] Radu Jurca and Boi Faltings.  Robust incentive-compatible feedback payments.  In _Workshop on Trading Agent Design and Analysis_ , 2006a.
  * Jurca and Faltings [2006b] Radu Jurca and Boi Faltings.  Minimum payments that reward honest reputation feedback.  In _ACM Conference on Economics and Computation (EC)_ , 2006b.
  * Kang et al. [2019] Jiawen Kang, Zehui Xiong, Dusit Niyato, Dongdong Ye, Dong In Kim, and Jun Zhao.  Toward secure blockchain-enabled internet of vehicles: Optimizing consensus management using reputation and contract theory.  _IEEE Transactions on Vehicular Technology_ , 68(3):2906–2920, 2019.
  * Kou et al. [2017] Ngai Meng Kou, Yan Li, Hao Wang, Leong Hou U, and Zhiguo Gong.  Crowdsourced top-k queries by confidence-aware pairwise judgments.  _Proceedings of the 2017 ACM International Conference on Management of Data_ , 2017.  URL https://api.semanticscholar.org/CorpusID:36647621.
  * Laffont and Martimort [2002] Jean-Jacques Laffont and David Martimort.  _Moral Hazard: The Basic Trade-Offs_ , pages 145–186.  Princeton University Press, 2002.  URL http://www.jstor.org/stable/j.ctv7h0rwr.8.
  * Lin [2010] Shili Lin.  Rank aggregation methods.  _Wiley Interdisciplinary Reviews: Computational Statistics_ , 2(5):555–570, 2010.
  * Lu and Boutilier [2011] Tyler Lu and Craig Boutilier.  Learning mallows models with pairwise preferences.  In _International Conference on Machine Learning (ICML)_ , 2011.
  * Mallows [1957] C. L. Mallows.  Non-null ranking models. i.  _Biometrika_ , 44:114–130, 1957.  URL https://api.semanticscholar.org/CorpusID:121527283.
  * Mi and Yeung [2015] Fei Mi and Dit-Yan Yeung.  Probabilistic graphical models for boosting cardinal and ordinal peer grading in moocs.  In _AAAI Conference on Artificial Intelligence_ , 2015.
  * Piech et al. [2013] Chris Piech, Jonathan Huang, Zhenghao Chen, Chuong Do, Andrew Ng, and Daphne Koller.  Tuned models of peer assessment in moocs.  In _Proceedings of The 6th International Conference on Educational Data Mining (EDM)_ , 2013.
  * Plackett [1975] R. L. Plackett.  The Analysis of Permutations.  _Journal of the Royal Statistical Society Series C_ , 24(2):193–202, June 1975.  doi: 10.2307/2346567.  URL https://ideas.repec.org/a/bla/jorssc/v24y1975i2p193-202.html.
  * Raman and Joachims [2014] Karthik Raman and Thorsten Joachims.  Methods for ordinal peer grading.  In _International Conference on Knowledge Discovery and Data Mining (KDD)_ , 2014.
  * Raman and Joachims [2015] Karthik Raman and Thorsten Joachims.  Bayesian ordinal peer grading.  In _Proceedings of the ACM Conference on Learning at Scale_ , 2015.
  * Raykar et al. [2010] Vikas C Raykar, Shipeng Yu, Linda H Zhao, Gerardo Hermosillo Valadez, Charles Florin, Luca Bogoni, and Linda Moy.  Learning from crowds.  _Journal of machine learning research_ , 11(4), 2010.
  * Shah et al. [2015] Nihar Shah, Sivaraman Balakrishnan, Joseph Bradley, Abhay Parekh, Kannan Ramchandran, and Martin Wainwright.  Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2015.
  * Shah et al. [2013] Nihar B Shah, Joseph K Bradley, Abhay Parekh, Martin Wainwright, and Kannan Ramchandran.  A case for ordinal peer-evaluation in moocs.  In _NIPS Workshop on Data-Driven Education_ , 2013.
  * Thurstone [1927] Louis Leon Thurstone.  The method of paired comparisons for social values.  _The Journal of Abnormal and Social Psychology_ , 21:384–400, 1927.  URL https://api.semanticscholar.org/CorpusID:144595330.
  * Triska [2008] Markus Triska.  _Solution Methods for the Social Golfer Problem_.  PhD thesis, Vienna University of Technology, March 2008.  Available from https://www.metalevel.at/mst.pdf.
  * Tsukida et al. [2011] Kristi Tsukida, Maya R Gupta, et al.  How to analyze paired comparison data.  _Department of Electrical Engineering University of Washington, Tech. Rep. UWEETR-2011-0004_ , 1, 2011.
  * Waggoner and Chen [2014] Bo Waggoner and Yiling Chen.  Output agreement mechanisms and common knowledge.  _Proceedings of the AAAI Conference on Human Computation and Crowdsourcing_ , 2(1):220–226, Sep. 2014.  doi: 10.1609/hcomp.v2i1.13151.  URL https://ojs.aaai.org/index.php/HCOMP/article/view/13151.
  * Zhu et al. [2023] Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan.  The sample complexity of online contract design.  In _ACM Conference on Economics and Computation (EC)_ , 2023.

##  Appendix A Summary of notation

Table 1: Summary of Most Commonly Used Notation Notation |  Definition
---|---
$a_{1},\cdots,a_{s}$ |  $s$ agents
$T=\\{T_{1},\cdots,T_{n}\\}$ |  set of $n$ items
$\mu^{*}:T\rightarrow[n]$ |  ground-truth permutation
$M_{T}$ |  set of all permutations $\mu:T\rightarrow[n]$
$V\subseteq[n]\times[n]$ |  verified set of pairs of items
$W=\\{W_{i}\\}_{i=1}^{s}$ |  collection of subsets of pairs of items assigned to $s$ agents
$t_{i}\in\\{\text{``good'', ``bad''}\\}$ |  type of agent $a_{i}$
$e_{i}\in\\{0,1\\}$ |  indicates whether agent $a_{i}$ exerts effort
$\pi\in[0,1]$ |  $\mathbb{P}[t_{i}=\text{``good''}|e_{i}=1]$
$c_{i}\in\\{0,1\\}$ |  indicates whether agent $a_{i}$ is identified as “bad”
$\hat{\pi}\in[0,1]$ |  $\mathbb{P}[c_{i}=1|t_{i}=\text{``bad''}]$
$\psi\in\mathbb{R}^{+}$ |  (Section 2) per-comparison disutility of agents
$\bar{\psi}$ |  per-comparison disutility of the principal
$\lambda$ |  per-comparison utility of the principal
$d$ |  upper bound on the expected number of pairwise comparisons each agent performs
$T_{j}<_{\mu}T_{k}$ |  indicates whether the ground truth score of $T_{j}$ under $\mu$ is smaller than that of $T_{k}$
$F,\hat{F},\tilde{F}$ |  CDF, estimate of CDF, quantile function corresponding to distribution $\mathscr{D}$ over disutilities
$\hat{g},g^{*}$ |  realized number and utility-maximizing number of incentivized agents

##  Appendix B Omitted proofs from Section 2

See 2.1

###### Proof.

Let $\mathbb{E}[|C_{i}|]\leq d$ for some $d>0$ be an upper bound on the
expected number of comparisons that each agent is asked to perform. We denote
agent $a_{i}$’s utility as $u_{i}$ and calculate its expected value given that
the agent exerts effort:

$\displaystyle\mathbb{E}[u_{i}|e_{i}=1]$
$\displaystyle=\mathbb{E}[p(c_{i})-|C_{i}|\psi\cdot e_{i}|e_{i}=1]$
$\displaystyle=p^{*}\mathbb{P}[p(c_{i})=p^{*}|e_{i}=1]-\mathbb{E}[|C_{i}|]\psi$

Since $p_{i}=p^{*}$ if either (1) $t_{i}$ = “good” or (2) $t_{i}$ = “bad” but
the agent is not identified as “bad” ($c_{i}=0$), we have:

$\displaystyle\mathbb{E}[u_{i}|e_{i}=1]$
$\displaystyle=p^{*}\left(\mathbb{P}[t_{i}=\text{``good''}|e_{i}=1]\right.$
$\displaystyle\left.+\mathbb{P}[t_{i}=\text{``bad''}\cap
c_{i}=0|e_{i}=1]\right)-\mathbb{E}[|C_{i}|]\psi$

With Bayes’ rule and simplifying we get:

$\displaystyle\mathbb{E}[u_{i}|e_{i}=1]$
$\displaystyle=p^{*}\pi+p^{*}\mathbb{P}[c_{i}=0|t_{i}=\text{``bad''},e_{i}=1]\mathbb{P}[t_{i}=\text{``bad''}|e_{i}=1]-\mathbb{E}[|C_{i}|]\psi$
$\displaystyle=p^{*}\pi+p^{*}(1-\hat{\pi})(1-\pi)-\mathbb{E}[|C_{i}|]\psi$

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

$\displaystyle\mathbb{E}[u_{i}|e_{i}=0]$
$\displaystyle=\mathbb{E}[p(c_{i})-|C_{i}|\psi\cdot e_{i}|e_{i}=0]$
$\displaystyle=p^{*}\mathbb{P}[p(c_{i})=p^{*}|e_{i}=0]$
$\displaystyle=p^{*}\mathbb{P}[c_{i}=0|t_{i}=\text{``bad''}]$
$\displaystyle=p^{*}(1-\hat{\pi})$

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

$\displaystyle\mathbb{E}[u_{i}|e_{i}=1]\geq\mathbb{E}[u_{i}|e_{i}=0].$

We use the quantities from above to get:

$\displaystyle p^{*}\pi+p^{*}(1-\hat{\pi})(1-\pi)-\mathbb{E}[|C_{i}|]\psi\geq
p^{*}(1-\hat{\pi})$

which holds if and only if $p^{*}\hat{\pi}\pi\geq\mathbb{E}[|C_{i}|]\psi$. By
$\mathbb{E}[|C_{i}|]\leq d$ and simplifying we get the lower bound:

$\displaystyle p^{*}\geq\frac{d\psi}{\hat{\pi}\pi}$ (10)

To satisfy individual rationality, we require that:

$\displaystyle\mathbb{E}[u_{i}|e_{i}=1]\geq 0$

which holds if and only if:

$\displaystyle p^{*}\pi+p^{*}(1-\hat{\pi})(1-\pi)-\mathbb{E}[|C_{i}|]\psi\geq
0$

and by simplifying we get:

$\displaystyle
p^{*}\geq\frac{\mathbb{E}[|C_{i}|]\psi}{1+\hat{\pi}\pi-\hat{\pi}}$

which is always satisfied if constraint 10 is satisfied. ∎

See 2.3

###### Proof.

Let $\tilde{\mu}\in M_{T}$ be the permutation that an arbitrary “bad” agent
$a_{i}$ chooses. We must show that for every pair of items
$(T_{V_{j}},T_{V_{j}^{\prime}})\in V$:

$\displaystyle\mathbb{P}\left[T_{V_{j}}<_{i}T_{V_{j}^{\prime}}\mid
T_{V_{k}}<_{i}T_{V_{k}^{\prime}}\quad\forall(T_{V_{k}},T_{V_{k}^{\prime}})\in
V\setminus\\{(T_{V_{j}},T_{V_{j}^{\prime}})\\}\right]=\frac{1}{2}$

or equivalently:

$\displaystyle\mathbb{P}\left[\underbrace{T_{V_{j}}<_{\tilde{\mu}}T_{V_{j}^{\prime}}}_{P_{1}}\mid\underbrace{T_{V_{k}}<_{\tilde{\mu}}T_{V_{k}^{\prime}}\quad\forall(T_{V_{k}},T_{V_{k}^{\prime}})\in
V\setminus\\{(T_{V_{j}},T_{V_{j}^{\prime}})\\}}_{P_{2}}\right]=\frac{1}{2}$

This holds if and only if the number of permutations that satisfy property
$P_{1}$ and property $P_{2}$ is exactly half of the number of permutations
that only satisfy property $P_{2}$. This holds since no items in the set V
appear in a pair more than once so $(T_{V_{j}},T_{V_{j^{\prime}}})$ is not
contained in $P_{2}$. Therefore, no information can be inferred about the
relative indices of items $T_{V_{j}}$ and $T_{V_{j}^{\prime}}$. ∎

See 2.4

###### Proof.

By Lemma 2.3 we have that each agent of type “bad” samples every verified
comparison i.i.d. from Bernoulli(1/2). Therefore, we have that for every “bad”
agent $a_{i}$:

$\displaystyle\mathbb{P}[i\not\in B\mid
t_{i}=\text{``bad''}]=\frac{1}{2^{|V|}}$

So, we know that:

$\displaystyle\mathbb{P}[(t_{i}=\text{``bad''})\cap(i\not\in
B)]=\mathbb{P}[(i\not\in
B)\;|\;(t_{i}=\text{``bad''})]\cdot\mathbb{P}[(t_{i}=\text{``bad''})]=\frac{1-\pi}{2^{|V|}}$

By taking the union bound over all agents we get:

$\displaystyle\mathbb{P}[\exists i\ \text{s.t.}\ (t_{i}=\text{``bad''}\cap
i\not\in B)]\leq\frac{(1-\pi)s}{2^{|V|}}$

Upper bounding this probability by $\delta/2$ and solving for $|V|$ gives us
the lower bound:

$\displaystyle|V|\geq\log\left(\frac{2(1-\pi)s}{\delta}\right)$

∎

See 2.5

###### Proof.

Assume that CrowdSort($T,s,v,r,\delta$) must return all $\binom{n}{2}$ correct
pairwise comparisons for the ground-truth ordering to be retireved. Since
$|V|\geq\log\left(\frac{2(1-\pi)s}{\delta}\right)$ we know from Lemma 2.4 that
with high probability CrowdSort($T,s,v,r,\delta$) identifies all “bad” agents.
Therefore, it suffices to assign each comparison to at least one ‘good” agent,
for the true value of the comparison to be returned. The number of “good”
agents in a set of $r$ agents follows a binomial distribution:

$\displaystyle\mathbb{P}[t_{i}=\text{bad}\;\forall a_{i}\in[r]]$
$\displaystyle=(1-\pi)^{r}$

so by the union bound over all comparisons we have that the probability that
there exists a pairwise comparison that is assinged to $r$ “bad” agents is at
most:

$\displaystyle n^{2}\mathbb{P}[t_{i}=\text{bad}\;\forall
a_{i}\in[r]]=n^{2}(1-\pi)^{r}\leq\frac{\delta}{2}$

Thus, we get that:

$\displaystyle r\geq\frac{\log\left(\frac{\delta}{n^{2}}\right)}{\log(1-\pi)}$

Now let $E_{1}$ be the event that $B=\\{i|\forall a_{i}$ s.t.
$t_{i}=$“bad”$\\}$ and $E_{2}$ be the event that every pairwise comparison is
assigned to at least one “good” agent. For CrowdSort($T,s,v,r,\delta$) to
return the items’ ground truth ordering with probability at least $1-\delta$,
it suffices that all pairwise comparisons are assigned to at least one “good”
agent and that all comparisons performed by “bad” agents are eliminated i.e.
all “bad” agents are identified. This holds if $\mathbb{P}[E_{1}\cap
E_{2}]\geq 1-\delta$.

By Lemma 2.4 we have that $\mathbb{P}[E_{1}]\geq 1-\frac{\delta}{2}$. We also
know $\mathbb{P}[E_{2}]\geq 1-\frac{\delta}{2}$. We want to show that
$\mathbb{P}[E_{1}\cap E_{2}]\geq 1-\delta$. It suffices to show that
$\mathbb{P}[\neg E_{1}\cup\neg E_{2}]\leq\delta$. This holds because by the
union bound $\mathbb{P}[\neg E_{1}\cup\neg E_{2}]\leq\mathbb{P}[\neg
E_{1}]+\mathbb{P}[E_{2}]\leq 2\frac{\delta}{2}=\delta$. ∎

See 2.6

###### Proof.

In findWset, the algorithm findPrime finds the smallest prime $q$, such that
$q\geq\sqrt{|T|}$. In findWset, each agent is assigned all pairwise
comparisons among non-hallucinated items within a subset, for
$r=\mathscr{O}(\log{n})$ subsets. Each subset consists of $q$ items, so each
agent will be asked to compare the following number of items:

$\displaystyle r\cdot\frac{n}{s}\cdot q$ $\displaystyle\leq
O\left(\log{n}\cdot\frac{n}{s}\cdot\left(\sqrt{|T|}+(q-\sqrt{|T|})\right)\right)$
$\displaystyle\leq
O\left(\log{n}\cdot\left(\sqrt{n}+(q-\sqrt{n})\right)\right)$
$\displaystyle\leq
O\left(\frac{n}{s}\log{n}\cdot(\sqrt{n}+(\log{\sqrt{n}})^{2})\right)$
$\displaystyle\leq\tilde{O}(n^{3/2}/s)$

where in the last step, we use Cramer’s conjecture, which states the
following: If $p_{n}$ and $p_{n+1}$ are two consecutive prime numbers, then:

$\displaystyle p_{n+1}-p_{n}=\mathscr{O}((\log p_{n})^{2})$

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:

$\displaystyle|W_{i}|$ $\displaystyle\leq
r\cdot\frac{n}{s}\cdot\mathscr{O}(q\log{q})$ ($rn/s$ subsets of $q$ items each
)
$\displaystyle\leq\mathscr{O}\left(\frac{n}{s}\log{n}\right)\cdot\mathscr{O}\left(\left(\sqrt{|T|}+(q-\sqrt{|T|})\right)\cdot\log{\left(\sqrt{|T|}+(q-\sqrt{|T|})\right)}\right)$
$\displaystyle\leq\mathscr{O}\left(\frac{n}{s}\log{n}\right)\cdot\mathscr{O}\left(\left(\sqrt{n}+(\log{\sqrt{n}})^{2}\right)\cdot\log{\left(\sqrt{n}+(\log{\sqrt{n}})^{2}\right)}\right)$
$\displaystyle\leq\mathscr{O}\left(\frac{n}{s}\log{n}\right)\cdot\mathscr{O}\left(\left(\sqrt{n}+(\log{\sqrt{n}})^{2}\right)\cdot\log{\sqrt{n}}\right)$
$\displaystyle\leq\mathscr{O}\left(\frac{n}{s}\log{n}\right)\cdot\mathscr{O}\left(\sqrt{n}\cdot\log{\sqrt{n}}\right)$
$\displaystyle\leq\mathscr{O}(\frac{n^{3/2}}{s}\log^{2}{n})$
$\displaystyle\leq\tilde{\mathscr{O}}(n^{3/2}/s),$

∎

######  Remark B.1.

In expectation the number of comparisons needed to fully sort $q$ items using
quicksort is at most $2q\ln{q}$. Therefore, we write that for every agent
$a_{i}$:

$\displaystyle\mathbb{E}[|C_{i}|]$
$\displaystyle=\mathbb{E}[|V|+|W_{i}|]\leq|V|+2rnq\ln{q}/s$

and we set $d=|V|+2rnq\ln{q}/s=\mathscr{O}(n^{3/2}\log^{2}{n}/s)$.

Algorithm 3 SGP($T=\\{T_{1},\cdots T_{q^{2}}\\}$)

1:$\sigma\leftarrow$ Uniform$(S_{q^{2}})$

2:for $k=1,2,\cdots,q-1$ do

3: for $(i,j)\in\mathbb{F}_{q}^{2}$ do

4: $L_{k-1}(i,j)\leftarrow ki+j$

5: for $l\in\mathbb{F}_{q}$ do

6: $R_{k-1,l}\leftarrow\\{\sigma^{-1}(i,j):L_{k-1}(i,j)=l\\}$

7: $P_{k-1}\leftarrow\\{R_{k-1,0},\cdots,R_{k-1,q-1}\\}$

8:for $l\in\mathbb{F}_{q}$ do

9:
$N_{l}\leftarrow\\{\sigma^{-1}(0,l),\sigma^{-1}(1,l),\cdots\sigma^{-1}(q-1,l)\\}$

10:
$M_{l}\leftarrow\\{\sigma^{-1}(l,0),\sigma^{-1}(l,1),\cdots\sigma^{-1}(l,q-1)\\}$

11:$P_{q-1}\leftarrow\\{M_{0},\cdots,M_{q-1}\\}$

12:$P_{q}\leftarrow\\{N_{0},\cdots,N_{q-1}\\}$

######  Theorem B.2.

[Triska [29]] For a prime power $q$, there exists a solution to the instance
SGP($q,q,q+1$), such that every pair of golfers plays against each other
exactly once.

###### Proof.

We want to prove that there exists a schedule such that $q^{2}$ players are
split into disjoint groups of $q$ players each for $q$ days such that no two
players are in the same group for more than one day.

Let $\mathbb{F}_{q}$ denote the GF(q) for the prime number q. We pick an
arbitrary bijection
$\sigma:\mathbb{F}_{q}^{2}\rightarrow\\{p_{1},\cdots,p_{q^{2}}\\}$ between
$q^{2}$ players and ordered pairs $(i,j)\in\mathbb{F}_{q}^{2}.$ For all $1\leq
k<q,$ let $L_{k}:\mathbb{F}_{q}^{2}\rightarrow\mathbb{F}_{q}$ be a function
such that $L_{k}(i,j)=ki+j$.

Now, it is easy to verify that for all $i\in\\{0,\cdots,q-1\\},k\in\\{1,\cdots
q-1\\}$, it holds that $L_{k}(i,:)$ contains the elements $1,\cdots q-1$
exactly once. (Property 1)

Also, notice that for any $i_{1},i_{2},j_{1},j_{2}\in\\{0,\cdots,q-1\\}$, and
$k\in\\{1,\cdots,q-1\\}$, if $L_{k}(i_{1},j_{1})=L_{k}(i_{2},j_{2})$, then
$\nexists m$ s.t. $L_{m}(i_{1},j_{1})=L_{m}(i_{2},j_{2})$. (Property 2). To
prove this, suppose that there exists $m$ s.t.
$L_{m}(i_{1},j_{1})=L_{m}(i_{2},j_{2}).$ Then we have
$ki_{1}+j_{1}=ki_{2}+j_{2}$ and $mi_{1}+j_{1}=mi_{2}+j_{2},$ so
$(i_{1}-i_{2})k=(i_{1}-i_{2})m.$ Since $\mathbb{F}_{q}$ is a finite field and
$k\neq m$, we must have $i_{1}=i_{2},$ which implies that $j_{1}=j_{2}$, a
contradiction.

Now let $W_{k}$ be a list of q sets that denotes day i consisting of q groups.
For $k\in\\{0,\cdots q-2\\}$, we set $W_{k}=(R_{k,1},\cdots,R_{k,q})$, where
$R_{k,l}$ is the set of all tuples in the domain of $L_{k}$ that map to $l$,
i.e. $R_{k,l}=\\{\sigma^{-1}(i,j):L_{k}(i,j)=l\\}$. For day $q$, we set
$W_{q}=\\{N_{0},\cdots N_{q-1}\\}$, where
$N_{l}=\\{\sigma^{-1}(0,l),\sigma^{-1}(1,l),\cdots\sigma^{-1}(q-1,l)\\}$ for
all $0\leq l<q$. For day q-1, we set $W_{q}=\\{M_{0},\cdots M_{q-1}\\}$, where
$M_{l}=\\{\sigma^{-1}(l,0),\sigma^{-1}(l,1),\cdots\sigma^{-1}(l,q-1)\\}$ for
all $0\leq l<q$. For day q, we set $W_{q}=\\{N_{0},\cdots N_{q-1}\\}$, where
$N_{l}=\\{\sigma^{-1}(0,l),\sigma^{-1}(1,l),\cdots\sigma^{-1}(q-1,l)\\}$ for
all $0\leq l<q$.

We will show that the collection $W_{1},\cdots,W_{q}$ is a valid assignment
scheme for the Social Golfer Problem. By Property 1, we know that for every
day, every player is assigned in a group and that groups are disjoint. By
Property 2, we know that for distinct indices
$(i_{1},j_{1})\neq(i_{2},j_{2})$, if
$L_{k}(i_{1},j_{1})=L_{k}(i_{2},j_{2})=l_{1}$, then $\nexists m$ s.t.
$L_{m}(i_{1},j_{1})=L_{m}(i_{2},j_{2})=l_{2}$. Thus any two elements assigned
to the same group in day $W_{k}$ cannot be assigned to the same group in day
$W_{m}$ for all $1\leq k\neq m<q$. Lastly, note that for all $1\leq k<q$ and
$0\leq a_{1},a_{2}<q,$ we have $L_{k}(a_{1},l)=ka_{1}+l\neq
ka_{2}+l=L_{k}(a_{2},l),$ so $\sigma_{-1}(a_{1},l),\sigma_{-1}(a_{2},l)\in
N_{l}$ are not assigned to the same part in any of $W_{1},\cdots W_{q-1},$ so
partition $W_{q}$ satisfies the desired properties when added to the
collection. A similar argument holds for $W_{q-1}$. Thus, our construction
$W_{1},\cdots,W_{q+1}$ is valid solution to the instance $SGP(q,q,q+1)$.

We have proved that each player will play with a group of $q-1$ different
players for $q+1$ days. There are $q^{2}$ players in total. Then, each player
will play against a total of $(q-1)(q+1)=q^{2}-1$ different players. So every
player will be in the same group with every other player exactly once.

∎

See 2.7

###### Proof.

Results (1), (2), (3) directly stem from Lemmas 2.6, 2.4, and 2.5
respectively. We denote with $u$ the utility of the principal and calculate
its expected value given that she sets the payment $p=p^{*}$. Recall that
$u_{\mu^{*}}$ is a constant multiple of the number of pairwise comparisons
that are returned by our algorithm.

$\displaystyle\mathbb{E}[u|p=p^{*}]=\mathbb{E}\left[u_{\mu^{*}}-\bar{\psi}|V|-p^{*}\sum_{i=1}^{s}\mathbb{1}\\{t_{i}=\text{``good''}\\}-p^{*}\sum_{i=1}^{s}\mathbb{1}\\{t_{i}=\text{``bad''},c_{i}=0\\}\mid
p=p^{*}\right]$

By Theorem 2.1 we know that if the principal sets the price to $p=p^{*}$ the
probability that any agent is “good” is $\pi$. By Lemma 2.4 we also know that
the probability that any agent is “bad” and not identified is
$\frac{1-\pi}{2^{|V|}}$. Therefore, we can write:

$\displaystyle\mathbb{E}[u|p=p^{*}]=\mathbb{E}[u_{\mu^{*}}]-\bar{\psi}|V|-p^{*}s\pi-p^{*}\frac{s(1-\pi)}{2^{|V|}}$

where here we define $|V|$ according to Lemma 2.4. Finally, by Lemma 2.5, with
probability at least $1-\delta$, algorithm CrowdSort returns all
$\binom{n}{2}$ ground-truth pairwise comparisons. Therefore,
$\mathbb{E}[u_{\mu^{*}}]\geq(1-\delta)\lambda\binom{n}{2}$ for some
$\lambda\in\mathbb{R^{+}}$. So, we get that:

$\displaystyle\mathbb{E}[u|p=p^{*}]\geq\lambda(1-\delta)\binom{n}{2}-\bar{\psi}|V|-p^{*}s\pi-p^{*}\frac{s(1-\pi)}{2^{|V|}}$

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:

$\displaystyle\mathbb{E}[u|p=0]=\lambda\binom{n}{2}-2\bar{\psi}n\log{n}$

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:

$\displaystyle\mathbb{E}[u|p=p^{*}]\geq\mathbb{E}[u|p=0]$

We substitute the values of the utilities found above along with the
appropriate values for $|V|=\log\left(\frac{2(1-\pi)s}{\delta}\right)$ to get:

$\displaystyle\lambda(1-\delta)\binom{n}{2}-\bar{\psi}\log\frac{2(1-\pi)s}{\delta}-p^{*}s\pi-p^{*}\frac{s(1-\pi)}{\frac{2(1-\pi)s}{\delta}}\geq\lambda\binom{n}{2}-2\bar{\psi}n\log{n}$

which holds if and only if:

$\displaystyle-\lambda\delta\binom{n}{2}-p^{*}\left(s\pi+\frac{\delta}{2}\right)\geq\bar{\psi}\left(\log{\frac{2(1-\pi)s}{\delta}}-2n\log{n}\right)$

We substitute the values $p^{*}=\frac{d\psi}{\hat{\pi}\pi}$ and
$\hat{\pi}=1-1/2^{|V|}$ to get:

$\displaystyle\lambda\delta\binom{n}{2}+\frac{d\psi}{1-\frac{\delta}{2(1-\pi)s}}\left(s+\frac{\delta}{2\pi}\right)\leq\bar{\psi}\left(2n\log{n}-\log{\frac{2(1-\pi)s}{\delta}}\right)$
(11)

By Remark B.1, we know that $d=\mathscr{O}(n^{3/2}\log^{2}{n}/s)$ and assuming
that $\delta<(1/n^{2})$ and that $\pi$ is bounded away from $1$, we get that:

$\displaystyle\bar{\psi}/\psi\geq\Omega\left(\frac{ds}{n\log{n}}\right)=\Omega(\sqrt{n}\log{n})$

∎

##  Appendix C Omitted proofs from Section 3

See 3.1

###### Proof.

We denote agent $a_{i}$’s utility as $u_{i}$ and following a similar analysis
as in Lemma 2.1 we have that:

$\displaystyle\mathbb{E}[u_{i}|e_{i}=1]=p_{g}\pi+p_{g}(1-\hat{\pi})(1-\pi)-|C_{i}|\psi_{i}$

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

$\displaystyle\mathbb{E}[u_{i}|e_{i}=0]=p_{g}(1-\hat{\pi})$

For agent $a_{i}$ to be incentivized to exert effort, the payment needs to be
such that:

$\displaystyle\mathbb{E}[u_{i}|e_{i}=1]\geq\mathbb{E}[u_{i}|e_{i}=0].$

Using $\mathbb{E}[|C_{i}|]<d$ and simplifying we get the lower bound:

$\displaystyle p_{g}\geq\frac{d\psi_{i}}{\hat{\pi}\pi}$ (12)

To satisfy individual rationality, we require the following:

$\displaystyle\mathbb{E}[u_{i}|e_{i}=1]\geq 0$

which holds if and only if:

$\displaystyle
p_{g}\geq\frac{\mathbb{E}[|C_{i}|]\psi_{i}}{1+\hat{\pi}\pi-\hat{\pi}}$

which is always satisfied as long as constraint 12 is satisfied. ∎

See 3.6

###### Proof.

Results (1), (2), (3) directly stem from Lemmas 2.6, 3.4, and 3.5
respectively. We denote as $v$ the utility of the principal and calculate its
expected value given that she decides to incentivize at least $g$ agents and
set the payment $p=p_{g}$. Recall that $u_{\mu^{*}}$ is the utility of the
principal if the resulting sorting of the items coincides with the ground-
truth permutation $\mu^{*}$. Here, $u_{\mu}^{*}$ scales with the number of
comparisons the principal retrieves from the agents.

$\displaystyle\mathbb{E}[u|p=p_{g}]=\mathbb{E}\left[u_{\mu^{*}}-\bar{\psi}|V|-p_{g}\sum_{i=1}^{s}\mathbb{1}\\{t_{i}=\text{``good''}\\}-p_{g}\sum_{i=1}^{s}\mathbb{1}\\{t_{i}=\text{``bad''},c_{i}=0\\}\mid
p=p_{g}\right]$

By Remark 3.3 we know that if the principal sets the price to $p=p_{g}$ then
with probability at least $1-\delta/4$ the probability that any given agent is
“good” is at most $\pi(\frac{g}{s}+\epsilon)$. By Lemma 3.4 we also know that
with probability at least $1-\delta/4$ the probability that any agent is “bad”
and not identified is at most $\frac{1}{2^{|V|}}(1-\frac{\pi
g}{s}+\pi\epsilon)$. We substitute
$u_{\mu^{*}}\geq\lambda(1-\delta)\binom{n}{2}$ for some
$\lambda\in\mathbb{R}^{+}$ by Lemma 3.5 . Therefore, we have that:

$\displaystyle\mathbb{E}[u|p=p_{g}]\geq\lambda(1-\delta)\binom{n}{2}-\bar{\psi}|V|-sp_{g}\left(\left(1-\frac{\delta}{4}\right)\pi\left(\frac{g}{s}+\epsilon\right)+\frac{\delta}{4}\right)-sp_{g}\left(\left(1-\frac{\delta}{4}\right)\frac{1}{2^{|V|}}\left(1-\pi\frac{g}{s}+\pi\epsilon\right)+\frac{\delta}{4}\right)$

where here we take $|V|$ satisfying the conditions from Lemma 3.4 and using
the fact that
$\hat{\pi}=\mathbb{P}[c_{i}=1|t_{i}=\text{``bad''}]=1-1/2^{|V|}$.

Let $E(p_{g})$ denote the lower bound above. For the algorithm to be
incentive-compatible for the principal, it must hold that:

$\displaystyle\mathbb{E}[u|p=p_{g}]\geq
E(p_{g})\geq\mathbb{E}[v|p=0]=u_{\mu^{*}}-2\bar{\psi}n\log{n}$

where the first inequality follows from above. Therefore the optimization
problem for a suitable $g^{*}$ is the following:

$\displaystyle g^{*}$ $\displaystyle=\arg\max_{g\in[s]}\;E(p_{g})$

such that:

$\displaystyle\left.\begin{aligned} |V|&\geq\log_{2}\left(\frac{2(s-\pi g+\pi
s\epsilon)}{\delta}\right)\\\
r_{g}&\geq\frac{\log_{2}\left(\frac{\delta}{2n^{2}}\right)}{\log_{2}\left(1-\frac{\pi
g}{s}+\pi\epsilon\right)}\end{aligned}\right\\}\text{correctness of
algorithm}$

$\displaystyle\left.\begin{aligned}
p_{g}=\frac{d}{\hat{\pi}\pi}\tilde{F}_{N}\left(\frac{g}{s}\right)\end{aligned}\right\\}\text{relaxed
incentive compatibility for agents}$

$\displaystyle\left.\begin{aligned} E(p_{g})\geq
u_{\mu^{*}}-2\bar{\psi}n\log{n}\end{aligned}\right\\}\text{incentive
compatibility for principal}$

Notice that the objective is increasing in $|V|$ and in $p_{g}$ (therefore
also in $d$). Thus, the inequality constraints above can be turned into
equality constraints, fixing the values of $|V|$ and $r$ to their minimum
feasible values without changing the outcome of the optimization. Therefore,
the above problem can be solved in $O(s)$ time by iterating over all
$g\in[s]$.

∎

##  Appendix D Additional Information about Experiments

###  D.1 Post-processing algorithm

Algorithm 4 Post-Process(comparisons, identified)

1:condensed = {}

2:conflicts = {}

3:for agent $\in$ s do

4: if agent not in identified then

5: for “$i<j$” in comparisons[agent] do

6: if “$i<j$” in condensed or “$i<j$” in conflicts then

7: continue

8: if “$j<i$” in condensed then

9: conflicts $\leftarrow$ conflicts $\cup$ {“$j<i$”, “$i<j$”}

10: condensed $\leftarrow$ condensed $\setminus$ {“$i<j$”}

11: else

12: condensed $\leftarrow$ condensed $\cup$ {“$i<j$”}

13:Return condensed

Algorithm 4 takes as input “comparisons”, which is a list of $s$ sublists,
each containing the returned results of the binary comparisons performed by an
agent. Each result is represented with a string of the form “$i<j$”,
representing that according to the agent, the true score of item $T_{i}$ is
smaller than that of item $T_{j}$. The input “identified” is a set containing
the indeces of all agents who returned at least one verified comparison
incorrectly.

Algorithm 4 iterates through the comparisons returned by agents not in the set
“identified” and adds them to the set “condensed”, which will be returned at
the end. If the comparison is already in the set “condensed”, then it is not
added again. If there has been another agent whose returned comparison
disagrees with it, then the comparison is added to the set “conflicts” (if not
already added), and is removed from the set “condensed”. Consequently, if
there is at least one agent that disagrees on a comparison with all other
agents assigned the same comparison, then algorithm 4 will completely
disregard it. Finally, algorithm 4 returns the set condensed, which has size
at most $\binom{n}{2}$.

###  D.2 Principal’s utility vs. parameter $\pi$

The plot shows a monotonic increase in the principal’s utility as $\pi$
increases. The shaded region corresponds to a 90% confidence interval across
15 iterations. We notice that for any value of $\pi$ that is greater than
$0.35$, it is in the principal’s best interest to implement our contract
instead of performing all pairwise comparisons herself.

Figure 4: Principal’s utility as a function of parameter $\pi$.

###  D.3 Additional Hyper-parameter settings from Section 4

For the remainder of this section, we fix the hyper-parameter settings found
in Section 4, unless otherwise stated. Namely, we assume that $\pi=0.8$,
$\delta=0.01$, $n=100$, $s=100$, $\bar{\psi}=2$, and $\psi=0.01$.

_Discussion of Figure 5._ In Figure 5 we provide additional hyper-parameter
settings for Figure 1(a) in Section 4. First, we select the probability of an
effortful agent being “good” to be a value in $\\{0.3,0.6,0.9\\}$ and the
number of agents and items to be in the set $\\{50,200\\}$. In plots 5(a)-5(c)
results are averaged across 15 trials, while in plots 5(d)\- 5(f), results are
averaged across 10 trials. The blue shading corresponds to a 90% confidence
interval. We notice that the confidence intervals decrease with the number of
agents, even for a small number of trials. The confidence intervals also
decrease, as the agents’ work becomes more predictable ($\pi$ increases).

We find that as $\pi$ increases, the principal’s utility also increases along
with the threshold for $\psi$, below which it is in the principal’s best
interest to run CrowdSort than perform all comparisons herself. This threshold
also decreases with the number of agents, $s$. This implies that there is a
sweet spot, in which the expected number of “good” agents is just enough that
the ground-truth ordering of the items is retrieved and it is sufficiently
small so that the principal can pay all of them.

(a) $\pi=0.3$ and $s=50$

(b) $\pi=0.6$ and $s=50$

(c) $\pi=0.9$ and $s=50$

(d) $\pi=0.3$ and $s=200$

(e) $\pi=0.6$ and $s=200$

(f) $\pi=0.9$ and $s=200$

Figure 5: Principal’s utility as a function of parameter $\psi$ (in the
absence of noise)

_Discussion of Figure 6._ In Figure 6 we provide additional hyper-parameter
settings for Figure 1(a) in Section 4. Specifically, we select the per-
comparison disutility of the principal, $\bar{\psi}$, along with the per-
comparison utility of the principal, $\lambda$, to take values in
$\\{4,6,8\\}$. The number of agents and items is in the set $\\{200,500\\}$
and our results are averaged across 2 trials with the blue shading
corresponding to a 90% confidence interval.

We notice that the utility of the principal dramatically increases with the
value she assigns to the correct ordering. Interestingly, by comparing Figure
5(f) to Figures 6(a)-6(a), we find that even when the reliability of the
agents is smaller ($\pi=0.8$ in 5(f) and $\pi=0.9$ in 6(a)-6(c)), the
principal’s point of indifference is higher when her disutility is larger. As
before, we notice that when a large number of agents is incentivized, their
labor needs to be sufficiently inexpensive (smaller threshold on $\psi$) for
their work to be more profitable to the principal than performing all pairwise
comparisons herself.

Lastly, our results show, that for a broad range of hyperparameters, our
theoretical analysis accurately predicts the value of $\psi$, for which the
principal is indifferent between running CrowdSort or performing all
comparisons herself.

(a) $\bar{\psi}=4$ and $s=200$

(b) $\bar{\psi}=6$ and $s=200$

(c) $\bar{\psi}=8$ and $s=200$

(d) $\bar{\psi}=4$ and $s=500$

(e) $\bar{\psi}=6$ and $s=500$

(f) $\bar{\psi}=8$ and $s=500$

Figure 6: Principal’s Utility as a function of parameter $\psi$ (in the
absence of noise)

(a) $\pi=0.3$ and $s=50$

(b) $\pi=0.6$ and $s=50$

(c) $\pi=0.9$ and $s=50$

(d) $\pi=0.3$ and $s=200$

(e) $\pi=0.6$ and $s=200$

(f) $\pi=0.9$ and $s=200$

Figure 7: Principal’s utility as a function of parameter $\psi$ (with noise)

_Discussion of Figure 7._ We provide additional parameter settings
corresponding to Figure 1(b). The parameters $\pi$ and $s$ along with the
number of trials vary as in Figure 5. We find that as the number of agents to
be incentivized grows, our theoretical analysis for the principal’s point of
indifference becomes more accurate. Also, noise on the disutilites results in
many agents not being incentivized to exert effort and therefore get paid.
This increases the principal’s utility, especially when parameter $\pi$ is
large, therefore resulting in a less steep slope. As in Figure 1(b), we note
that the confidence intervals become larger with $\psi$, as the principal’s
utility shows higher variance, when less agents are “good”.

_Discussion of Figures 8 and 9._ We provide additional parameter settings
corresponding to Figure 2. In Figure 8, we select the probability of an
effortful agent being “good” to be a value in $\\{0.3,0.6,0.9\\}$, while in
Figure 9, we select the disutility of an effortful agent to be a value in
$\\{0.02,0.04,0.06\\}$. The number of agents $s$ is in the set $\\{50,200\\}$.
In plots 8(a)-8(c) and 9a-9c results are averaged across 10 trials, while in
plots 8(d)-8(f) and 9(d)-9(f), results are averaged across 5 trials. In Figure
8, we see that the payment required to incentivize agents increases with the
number of items, which amplifies the effect of noisy disutilites on the number
of comparisons returned. Also, we find that more reliable agents (higher
values of $\pi$) significantly reduce the effect of noise on the number of
comparisons returned as they converge faster to the optimal $\binom{n}{2}$.
Comparing Figures 8 and 9, we find that the noisy values of $\pi$ have a
smaller impact on the number of comparisons returned compared to noisy values
of $\psi$.

(a) $\pi=0.3$ and $s=50$

(b) $\pi=0.6$ and $s=50$

(c) $\pi=0.9$ and $s=50$

(d) $\pi=0.3$ and $s=200$

(e) $\pi=0.6$ and $s=200$

(f) $\pi=0.9$ and $s=200$

Figure 8: Number of comparisons returned as a function of parameter $\psi$

(a) $\psi=0.02$ and $s=50$

(b) $\psi=0.04$ and $s=50$

(c) $\psi=0.06$ and $s=50$

(d) $\psi=0.02$ and $s=200$

(e) $\psi=0.04$ and $s=200$

(f) $\psi=0.06$ and $s=200$

Figure 9: Number of comparisons returned as a function of parameter $\pi$

_Discussion of Figure 10._ In Figure 10 we offer a range of parameters
corresponding to Figure 3 in Section 4. Specifically, we vary the probability
than an effortful agent is “good”, which take values in $\\{0.3,0.6,0.9\\}$
and the principal’s per-comparison disutility, $\psi$, and utility $\lambda$,
which takes values in $\\{4,6,8\\}$. The multicolored plots indicate the
principal’s utility for different sample sizes (namely, $10,20,100$, and
$500$) drawn from $\mathscr{D}$, which in this case is
$\mathscr{N}(0.03,0.01)$. Notice that we do not normalize the y-axis in this
case. Results are averaged across 10 trials.

We see that as agents become more reliable (higher value of $\pi$) and as the
principal’s value for the correct sorting grows ($\lambda$), it becomes
increasingly beneficial to the principal to run CrowdSort, than perform all
pairwise comparisons on her own. Interestingly, even if $\pi$ is $0.3$, for
sufficiently large values of $\bar{\psi}$, the agent’s work is more profitable
to the principal than sorting herself. This suggests that for a sufficiently
large value of $\bar{\psi}/{\psi}$, incentivizing agents under our proposed
contract is substantially more beneficial to the principal than sorting the
items herself.

(a) $\bar{\psi}=4$ and $\pi=0.3$

(b) $\bar{\psi}=4$ and $\pi=0.6$

(c) $\bar{\psi}=4$ and $\pi=0.9$

(d) $\bar{\psi}=6$ and $\pi=0.3$

(e) $\bar{\psi}=6$ and $\pi=0.6$

(f) $\bar{\psi}=6$ and $\pi=0.9$

(g) $\bar{\psi}=8$ and $\pi=0.3$

(h) $\bar{\psi}=8$ and $\pi=0.3$

(i) $\bar{\psi}=8$ and $\pi=0.9$

Figure 10: Principal’s utility as a function of parameter g