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 2 Warm-up: Agents with known equal disutility As a warm up to our main result, in this section, we propose a contract assuming that (a) the principal knows the agents’ disutilites and (b) every agent experiences the same value of per-comparison disutility (assumptions we relax in Section 3). We begin with a formal model in Section 2.1 and define the optimal payment in Section 2.2. In Sections 2.3 and 2.4, we present our main algorithm CrowdSort for computing the correct sorting. Section 2.5 identifies conditions under which the principal gets higher utility when implementing our proposed contract than when performing all pairwise comparisons herself. The full proofs of all results in this section are in Appendix B. 2.1 Model and notation The interaction proceeds as follows: 1. The principal fixes a payment p∗ ∈ R+ that she will pay agents in order to incentivize them to exert effort. 2. The principal verifies a subset of the comparisons and announces the size of this set to the agents. 3. Agents choose whether to exert effort, which fixes their type upfront. 4. Agents are assigned verified and unverified comparisons. 2.2 Agents’ incentives 2.3 Peer grading algorithm 2.4 Allocation of items 2.4.1 Assigning verified comparisons. Lemma 2.3. If each item in V appears in exactly one pair, then no pair in V is redundant. 2.4.2 Assigning unverified comparisons. We now define findWset. First, we bound the number of agents each comparison must be assigned to in order to retrieve the ground-truth sorting. Details about the social golfer problem. In the social golfer problem, the goal is to determine whether m golfers can play together in g groups of p (where m = gp) for w days in such a way that (1) no two golfers play in the same group more than once, and (2) each golfer plays exactly once each day. Thus, an instance of this problem is defined by integers (g, p, w). For us, the golfers correspond to the items, the days correspond to the partitions, and the groups of golfers correspond to the sets in the partitions. Thus, we aim to solve this problem with g, p, and w all approximately equal to √n. 2.5 Principal’s incentives We synthesize our results in the following theorem, in which we additionally prove that if the principal’s disutility ψ¯ is sufficiently larger than the agents’ disuility ψ, then it is in the principal’s best interest to use our mechanism rather than perform all pairwise comparisons herself. This is a natural assumption, which implies that the principal would have to be compensated sufficiently more per comparison than the agents for their work to be profitable to the principal. This paper is available on Arxiv under CC 4.0 license. 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 2 Warm-up: Agents with known equal disutility As a warm up to our main result, in this section, we propose a contract assuming that (a) the principal knows the agents’ disutilites and (b) every agent experiences the same value of per-comparison disutility (assumptions we relax in Section 3). We begin with a formal model in Section 2.1 and define the optimal payment in Section 2.2. In Sections 2.3 and 2.4, we present our main algorithm CrowdSort for computing the correct sorting. Section 2.5 identifies conditions under which the principal gets higher utility when implementing our proposed contract than when performing all pairwise comparisons herself. The full proofs of all results in this section are in Appendix B. 2.1 Model and notation The interaction proceeds as follows: 1. The principal fixes a payment p∗ ∈ R+ that she will pay agents in order to incentivize them to exert effort. 2. The principal verifies a subset of the comparisons and announces the size of this set to the agents. 3. Agents choose whether to exert effort, which fixes their type upfront. 4. Agents are assigned verified and unverified comparisons. 2.2 Agents’ incentives 2.3 Peer grading algorithm 2.4 Allocation of items 2.4.1 Assigning verified comparisons. Lemma 2.3. If each item in V appears in exactly one pair, then no pair in V is redundant. Lemma 2.3. If each item in V appears in exactly one pair, then no pair in V is redundant. 2.4.2 Assigning unverified comparisons. We now define findWset. First, we bound the number of agents each comparison must be assigned to in order to retrieve the ground-truth sorting. Details about the social golfer problem. In the social golfer problem, the goal is to determine whether m golfers can play together in g groups of p (where m = gp) for w days in such a way that (1) no two golfers play in the same group more than once, and (2) each golfer plays exactly once each day. Thus, an instance of this problem is defined by integers (g, p, w). For us, the golfers correspond to the items, the days correspond to the partitions, and the groups of golfers correspond to the sets in the partitions. Thus, we aim to solve this problem with g, p, and w all approximately equal to √n. Details about the social golfer problem. 2.5 Principal’s incentives We synthesize our results in the following theorem, in which we additionally prove that if the principal’s disutility ψ¯ is sufficiently larger than the agents’ disuility ψ, then it is in the principal’s best interest to use our mechanism rather than perform all pairwise comparisons herself. This is a natural assumption, which implies that the principal would have to be compensated sufficiently more per comparison than the agents for their work to be profitable to the principal. This paper is available on Arxiv under CC 4.0 license. Arxiv Arxiv

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

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Comparative Algorithm Audit: Conspiracy Theories in the Online Environments

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: Omitted Proofs From Section 2

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

Additional Information About the Algorithmic Contract Design Experiments: What You Should Know

A Comparative Algorithm Audit: Conspiracy Theories in the Online Environments

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: Omitted Proofs From Section 2

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

Additional Information About the Algorithmic Contract Design Experiments: What You Should Know

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps