You are organizing a conference that has received n submitted papers. Your goal is to get people to review as many of them as possible. To do this, you have enlisted the help of k reviewers. Each reviewer i has a cost sij for writing a review for paper j. The strategy of each reviewer i is to select a subset of papers to write a review for. They can select any subset S; C {1,2,.,n}, as long as the total cost to write all reviews is less than T (the time before the deadline): E Sij ST. jeS; Reviews are costly, so you want to reward them for their efforts. However, each paper and review has to be treated equally: specifically, there is a budget of 1 for each paper, that will be evenly shared across all reviewers who reviewed that paper. For example, if 4 reviewers reviewed a paper they will receive 1/4 each. If only one reviewer reviews the paper they will receive all the reward. Of course, each reviewer i wants to maximize their utility u;, which is the reward R; over all papers they receive minus the effort they put into writting reviews: U; = R; – Sij. jeS; You can assume that for the given s;j's, there is a combination of strategies S; where every reviewer has positive utility and all papers get at least one review. However, this outcome might not be a pure Nash equilibrium. As a designer, your goal is to find the fraction of papers that receive at least 1 review at a pure Nash equilibrium, for the worst possible combination of s;j's satisfying the assumption. (a) Show that there exists a set of si;'s such that the fraction of papers that receive reviews is close to 1/n. Given the previous negative result, you think about increasing the reward of each paper from 1 to B > 1. (b) Show that for B = 2 this fraction is close to 1/3. [Hint: You can consider an instance with 3n +1 papers and only n will be reviewed.]
You are organizing a conference that has received n submitted papers. Your goal is to get people to review as many of them as possible. To do this, you have enlisted the help of k reviewers. Each reviewer i has a cost sij for writing a review for paper j. The strategy of each reviewer i is to select a subset of papers to write a review for. They can select any subset S; C {1,2,.,n}, as long as the total cost to write all reviews is less than T (the time before the deadline): E Sij ST. jeS; Reviews are costly, so you want to reward them for their efforts. However, each paper and review has to be treated equally: specifically, there is a budget of 1 for each paper, that will be evenly shared across all reviewers who reviewed that paper. For example, if 4 reviewers reviewed a paper they will receive 1/4 each. If only one reviewer reviews the paper they will receive all the reward. Of course, each reviewer i wants to maximize their utility u;, which is the reward R; over all papers they receive minus the effort they put into writting reviews: U; = R; – Sij. jeS; You can assume that for the given s;j's, there is a combination of strategies S; where every reviewer has positive utility and all papers get at least one review. However, this outcome might not be a pure Nash equilibrium. As a designer, your goal is to find the fraction of papers that receive at least 1 review at a pure Nash equilibrium, for the worst possible combination of s;j's satisfying the assumption. (a) Show that there exists a set of si;'s such that the fraction of papers that receive reviews is close to 1/n. Given the previous negative result, you think about increasing the reward of each paper from 1 to B > 1. (b) Show that for B = 2 this fraction is close to 1/3. [Hint: You can consider an instance with 3n +1 papers and only n will be reviewed.]
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
Can anyone help me solve the game theory exercise? Without using Ford-Fulkerson
![Exercise 4
You are organizing a conference that has received n submitted papers. Your goal is to get people to review as many
of them as possible. To do this, you have enlisted the help of k reviewers. Each reviewer i has a cost sij for writing a
review for paper j. The strategy of each reviewer i is to select a subset of papers to write a review for. They can select
any subset S; C{1,2,.,n}, as long as the total cost to write all reviews is less than T (the time before the deadline):
2 Sij <T.
jeS;
Reviews are costly, so you want to reward them for their efforts. However, each paper and review has to be treated
equally: specifically, there is a budget of 1 for each paper, that will be evenly shared across all reviewers who reviewed
that paper. For example, if 4 reviewers reviewed a paper they will receive 1/4 each. If only one reviewer reviews
the paper they will receive all the reward. Of course, each reviewer i wants to maximize their utility u;, which is the
reward R; over all papers they receive minus the effort they put into writting reviews:
Ui = R;
> Sij.
jeS;
You can assume that for the given si;'s, there is a combination of strategies S; where every reviewer has positive
utility and all papers get at least one review. However, this outcome might not be a pure Nash equilibrium. As a
designer, your goal is to find the fraction of papers that receive at least 1 review at a pure Nash equilibrium, for the
worst possible combination of sij's satisfying the assumption.
(a) Show that there exists a set of s;;'s such that the fraction of papers that receive reviews is close to 1/n.
Given the previous negative result, you think about increasing the reward of each paper from 1 to B > 1.
(b) Show that for B = 2 this fraction is close to 1/3. [Hint: You can consider an instance with 3n +1 papers and
only
n will be reviewed.]](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F71f4daa0-cfb1-4f36-b8af-232f3138bbf3%2F9eb640ef-7273-4068-94d9-d20410400be4%2Fv7zm12_processed.png&w=3840&q=75)
Transcribed Image Text:Exercise 4
You are organizing a conference that has received n submitted papers. Your goal is to get people to review as many
of them as possible. To do this, you have enlisted the help of k reviewers. Each reviewer i has a cost sij for writing a
review for paper j. The strategy of each reviewer i is to select a subset of papers to write a review for. They can select
any subset S; C{1,2,.,n}, as long as the total cost to write all reviews is less than T (the time before the deadline):
2 Sij <T.
jeS;
Reviews are costly, so you want to reward them for their efforts. However, each paper and review has to be treated
equally: specifically, there is a budget of 1 for each paper, that will be evenly shared across all reviewers who reviewed
that paper. For example, if 4 reviewers reviewed a paper they will receive 1/4 each. If only one reviewer reviews
the paper they will receive all the reward. Of course, each reviewer i wants to maximize their utility u;, which is the
reward R; over all papers they receive minus the effort they put into writting reviews:
Ui = R;
> Sij.
jeS;
You can assume that for the given si;'s, there is a combination of strategies S; where every reviewer has positive
utility and all papers get at least one review. However, this outcome might not be a pure Nash equilibrium. As a
designer, your goal is to find the fraction of papers that receive at least 1 review at a pure Nash equilibrium, for the
worst possible combination of sij's satisfying the assumption.
(a) Show that there exists a set of s;;'s such that the fraction of papers that receive reviews is close to 1/n.
Given the previous negative result, you think about increasing the reward of each paper from 1 to B > 1.
(b) Show that for B = 2 this fraction is close to 1/3. [Hint: You can consider an instance with 3n +1 papers and
only
n will be reviewed.]
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY