Study Guide Corps

Game Theory

Strictly Determined Games Payoff Matrix is POV of row player $\left[\begin{array}{cc}3& -1\\ -1& -2\end{array}\right]$ So If the row player chooses the first row, they will wither get +3 or -1, and if they chose the bottom row, they will get -1 or -2

In a strictly determined game, the best strategy for each player is to chose the option with the best worst-case, or the maximin. For the row player, the minimums for the rows are -1, -2. So the Row player would chose to always play row one.

If a game has more than two options, first remove any rows/columns which are dominated. A row/column is dominated by another if every possible outcome in that row/column is less than the corresponding outcome in a particular alternative row/column.

How to know if a game is strictly determined?

A strictly determined game is one in which the maximin (the maximum of the row minimums) and the minimax (the minimum of the column maximums) are the same value. This value is called the saddle point of the game. The saddle point can be interpreted as the amount won per play by the row player

Games with mixed strategies $\left[\begin{array}{cc}4& -2\\ -3& 1\end{array}\right]$ Here the minimax (of the columns) is 1, and the maximin (of the rows) is -2. Since these are not equal, the game is not strictly determined.

To determine the row players optimal mixed strategy, do this: $\left[\begin{array}{cc}p& 1-p\end{array}\right]\left[\begin{array}{cc}4& -2\\ -3& 1\end{array}\right]=\left[\begin{array}{cc}4p-3(1-p)& -2p+1(1-p)\end{array}\right]$ Then set the resulting columns equal to one another: $4p-3(1-p)=-2p+1(1-p)$ And solve for p: $p=0.4$ $p$ represents what fraction of the time the row player should play the first row

For the column player, do: $\left[\begin{array}{cc}4& -2\\ -3& 1\end{array}\right]\left[\begin{array}{c}q\\ 1-q\end{array}\right]$

Graph Theory (Abridged)

Pigeon Hole Principle “A directed graph with n vertices and n edges, where each note has outdegree of 1 will always have between 1 and n cycles”

Size of a set is denoted by absolute value: $|M|$ is the size of the set of all men

Colleys Method Colley matrix times ranking matrix equals win/loss matrix

win/loss matrix is $1+\frac{w-l}{2}$

multiply both sides by inverse of colley matrix to find ranking matrix

Graphs for division/allocation

Top Trading Cycle

• Everyone picks selects the thing they want most
• Search for cycles, swapping item
• Once cycles have been eliminated, people with no preference on the board pick a “next best option”

Stable Matching

• Matching between two separate groups (represented by bipartite graph)
  • A pair includes one vertex from each set
• Stable if there are no rouges
  • There are no people who prefer each other to the person they are currently matched with

Gale-Shapley

• Matching between two separate groups (represented by bipartite graph)
• One side proposes, other side accepts or not, or temporarily accept
• As more proposals are made, accepters have the opportunity to reconfigure
• Can be different if sides are swapped
• Stable
  • The proposers get they first compatible choice - optimal

Transition Matrix Stuffs

For Transition $P$ and Initial condition $p$: $p_n=p_0\cdot P^n$ $\pi =\pi \cdot P$ & $\Sigma \pi =1$

Voting

1. Majority Criterion
   • If a candidate has a majority (>50%) of 1st-place votes, they must win.
     (Plurality and IRV pass; Borda sometimes fails!)
2. Condorcet Criterion
   • If someone beats every other candidate head-to-head, they should win.
     (Condorcet methods pass; plurality and IRV can fail.)
3. Monotonicity
   • Raising a candidate in rankings should not hurt their chances.
     (IRV can fail this!)
4. Independence of Irrelevant Alternatives (IIA)
   • If a loser drops out, the winner shouldn’t change.
     (Most systems fail this — even plurality and IRV.)
5. Pareto (Unanimity) Criterion
   • If everyone prefers A over B, then B shouldn’t win.
     (Almost all methods pass this.)

Banzhaf Power Index (β) Measures how often a voter is “critical” in turning a losing coalition into a winning one. Steps:

• List all winning coalitions.
• Count how many times each voter is critical (their removal flips it to losing).
• Normalize by total critical counts. Shows raw voting power, not just weight. Formula (for voter $i$): ${\beta }_i=\frac{\text{\# of times }i\text{ is critical}}{\text{total critical counts}}$

Shapley-Shubik Power Index (ϕ)

• Based on orderings (permutations) of voters joining a coalition.
• A voter is “pivotal” if their vote makes the coalition win for the first time.
• Steps:
  • List all voter orderings.
  • Count how often each voter is pivotal.
  • Normalize by total permutations (n!).
• Reflects sequential power in forming winning groups.
• Formula (for voter i): ${\varphi }_i=\frac{\text{\# of pivotal occurrences for }i}{n!}$

Methods

Plurality (First-Past-the-Post) Most votes wins, even if it’s not a majority.

Runoff (Two-Round System) If no majority, top 2 face off in a second round.

Instant-Runoff Voting (IRV) Voters rank; lowest gets eliminated in rounds until one has a majority. (Also called Ranked Choice Voting.)

Borda Count Points assigned based on rank (e.g., 1st = 3 pts, 2nd = 2 pts, etc.). Candidate with highest total wins.

Condorcet Method Winner beats every other candidate head-to-head.

Approval Voting Vote for as many candidates as you “approve.” Most approvals wins.

Aportionment

• Standard quota for each:
  • $q_i=\frac{\text{state pop}}{\text{total pop}}\times \text{total seats}$.
• Hamilton: assign $\lfloor q_i$ then extra seats by largest fractional parts.
• Webster: round $q_i$ to nearest integer.
• Huntington‑Hill: round using geometric mean thresholds
  $\sqrt{k(k+1)}$.