Assigment 14 is posted and is due Monday: assignment 14 (pdf)

We continued talking about voting methods, with an in-depth look at IRV (instant runoff voting) and the ranked pairs method. I’ll review with an example on Friday and then we’ll be moving on.

We also discussed why the plurality method does satisfy later-no-harm, but why in practice it fails in this general area very, very badly … as our example last Friday suggested.

Since we had looked at some things such as the binomial theorem, Pascal’s triangle, choice functions, and so on, I decided to briefly expand on that a bit as there was 5 minutes or so left at the end of class. I discussed this.

We continued to look at voting systems, with a botched attempt at explaining the Instant Runoff Method. (The example will work now. It’s relatively straightforward once figured out … no thanks to the Wikipedia article.)

See the chart of this page for a detailed matrix of which voting systems satisfy a multitude of criteria.

Why Plurality Satisfies Later-No-Harm

I found this a bit interesting. Namely, our analysis in class of the plurality method (and in fact, how we see it function in society) noted that it’s entirely possible to have three candidates in an election as follows.

  • Blue (40% of votes)
  • Red (30% of votes)
  • Green (30% of votes)

In such a situation, let’s say that the Red and Green parties are very similar but that both are very different from the Blue party. What happens if the Green party candidate is removed? Well, technically speaking, we’d have to have a new election if we were counting based on Plurality, since it isn’t a preference system. So, technically speaking, plurality can’t fail the later-no-harm criterion since the preference doesn’t change while tabulating the votes. Arguably, holding a new election with the Green party candidate removed DOES ESSENTIALLY THE SAME THING, but it’s technically a new election. That’s interesting, since we can see this at work, for instance, when smaller parties gain power in U.S. elections. Those smaller parties are often blamed for skimming off votes from one of the larger parties, leading to that larger party failing to gain enough votes overall.

Instant Runoff Voting Example

After some searching, I found this example on YouTube:

We’ll reconsider our example of votes in Tennessee on Wednesday. I’ll assign another homework then related to voting systems.

On Friday, we discussed voting systems. We’ll continue this on Monday. First, we discussed the voting system in the United States, hitting on some topics such as the electoral college system and drawing district lines. Then, we developed the following axioms for voting fairness. These are essentially the building blocks that any fair voting system must satisfy.

  1. (Majority Criterion) If one candidate is preferred by an absolute majority, then that candidate should win.
  2. (Mutual Majority Criterion) If an absolute majority prefer every member in one group over every member in another group, then a member of the preferred group should win.
  3. (Later-No-Harm Criterion) If every voter’s preference of $X$ or $Y$ remains unchanged, then the overall group’s preference of $X$ or $Y$ remains unchanged.
  4. (Condorcet Criterion) If a candidate would win a head-to-head battle against every other candidate, then that candidate should win.

There are other things we could add to this, such as a “dictator criterion,” i.e., that no person has any more power than any other person.

Voting Systems

We discussed a few voting systems. The details can be found on Wikipedia, and so for each of the ones we considered I am simply going to post a link. We’ll discuss these more on Monday.

The first system we discussed was plurality (first-past-the-post). Plurality fails to satisfy the mutual majority or Condorcet criteria.

The second system we discussed was the Borda count method. We considered an example where this method fails the later-no-harm criterion. Actually, interestingly, one can come up with examples to show that it fails all 4 of our fairness criteria.

We then considered the method known as instant runoff. This method has been shown to satisfy all of our criteria except the Condorcet criterion.

We’ve been talking about axiom systems and formal proofs in mathematics. On Wednesday, we covered some things from axiomatic Euclidean geometry. This is formal and a bit abstract. The idea is that we’ll talk about axioms of fair voting systems on Friday and show that certain voting systems fail to satisfy those axioms.

Undefined Terms

We have to start somewhere, and so we’re going to agree on what the following terms mean without defining them.

  • point
  • line
  • lies on (as in, a point lies on a line)
  • between (as in, a point is between two other points on a line)
  • circle
  • congruent

The last one there is a bit of a mathematical term. Congruence is a bit weaker than equality, just as equality is a bit weaker than identity. I explained this in class with some examples. Shoot me an email if you have questions or would like more examples.

Axioms

We’re going to be using the following axioms for Euclidean geometry.

  1. We may draw a (unique) line connecting any two points.
  2. We may extend lines indefinitely in either direction once they are created.
  3. Given a point and a length, we may create a circle centered at the point with radius equal to the length.
  4. All right angles are congruent.
  5. Given a line and a point not on the line, there is a unique line going through the point that is parallel to the given line.

Defining a Right Angle

We didn’t include “right angle” in the list of undefined terms. Should we? Well, if we can construct the definition using what we have so far, then no. Can we describe what a right angle is using only what we have? The answer is yes. But, it isn’t easy. We need to define some things along the way. First, we need to know what a “ray” is.

Definition: Given two points $A$ and $B$, the ray $AB\rightarrow$ is the line starting at $A$, containing $B$, and then continuing indefinitely past $B$.

Once we have the definition of a ray, we can then define an angle.

Definition: Given three points $A$, $B$, and $C$, the angle $\angle BAC$ is the ray $AB\rightarrow$ together with the ray $AC\rightarrow$. That is, both rays start at $A$, one containing $B$ and one containing $C$.

Definition: Two rays are called opposite if they start at the same point, lie on the same line, but point in opposite directions.

Definition: Two angles are called supplementary if two of the rays forming them are opposite.

In the diagram, angles 1 and 2 are supplementary, and the rays from $B$ to $A$ and $C$ are opposite. Now, we can define right angles.

Definition: An angle is a right angle if there exists a supplementary opposite angle to it.

Proofs

Sometimes, we can prove things directly from the axioms, and other times we can’t. When we can’t, we use formal logic to guide us through other strategies. One possible approach is what we’ll can RAA (reductio ad absurdum). The idea is that we want to show that a collection of known facts, axioms, definitions and so on can be used to prove a claim. So, what we do is assume that the claim is false … and then show that doing this results in running up against a logical brick wall. I explained this in detail in class, and you should feel free to ask me questions about it. It isn’t easy, so don’t think that I’m expecting you to get it immediately. The example we used in class was to prove that $\sqrt{2}$ is irrational. We assumed that is was in fact rational, and we ended up getting something that was nonsensical… meaning that one of our assumptions didn’t make sense.

Assignment 13 is posted and is due Wednesday, March 5. math2380-s2013-assign13 (pdf)

Mathematical Proof

Today, we started looking at Chapter 11 in the text. The main idea is that logical proofs can be broken down step by step, sometimes at a level so specific that many of the steps seem obvious (but aren’t).  I added the topic of Euclidean geometry, which we discussed in class (and isn’t in the book). The main axioms we have there are the following.

  1. Given two points, we may draw a line between those points.
  2. Given a line between two points, that line may be extended indefinitely in either direction.
  3. Given a point and a radius (some distance), we can create the circle having the point as the center and containing all points at the radius’ distance from the center.
  4. All right angles are congruent.
  5. Given a point and a line, there exists precisely one line through the point that is parallel to the given line.

I’ll be expending on these in class on Wednesday and Friday. I’ll provide some more detail on the website at that point.

Class Project

We discussed the class project briefly. You will work individually on a topic of your choice, either expanding on something that has been covered in class or following a topic of your own interest related to the spirit of the course. An additional stipulation is that no two students may work on projects that are too closely related. I prefer presentations (10-15 minutes) to the class, but am open to videos that you may produce, and other options. As a last resort, you can write a paper (4-5 pages, with correct citations, etc.). Remember that this is worth 25% of your grade, and you should therefore be trying to impress and interest me. Beyond that, you’re being given a pretty good amount of independence with this project, and my hope is that you take advantage of that and be creative. I’ll give you an example in class on Wednesday (tomorrow).

Assignment 12 is posted and is due on Friday, March 1. assignment 12 (pdf)

Read chapter 11 of the text, up through and including 11.7.

We reviewed today. I gave the solution to the problem in the homework that asked how many more pairs of people may interact in a city when the population doubles. I also reviewed equivalence relations and the binomial theorem.