Computational game theory (Nash equilibriums) PROBLEM :

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 Si C{1,2,...,n}, as long as the total cost to write all reviews is less than T (the time before the deadline): 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 wi, which is the reward Ri over all papers they receive minus the effort they put into writting reviews: Ui = Ri - Sij. jes, You can assume that for the given sij's, there is a combination of strategies S, where every reviewer has positive uti 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 sij's such that the fraction of papers that receive reviews is close to 1. 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.]