This paper is available on arxiv under CC 4.0 license.
Authors:
(1) Kiriaki Frangias;
(2) Andrew Lin;
(3) Ellen Vitercik;
(4) Manolis Zampetakis. 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. This paper is available on arxiv under CC 4.0 license. Authors: (1) Kiriaki Frangias; (2) Andrew Lin; (3) Ellen Vitercik; (4) Manolis Zampetakis. This paper is available on arxiv under CC 4.0 license. Authors : Authors (1) Kiriaki Frangias; (2) Andrew Lin; (3) Ellen Vitercik; (4) Manolis Zampetakis. Table of Links Abstract and Introduction Abstract and Introduction Warm-up: Agents with known equal disutility Warm-up: Agents with known equal disutility Agents with unknown disutilites Agents with unknown disutilites Experiments Experiments Conclusions and future directions, References Conclusions and future directions, References A Summary of notation A Summary of notation B Omitted proofs from Section 2 B Omitted proofs from Section 2 C Omitted proofs from Section 3 C Omitted proofs from Section 3 D Additional Information about Experiments 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.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 Lemma 2.5. be the number of agents each comparison is assigned to. Then with probability 1 − δ, be the number of agents each comparison is assigned to. Then with probability 1 − δ, CrowdSort(T, s, v, r, δ) returns the ground-truth ordering. 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: Theorem 2.7. 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. This paper is available on Arxiv under CC 4.0 license. Arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Algorithmic Contract Design for Crowdsourced Ranking: What Was Left Out of Section 3

Algorithmic Contract Design for Crowdsourced Ranking: Definitions You Should Know

Read My Stories

Too Long; Didn't Read

Make resilience your competitive advantage

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Exploring Benefits of Using Alternative Search Engines

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

Algorithmic Contract Design for Crowdsourced Ranking: A Deeper Look at Our Experiments

Algorithmic Contract Design for Crowdsourced Ranking: Definitions You Should Know

Algorithmic Contract Design for Crowdsourced Ranking: What Was Left Out of Section 3

Exploring Benefits of Using Alternative Search Engines

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

Algorithmic Contract Design for Crowdsourced Ranking: A Deeper Look at Our Experiments

Algorithmic Contract Design for Crowdsourced Ranking: Definitions You Should Know

Algorithmic Contract Design for Crowdsourced Ranking: What Was Left Out of Section 3

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps