Math 181: A Mathematical World
Comments on Homeworks and Quizzes

Return to Class Webpage
Tom Cooney's Webpage

Solutions to Quizzes

Solutions to Quiz 1: Page 1 and Page 2 .
Solutions to Quiz 2
Solutions to Quiz 3
Solutions to Quiz 4
Solutions to Quiz 5
Solutions to Quiz 6
Solutions to Quiz 7
Solutions to Quiz 8
Solutions to Quiz 9
Solutions to Quiz 10

Comments on Homework Assignment 11

We went through nearly all of these problems in class on Friday.
Adjusted winner procedure: Sometimes it will be necessary to transfer more than one item in order to make both people have the same number of points. Look at the point ratios (of the items belonging to the person with more points). We give (all or part of) the item with the lowest point ratio to the person with less points. If this person still has fewer points, we move on to the item with the next lowest point ratio and give (all or part of ) that item to the person with fewer points.
If there is an item that both people value equally, give it to the person with fewer points. If they now have different number of points, look at the point ratios to decide which items they should share ownership of.
When splitting an item between two people, keep track of who you gave x of that object to and who you gave 1-x of that object to. If you calculate person A's points by saying they got x amount of an object, then after you solve for x, you should give person A x of that object.
Let's look at Question 7, allocation 1 (and you can do the other allocations by yourselves).
Proportional (for three people) means that each person thinks he or she is receiving one-third or more of the total. It is proportional if every person thinks they are getting one-third or more of 100 = 33.333... points. In this allocation, Bob has 10 points and does not think he is getting his fair share of 33 or more points. So allocation 1 is not proportional. (If there were 4 people, proportional would mean each person believes they are receiving one-fourth or more of the total, and so on.)
Envy-free: What does envy mean? It means you look at what someone else has and want it for yourself; you think that they are getting a better share than you are; you prefer what they have to what you have. In Allocation 1, Bob has 10 points. Carol has received Y. In Bob's opinion, Y is worth 50 points. Bob feels envy; he thinks he has received 10 points and that Carol has received 50 points. He thinks Carol is getting more than he is. He prefers Carol's share to his share. Allocation 1 is not envy-free.
Equitable: This means everyone receives the same number of points. If everyone thought they were receiving 50 points worth of goods, that would be an equitable distribution. If everyone thought they were receiving 20 points, that would be an equitable distribution. In allocation 1, Bob thinks he is getting 10 points and Carol thinks she is getting 40 points and Ted thinks he is getting 30 points. This is not equitable - they are not all walking away with the same number of points.
Pareto Optimal: Here's an example of a Pareto-optimal allocation. You split up $20 as follows, $10 to A, $10 to B. You can improve this (from A's point of view) by giving $15 to A and $5 to B, but B will not be happy about this. There is no way of improving upon this 10-10 split that will make one person happier without making someone else unhappy. Any way of changing things to help one person will harm the other.
Here's an example of an allocation that is not Pareto-optimal: allocation 1.
Bob gets Z for 10 points.
Carol gets Y for 40 points.
Ted gets X for 30 points.
Question asks you to change this allocation in a way that makes someone happier without hurting anyone else.
How about this?
Bob gets X for 40 points. 40>10 so Bob is happier.
Carol gets Y for 40 points. Still has 40 points, so Carol is as happy as before and has not been hurt by this change.
Ted gets Z for 40 points. 40>30 so Ted is happier.
This allocation is an improvement upon allocation 1: the changes made some people happier and the changes did not make anyone unhappy.
It would not work to give Y to Bob and Z to Carol. Yes, Bob would be happier but Carol would be unhappy as she went down from 40 points to 30 points.

Comments on Homework Assignment 10 and Quiz 9

Solutions to Homework Assignment 10
While this was largely answered well, there are a couple of minor details to watch for.
For example, C⁹₃ (9 choose 3 - apologies for my limited html skills), should have 3 numbers on top, counting down from 9, and 3 numbers in the denominator, counting down from 3. It should be
9 × 8 × 7
------------
3 × 2 × 1
This is much easier than working with 13! (=6227020800) and 9!=362880.
When counting permutations using factorials, it will often be quicker and easier to calculate the Shapley-Shubik Power index if you do NOT multiply out. For example, in this homework assignment you had the choice between calculating
240
----
720
equals one-third, or
2 × 5 × 4 × 3 × 2 × 1
----------------------------
6 × 5 × 4 × 3 × 2 × 1
equals one-third (where the cancellations are obvious.
When finding winning coalitions, work through the possibilities in some logical order. For example, all the possibilities with one voter, then two voters, then three voters,...
For four voters A, B, C, D, the possibilities are: A, B, C, D, AB, AC, AD, BC, BD, CD, ABC, ABD, ACD, BCD, ABCD.
There is certainly no point to memorizing that list, but it could help a lot to ask yourself: one voter, two voters starting with A, two voters starting with B,....

The quickest way to find the critical voters is as follows:
1. Look at the winning coalition. Example: ABCD
2. How many votes does it have? 15
3. How many extra votes does it have? 15-11=4.
If voter D changes his/her mind, we would be left with ABC, which is still a winning coalition. Because we have 4 extra votes, if any voter with 4 or less votes changes his/her mind, we would still have a winning coalition. If voter A changes his/her mind, we would be left with ACD, which is not a winning coalition -- we only had 4 extra votes, so if we lose 8 votes, it will no longer be critical. For this reason,
4. A voter (contained in a coalition) is critical if (and only if) it has strictly more votes than the number of extra votes for that coalition.
A has 8 votes (and 8 is strictly bigger than 4) and is critical. B,C,D each have 4 or less votes and are not critical for this winning coalition.
We proceed similarly for blocking coalitions. There are SOME differences.
How many votes do you need to be a blocking coalition?
How many extra votes does the blocking coalition ABCD have?
(The answers are NOT 11 and 4.)
Which voters are critical in the blocking coalition ABCD?
(Different answer to when we consider the winning coalition ABCD.)
It is NOT true that the number of winning coalitions containing A is the same as the number of blocking coalitions containing A. Instead, I am saying that the number of winning coalitions for which A is critical is equal to the number of blocking coalitions for which A is critical. There are 5 winning coalitions containing A and 5 winning coalitions for which A is critical. There are 8 blocking coalitions containing A (diferent from before, but this IS NOT what we are counting) and 5 blocking coalitions for which A is critical (same as before and this IS what we are counting).

Comments on Homework Assignment 9

Click here for solutions and comments

Comments on Quiz 8

This was very well answered. Good work, class.
While I did not deduct points for these today:

When listing winning coalitions or permutations, use the names of the voters (e.g., A,B,C) instead of their weights (e.g., 5,4,1). Otherwise things will get very confusing when you have two voters with the same number of votes. Is that 3 meant to be voter C or voter D?

It probably makes it easier to identify the pivotal voter in a permutation if you keep track of the cumulative weight totals rather than just the weights and should help prevent mistakes.

For example,
[8:5,4,1]
Permutation
A B C
(cumulative total / running total of) weights
5 5+4 5+4+1
5 9 10.

Comments on Homework Assignment 8

Except for a few difficulties with question 4, this was answered quite well.
See the remarks in "Comments on Quiz 7" about what it means to successfully manipulate an election. For example, in question 9, the voter on the far right has first preference B. B wins this election and this is the best possible outcome for this voter. This voter will never change their vote with the intention of making A the winner: this voter prefers B to A. The only voter unhappy with the result of this election (and thus the only voter willing to change his or her vote) is the voter on the left.
The book could phrase Question 4(c) more clearly than it does - perhaps this contributed to it being answered poorly.
What does May's theorem say about two-candidate elections? If the voting system used is

anonymous (treats all voters equally)

neutral (treats all candidates equally)

and nonmanipulable,

then it's majority rule. This is the "best" voting system for two candidate elections. All other voting systems have a flaw.
So if we have a second voting system different from majority rule, it must have a flaw. We are told that this second voting system is:

anonymous

and nonmanipulable.

So our second voting system must have the flaw of not being neutral.
What voting systems do we know for two-candidate elections that are anonymous, nonmanipulable (=monotone), but not neutral? Imposed rule.
Imposed rule is nonmanipulable: the winner has been decided in advance and your vote does not matter. No matter how you vote, sincerely or insincerely, the winner will be the same. You cannot manipulate the imposed rule voting system.
For these reasons, the answers to 4(b) and 4(c) are majority rule and imposed rule.
Borda count, Condorcet method, Hare method do not count as a valid answer to 4(c). If we only have two candidates, then Borda count and Condorcet method and Hare method all work the same way as majority rule - we end up counting to see who has the most first place votes. They always agree on who the winner is, if there are only two candidates. Yes, these are all very different when we have more than 3 candidates. However, read question 4 again: it asks for two voting systems that are genuinely different for two candidates and will sometimes disagree on who the winner is for two candidates.

Comments on Quiz 7

This was very well answered in general.
A few of you should take another look at how the Hare system works. (We decide who is in last place by looking at how many first place votes each candidate has. We do not consider anything else. All candidates tied for last are eliminated. See comments below on Homework 7 and Quiz 6.)

Keep in mind what it means to successfully manipulate an election. Suppose your preferences are:
A
B
C
D
E
An election is held and C wins. You want a better outcome (according to your preferences) and not a worse one. You will do whatever you can to help candidates A and B. You will not do anything to help D and E; from your point of view, a victory for D is worse than a victory for C. To successfully manipulate the election, you need to change your vote so that one of A or B wins. You will not always be able to make A (your most preferred candidate) the winner but you still prefer a victory for B to a victory for C. If you change your vote and C or D wins, then that is not a successful manipulation. (You are also not satisfied with a tie - you require outright victory.)
Here are things to bear in mind:

Always find the winner of the first election.

Find a voter who is unhappy with this outcome.

Can this voter change their vote (and vote insincerely in Election 2) so that he or she prefers the result of Election 2?

Find the winner of the second election.

Comments on Homework Assignment 7 and Quiz 6

Remember: Count voters, not columns. The number 5 on top of the column means that 5 voters voted this way.

Mainly Pareto Condition

What does the Pareto condition say?
If everyone prefers A to B, then B should not be a winner. This seems fair to me. It does not say that A is the winner. It does not say that A is everyone's first preference. It does not say that B is everyone's lowest preference.
Example of everyone preferring A to B:
7 3 2
C A A
A C B
B B C
Everyone prefers A to B. Some people prefer C to A; some prefer B to C. A is not universally adored and B is not universally hated. In this example (with most voting systems we have met), C is the winner and not A. The Pareto condition does not say that A is the winner. It says it seems "unfair" for B to be the winner; it says B should lose.
Some students' answers used the phrases "most preferred" and "least preferred" to refer to candidates. But what does this mean? The whole goal of voting theory is to find a good way of deciding who is "most preferred" or "least preferred". The last month has been spent looking at situations where it is not obvious who is "most preferred" but we still have to reach a decision. We are (probably) not looking at the situation
1 1 1
A A A
C D C
D C D
B B B
Here it is clear that A is "most preferred" and B is "least preferred". But this is rare, so we should usually avoid these phrases. The second example does indeed show everyone preferring A to B but, as the first example shows, the Pareto condition refers to situations much more general than the last example.
Pareto condition refers to individual preferences. Each individual prefers A to B. Group preferences (and statements like the voters prefer A to B) are trickier. This whole chapter is studying the difficulties of saying what a group prefers.

Good Questions (and if you know the answer, let me know that you know the answer - that's how you get points)

I have previously stated in class that I think 1, 2, 3, 16, 17, 18, 19, 20, 21 from Chapter 9 are good questions. They ask you to understand how the voting system works, what some idea of "fairness" (monotonicity, Pareto, . . .) means, and then to explain why the voting system has (or does not have) some property. If you need examples of how to solve these questions, come talk to me in office hours, make an appointment, or look at the textbook for solutions to 1, 3, 17, 19, 21.
These have not been answered well in the quizzes or in the homeworks. I believe many of you know the answer but then do not explain it on the page. I can only give you points for what you write on the page. Be specific.

Question 28

Similar comments to the one immediately above this.
Be specific. Zero points for merely repeating the statement of the question.
Why does sequential pairwise voting not lead to a tie when there are an odd number of voters?
Sequential pairwise voting consists of a series of head-to-head contests. If there are an odd number of votes to split between exactly two candidates, then there cannot be a tie. (For example, how could you split 7 votes between 2 candidates and get a tie?) We go through the agenda, with no ties at each stage, until we are left with one winner at the very end.
(Be specific: it is because sequential pairwise voting only looks at pairs of candidates that this is true. Don't just repeat the question without providing further explanation.)
Why does the Hare system never lead to a tie between exactly two candidates if there are an odd number of voters?
Ask yourself: how could a tie occur between exactly two candidates? The only way for two candidates to tie using the Hare system is:
All other candidates have been eliminated. The two candidates remaining have the same number of votes.
But if there is an odd number of votes, then these two candidates cannot split them evenly.
(Also, in response to some of your answers: it is possible for there to be ties earlier on in the election process:
5 2 1 1
A B C D
B A D C
C D A B
D C B A
In round 1, C and D tie and are eliminated. We then get
5 2 1 1
A B A B
B A B A
And now a tie is impossible. It is only when we are down to 2 voters that a tie is impossible.
It is also possible for there to be ties with three candidates and an odd number of voters:
1 1 1
A B C
B A B
C C A
It is possible to split three votes equally between three candidates. Problem 28b is true because it is impossible to split three votes equally between two candidates.)

Hare System versus Plurality Runofff

What is the difference between the Hare system and the Plurality runoff method?
Hare system:

Count first place votes and eliminate whoever is in last place (including ties).

Write out new tables of ballots after eliminating candidates - this will help prevent mistakes.

Repeat this process for as many rounds as necessary, until there is an overall winner and all other candidates have been eliminated.

If all remaining candidates are tied for last (or, viewed another way, tied for first) and would all be eliminated in the next round, then they all tie for the win.

Plurality Runoff:

Count first place votes. Those candidates in first and second place (including ties if necessary) go through to the runoff election. Everyone else is eliminated.

Write out a new table of ballots after eliminating candidates - this will help prevent mistakes.

Use plurality (most first place votes wins) to decide who wins the runoff election. This is our overall winner.

There is only one runoff election. The overall winner is decided after the runoff election. Unlike the Hare system, we do not have multiple rounds of eliminating candidates, we jump straight to declaring an overall winner.

Comments on Homework Assignment 6

The ideal answers to Questions 2 and 3 use the definitions of the properties. The reason we introduced these definitions is so that we can say what we mean by a "fair" voting system or treating voters "equally". Unless we use the definitions, we are reduced to speaking only of "feels nice" and "does not feel nice".
No matter how you answer Questions 2 and 3, you should explain why this voting system has that property. What is it about this particular voting system that forces it to have this particular property?
Need some examples? Read the solutions to Questions 1 and 3 near the back of your textbook.
In class I said that monotone could be thought of informally as "things which should help, do help". This is too sloppy. It is better to think of it as "things which should help, never hurt".
What's the difference between imposed rule and a dictatorship?

In imposed rule, everyone gets to vote but none of those votes has an effect on the outcome of the election. No one has an important vote. The winner of the election is imposed from outside and cannot be changed.

In a dictatorship, everyone gets to vote but only one of those votes has an effect on the outcome of the election -- everyone else's vote is ignored. One person, the dictator, has an important vote and chooses the winner of the election. If the dictator changes his mind about how to vote, then the winner of the election changes.

Comments on Quiz 5

This was (in general) answered very well. However, even if you got full marks, here are some potential confusions to avoid:
A question like Problem 1 on the exam has three parts:

What is imposed rule? At the least, you should mention whatever feature of imposed rule is relevant to the problem.

What is an anonymous voting system? At the least, you should mention those features relevant to the problem.

Why is imposed rule an anonymous voting system? On an exam, where this question would be worth more than three points, I would definitely deduct points for ignoring this third point completely.

The same comments obviously apply to Problem 2.
What does it mean to be a Condorcet winner?

B is the Condorcet winner because B wins all of its own head-to-head contests - it beats all the other candidates.

It is not enough to win the most head-to-head contests.

Yes, B does not win "A versus C" - that doesn't matter. B only has to win all of its own contests - it has no possibility of winning "A versus C".

Condorcet's Voting Paradox is an example of the fact that there does not always have to be a Condorcet winner. For some elections there is a Condorcet winner and for other elections, there is not one. It does not mean there is never a Condorcet winner.

Three columns is not the same as 3 voters. In the following:
9 7 1
A B B
B C A
C A C
There is a total of 17 voters, not 3. If we now look at the head-to-head contest "A versus B", we get
9 7 1
A B B
B A A
and A would win by 9 votes to 8. B is listed at the top of more columns but that does not mean that B has received more votes.
Finally, plurality means the single largest number of votes (even if this is less than half). Majority means more than half the votes. So, in question 3, it is correct to say that A won a plurality of the votes but it is not correct to say that A won a majority of the votes. (This is why the voting systems of "majority rule" and "plurality rule" have different names, even though they both rely on the same basic idea.)

Comments on Homework Assignment 5

This assignment was answered quite well. The most common difficulty was losing track of what items had already been packed in the bin-packing problems. Try underlining or crossing items off the list as you use them.
Suppose you have coloured a graph using 6 colours. This does NOT mean that the chromatic number of the graph is 6. It might be 6 or it might be less than 6. If some different way of colouring the graph used 5 colours and there was no possible way of colouring the graph with fewer colours, then the chromatic number would be 5. The chromatic number of a graph is not the number of colours some particular colouring uses; it is the smallest number of colours that could ever be used to colour that graph.
Also, I sometimes assign odd-numbered exercises from the textbook. They may be good practice using an idea or a good illustration of some concept. They also have the advantage that you can LATER check your answer in the back of the book, to see whether you are grasping things correctly. You learn NOTHING if you only copy the answer from the back of the textbook. Try the problem and then later look at the answer. Make sure you understand where that answer came from. If you have questions about a problem or a concept, come talk to me in office hours, make an appointment, or just email me.

Comments on Homework 4 and Quiz 4

Department of Mathematics
College of Liberal Arts and Sciences
University of Illinois at Urbana-Champaign
273 Altgeld Hall, MC-382
1409 W. Green Street, Urbana, IL 61801 USA
Department Main Office Telephone: (217) 333-3350 Fax (217) 333-9576

Math 181: A Mathematical World Comments on Homeworks and Quizzes