Problem Set: Voting and Sharing Problem 1. Voting methods You are ...

  1. Home
  2. Homework Library
  3. Mathematics
  4. Set Theory
  5. Problem Set: Voting and Sharing Problem 1. Voting methods You are ...


Transcribed TextTranscribed Text

Problem Set: Voting and Sharing Problem 1. Voting methods You are on a committee deciding who should headline the next Superbowl Halftime Show. 15 11 10 8 5 3 Drake 1 5 5 5 1 1 Future 4 1 2 4 5 4 Kendrick 3 2 3 332 CardiB 5 4 1 2 2 5 21Savage 2 3 4 1 4 3 Work out the winner according to each of the five different voting schemes (described in the web- pages for the voting lab). Attach pages showing how you got each of the answers below. Answer: Winner for: • plurality: • plurality with run-off: • sequential run-off (Hare): • Borda-count: • Condorcet-winner: 1 Problem 2. Arrow’s impossibility theorem The independence of irrelevant alternatives (IIA) property of a voting rule is that: If every voter’s preference between X and Y remains unchanged, then the group’s preference between X and Y will also remain unchanged (even if voters’ preferences between other pairs like X andZ,Y andZ,orZ andW change). Suppose two voters are using a Borda count to rank: Alligator, Baboon, Capybara and Dingo. A>1 B>1 C>1 D B>2 C>2 A>2 D What ranking does a Borda Count give between A and B? Give a modification of these rankings that does not change either voters preference between A and B, but changes the decision about A versus B. This demonstrates how IIA can fail for Borda counts. 2 Problem 3. Continuous voting You are voting with two other friends on where to setup a boombox at a park, P, shaped like this: You each pick a point x1, x2 and x3 in P and want an outcome that is unanimous, anonymous and continuous as in the notes. Is this possible? Explain why. Explain why taking the center of the triangle formed by your three choices would have votes that result in problematic choices. Give an example of such votes on the figure below. 3 One of your friends proposes the following fix: 1. Make a map of P out of playdough 2. Mark your vote on P with a sharpee 3. Stretch P into a rectangle. 4. Take the center of the triangle formed by where your marks reside on this box. 5. Reshape the box back into a park shape 6. Use the location of the resulting point Explain why this procedure would be unanimous, anonymous and continuous. 4 Problem 4. Agreeable societies. Do FOUR things: (a) Draw the agreement graph. (b) Find all values of k and m so that the society is (k, m) agreeable. (c) Write the pair from (b) that maximizes (k − 1)/(m − 1). (d) By looking at the preferences find a candidate that satisfies the most people. How many people does it satisfy? Part B 5 Problem 5. Agreeable societies Part A. Ninth street has 14 restaurants in a row ABCDEFGHIJKLM and every resident only dines at the 5 restaurants closest to them. Suppose that there are 1000 people living on the ninth street. Explain why there must be a restaurant dined at by at least 500 people. Hint: If each person chooses 5 restaurants in a row among 14 choices, what must happen with every 3 people’s preferences? 6 Part B. Some notation. Suppose that we have a (2,3)-agreeable society with a finite number of voters. The ith voter has an acceptability set Ai = [Li, Ri] with Li the leftmost and Ri the rightmost acceptable point for them. Set L = maxLi and R = minRi. ii So L is the rightmost left point of all of the voters and R is leftmost right point of all the voters. Explain why if L ≤ R why there is a choice that satisfies everyone. Now suppose L > R. This means that there is a voter, lets call them voter 1, who has L as their leftmost point, and another voter, let’s call them voter 2 who has R as their rightmost point. Here’s a diagram of the situation with five voters. voter 1 voter 2 RL (i) Explain why voter 1 and voter 2 do not agree. 7 (ii) Explain why a different voter, say voter j with j ̸= 1 or 2, must agree with either voter 1 or voter 2. (iii) Suppose that Aj does not contain L. Then who must Aj agree with? (iv) Using your answer to (iii) and how R is defined to explain why R ≤ Rj . (v) Use (iii) and (iv) to explain why R must be agreeable to voter j. (vi) The same reasoning would show that if Aj does not contain R then L must be acceptable to voter j. So, every voter must be okay with one of either R or L. Explain why this ensures that there is a candidate acceptable to at least half of the voters. Hint: Suppose you put 101 rocks into two buckets. What would have to be true about the final number of rocks in one of the buckets? 8 Problem 6. Power index. [ q : w1,w2,w3,...] = (p1, p2, p3,...) ↑ ↖↑↗ ↖↑↗ quorum weights of power indices needed to pass the voters of the voters a measure Suppose that we have the following quorem and wights:[51 : 40, 30, 20, 10]. Here are all 16 possible coalitions. Circle votes that are swing votes. circle votes that are swing votes A B C D Votes Pass/Fail 40 30 20 10 + + + + 100 P ⃝+ + + − 90 P Find the power indices [51 : 40, 30, 20, 10] = 􏰁 , , , 􏰂 ⃝+ ⃝+ − + +−++ −+++ ++−− +−+− +−−+ −++− −+−+ −−++ +−−− −+−− −−+− −−−+ −−−− 80 P 9 Problem 7. Sharing nachos Suppose a dinner consists of 8 morsels and is to be shared, taking turns, between Alice and Bob: D = {(1, 8), (2, 3), (3, 6), (4, 4), (5, 1), (6, 2), (7, 5), (8, 7)}. Alice goes first. Recall the following strategies from class: 1. Greedy: At each step Alice or Bob eats the morsel that would give them the most satisfaction. 2. Spiteful: At each step Alice or Bob eats the morsel that would give their opponent the most satisfaction. 3. Competitive: At each step Alice or Bob eats the morsel that is most valuable to the both of them (the morsel m = (a, b) that maximizes a + b. (If there are several that maximize this then the one more preferred by the player choosing is eaten.) 4. Crossout: The least preferred morsel by your opponent is eaten last. So Bob will eat Alice’s least preferred morsel, they will toss that out, then Alice will eat Bob’s least preferred morsel of those remaining, and so on until all have been eaten. How much satisfaction does each obtain if they employ the greedy strategy? D = {(1, 8), (2, 3), (3, 6), (4, 4), (5, 1), (6, 2), (7, 5), (8, 7)}. How much satisfaction if they both use the spiteful spiteful strategy? 10 D = {(1, 8), (2, 3), (3, 6), (4, 4), (5, 1), (6, 2), (7, 5), (8, 7)}. How much satisfaction if they both use the competitive strategy? D = {(1, 8), (2, 3), (3, 6), (4, 4), (5, 1), (6, 2), (7, 5), (8, 7)}. How much satisfaction if they both use the crossout strategy? D = {(1, 8), (2, 3), (3, 6), (4, 4), (5, 1), (6, 2), (7, 5), (8, 7)}. Now, have Alice and Bob play the crossout strategy except Bob will make a mistake and not follow the strategy for the second to last morsel he eats (remember the first bit is chosen last). Compare Alice and Bob’s satisfaction to when Bob followed the strategy perfectly. 11

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

    By purchasing this solution you'll be able to access the following files:

    for this solution

    or FREE if you
    register a new account!

    PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

    Find A Tutor

    View available Set Theory Tutors

    Get College Homework Help.

    Are you sure you don't want to upload any files?

    Fast tutor response requires as much info as possible.

    Upload a file
    Continue without uploading

    We couldn't find that subject.
    Please select the best match from the list below.

    We'll send you an email right away. If it's not in your inbox, check your spam folder.

    • 1
    • 2
    • 3
    Live Chats