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 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 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 ˆg, is a random variable with a distribution that depends on the payment. Under this model, the principal will: 1. Calculate g∗, the optimal number of agents to incentivize. 2. Announce the payment pg∗ ∈ R+ (based on g∗). 3. Verify a subset of comparisons assigned to the agents. 4. Assign each comparison to a total of r agents. 5. Pay pg∗ to all agents not identified as “bad.” 3.2 Payment function 3.3 Correctness of CrowdSort Next, we bound the redundancy required to ensure that CrowdSort returns the groundtruth ordering. Proof. We know from Lemma 3.4 that if then with high probability, the algorithm CrowdSort(T, s, v, r, δ) 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 ai, So the probability that all r agents assigned to a single comparison are “bad” is at most: 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 Upper-bounding the above probability by δ/2, we get that: Finally, notice that the above inequality and Inequality (6) hold simultaneously with probability at least 1 − δ/2. 3.4 Principal’s incentive 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 and 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 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 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 ˆg, is a random variable with a distribution that depends on the payment. Under this model, the principal will: 1. Calculate g∗, the optimal number of agents to incentivize. 2. Announce the payment pg∗ ∈ R+ (based on g∗). 3. Verify a subset of comparisons assigned to the agents. 4. Assign each comparison to a total of r agents. 5. Pay pg∗ to all agents not identified as “bad.” 3.2 Payment function 3.3 Correctness of CrowdSort Next, we bound the redundancy required to ensure that CrowdSort returns the groundtruth ordering. Proof. We know from Lemma 3.4 that if then with high probability, the algorithm CrowdSort(T, s, v, r, δ) 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 ai, So the probability that all r agents assigned to a single comparison are “bad” is at most: r 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 Upper-bounding the above probability by δ/2, we get that: Finally, notice that the above inequality and Inequality (6) hold simultaneously with probability at least 1 − δ/2. 3.4 Principal’s incentive 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 and This paper is available on Arxiv under CC 4.0 license. This paper is available on Arxiv under CC 4.0 license. Arxiv Arxiv

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

Algorithmic Contract Design: What to Know About Agents With Unknown Disutilites

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

A Comparative Algorithm Audit: Conspiracy Theories in the Online Environments

Algorithmic Contract Design for Crowdsourced Ranking: An Introduction to Get You Started

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: Conclusions, Future Directions, and References

A Comparative Algorithm Audit: Conspiracy Theories in the Online Environments

Algorithmic Contract Design for Crowdsourced Ranking: An Introduction to Get You Started

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: Conclusions, Future Directions, and References

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps