CPS 296.2 - Computational Game Theory and Mechanism DesignHomework 2 (due 10/12)Note the rules for assignments on the course web page. Show all your work,but circle your final answer. Contact Vince ([email protected]) with anyquestions.1. (Properties of voting rules.)Alice likes to analyze the outcomes of elections; specifically, she is interestedin the different outcomes that different voting rules produce on the same votes.To do so, she executes many different rules on the same set of votes, a painstak-ing process. She likes knowing about properties of voting rules that ease hertask. For example, she likes to know which voting rules satisfy the Condorcetcriterion, so that if there is a Condorcet winner, she immediately knows thatthat will be the winner for those rules, without having to go through the troubleof executing each rule individually.Recently, Alice has become interested in the phenomenon of votes “cancellingout.” Let us say that a set1S of votes cancels out with respect to voting ruler if for every set T of votes, the winner2that r produces for T is the sameas the winner that r produces for S ∪ T . For example, the set of votes {a Âb  c, b  a  c, c  a  b} cancels out with respect to the plurality rule:each candidate is ranked first once in this set of votes, so it has no net effect onthe outcome of the election. The same set does not cancel out with respect toBorda, though, because from these votes, a gets 4 points, b gets 3, and c gets 2,which may affect the outcome of the election. Alice likes to know when a set ofvotes cancels out with respect to a rule, so that she can just ignore these votes,easing her computation of the winner.Define a pair of opposite votes to be a pair of votes with completely oppositerankings of the candidates, i.e. the votes can be written as c1 c2 . . .  cmand cm cm−1 . . .  c1. Let us say that a voting rule r satisfies theOpposites Cancel Out (OCO) criterion if every pair of opposite votes cancelsout with respect to r.1a. (12 points) From among the (reasonable3) voting rules discussed inclass, give 3 voting rules that satisfy the OCO criterion, and 3 that do not (andsay which ones are which!).1Technically, a multiset, since the same vote may occur multiple times.2... or set of winners if there are ties.3E.g. not dictatorial rules, rules that always choose the same winner, or randomized rules.Also, approval cannot be one of the rules because it is not based on rankings. If you use Cup,Cup only satisfies a criterion if it satisfies it for every way of pairing the candidates.1Define a cycle of votes to be a set of votes that can be written as c1 c2Â. . .  cm, c2 c3 . . . cm c1, c3 c4 . . .  cm c1 c2, . . . , cm c1Âc2 . . .  cm−1. Let us say that a voting rule r satisfies the Cycles Cancel Out(CCO) criterion if every cycle cancels out with respect to r.1b. (12 points) From among the (reasonable) voting rules discussed inclass, give 3 voting rules that satisfy the CCO criterion, and 3 that do not.Define a pair of opposite cycles of votes to be a cycle, plus all the oppositevotes of votes in that cycle (note that these opposite votes themselves constitutea cycle). Let us say that a voting rule r satisfies the Opposite Cycles CancelOut (OCCO) criterion if every pair of opposite cycles cancels out with respectto r.1c. (12 points) From among the (reasonable) voting rules discussed inclass, give 5 voting rules that satisfy the OCCO criterion, and 1 that does not.1d. (14 points) Criterion C1is stronger than criterion C2if every rule thatsatisfies C1also satisfies C2. Two criteria are incomparable if neither is strongerthan the other. For every pair of criteria among OCO, CCO, and OCCO, saywhich one is stronger (or that they are incomparable).2. (A multi-unit auction with externalities.)We are running a multi-unit auction for badminton rackets in the townExterna, where nobody owns one yet and we are the only supplier. Of course,being the only person to own a badminton racket is no fun; bidders care aboutwhich other bidders win rackets as well. In such a setting, where bidders careabout what other bidders win, we say that there are externalities. Let us assumethat each agent is awarded at most one racket, and that shuttlecocks and netsare freely available. In the most general bidding language for this setting, eachbidder would specify, for every subset of the agents, what her value would beif exactly the agents in that subset won rackets. This is impractical becausethere are exponentially many subsets. Instead, we will consider more restrictedbidding languages.Let us suppose that it is commonly known which agents live close enough toeach other that they could play badminton together. This can be representedas a graph, which has an edge between two agents if and only if they live closeenough to each other to play together.AliceBobCarol DanielEvaFrankFigure 1: Externa’s proximity graph.In the first bidding language, every agent i submits a single value vi. Thesemantics of this are as follows. If the agent does not win a racket, her utility2is 0 regardless of who else wins a racket. If she does win a racket, her value isv times the number of her neighbors that also win a racket.Suppose we receive the following bids:AliceBobCarol DanielEvaFrank443553Figure 2: Graph with bids. The number next to an agent is that agent’s bid.Suppose we have three rackets for sale. One valid (but not optimal) allo-cation would be to give rackets to Carol, Daniel, and Eva. Carol would get a(reported) utility of 3, Daniel would get 6 (2·3, because two of Daniel’s neighborshave rackets), and Eva 5, for a total of 14.2a. (12 points) Give the optimal allocation, as well as the VCG (Clarke)payment for each agent.2b. (13 points) In general (general graphs and bids), is the problem offinding the optimal allocation solvable in polynomial time, or NP-hard? (Hint:think about the Clique problem.)One year has passed, and we have returned to Externa. Everyone’s racketshave broken (we are not in the business of selling high-quality rackets here)and they need new ones. However, the people in the town were not entirelyhappy with our previous system. Specifically, it turned out that each agentonly ever played with (at most) a single other agent, so that multiplying thevalue by the number of neighbors with rackets really made no sense. Also,agents have realized that they would receive different utilities for playing