MS&E 336/CS 366

Lecture 3,4 outline, 1/16/2024

​

Not notes — a cheat sheet for list of topics

Informal definitions; formalism in handbook

Missing most of the color and examples

Plan

Proof sketch of the Gibbard-Satterthwaite theorem

Another notion of bargaining: Kalai Smorodinsky

Some more social choice rules and classifications of these rules

Approval Voting

​

Gibbard–Satterthwaite theorem

We will develop the proof carefully. Will not repeat this for all proofs, but it is important to see one proof completely to develop insight and intuition.

Equivalent statement: Suppose there are at least three alternatives and that for each individual any strict ranking of these alternatives is permissible. Then the only unanimous, strategy-proof social choice function is a dictatorship.

Fact 1: Monotonicity as a consequence of strategy-proofness:��Suppose that alternative A is selected given some preference profile. Modify the profile by raising some alternative X in individual i’s ranking (holding everything else fixed). Then either A or X is now selected.

Proof step: Fact 1

Suppose some third candidate C is now selected

If voter i prefers C to A, then it would falsely report this move by B

If voter i prefers A to C, then it would falsely not report this move by B

Step 1: Define pivotal voter

Consider an arbitrary strict profile in which everyone ranks B last. Arrange voters from left to right (no anonymity)

— B is not the winner (strategy-proofness)

— Raise B to the top of the ranking of voter 1, then voter 2, … till when you raise it to the top of voter r, B becomes the winner (no neutrality)

— Call r the pivotal voter for B (we will call it r(B) when needed)

— B is chosen whenever the first r players rank B first. (*B)

— B is not selected whenever voters r through n rank alternative B last. (**NOT B)�

Proof step: illustrating Pivotal Voter

Proof step: (*B)

(*B): B is selected as the winner whenever the first r winners declare it as winner

Proof: Consider profile 2.

— If a different alternative is the winner when any voter i > r submits a different ranking, that voter i would misrepresent since voter i likes B the least.

—If a different alternative is the winner when any voter i <= r submits a different ranking (while keeping B on top), then i would not submit that ranking even if that were its true ranking.

​

Steps 2 and 3

Step 2: r(B) is a dictator in the special case when everyone ranks B last.

Step 3(a): If r(B) chooses K then either K or B wins

Step 3(b): The pivotal voter r(X) is the same for all X

This finishes the proof

The Gibbard–Satterthwaite theorem: a simple proof�Jean-Pierre Benoˆıt. Economics Letters 69 (2000) 319–322

​

Proof of Step 2: r(B) is a dictator when B is last in all rankings

Start with the following profile (profile 3), and we will show that K must win.

Step 2 contd:

Step 2 contd:

Suppose G (different from K) wins in profile 3. Start with profile 3 and promote B in first r-1 rankings. G must still win. (From Fact 1 and **NOT B)

​

Now move B to the second position for voter r to obtain Profile 6. By Fact 1, either B or G wins. If it is still G, then strategy-proofness will be violated for voter r (combined with *B). Hence B wins.

​

Now raise K to the second position for voters 1 through r - 1, and the first position for voters r + 1 through n.

​

By strategy-proofness, B must still win. But this is the same as profile 5 where K wins, and hence, by contradiction, G must be K.

​

Steps 2 and 3

Step 2: r(B) is a dictator in the special case when everyone ranks B last. (DONE)

Step 3(a): If r(B) chooses K then either K or B wins

Step 3(b): The pivotal voter r(X) is the same for all X

This finishes the proof

Proof of step 3(a)

3(a): If r(B) chooses K then either K or B wins

Proof:

— If r(B) chooses K and B is last in every ranking then K wins (step 2)

— If we now raise B to an arbitrary position in every ranking, then either K or B wins (Fact 1: monotonicity)

Proof of step 3(b)

Consider three candidates B, C, and A. Voter r is pivotal for B and voter s is pivotal for C

If everyone ranks C last, and the first r voters rank B first, and the last N - r voters rank A first, then:

— By (*B), B should win.

— By step (2), whoever is chosen by the s-th voter should win.

Hence, s <= r

By symmetry, r <= s. Hence the pivotal voter is the same for all candidates.

​

​

Kalai–Smorodinsky Bargaining

Nash’s Axioms: Invariant to affine transformations; Pareto optimality; Independence of irrelevant alternatives; Symmetry.

Kalai–Smorodinsky: Replace “Independence of irrelevant alternatives” with “Monotonicity”

Informal definition: If, for every utility level that player 1 may demand, the maximum feasible utility level that player 2 can simultaneously reach is increased, then the utility level assigned to player 2 according to the solution should also be increased

Solution: Assuming that the outside alternative is (0,0), both players get the same fraction of their maximum utility.

HW Problem (roughly): Design a two person game such that KS is the outcome.

More rules

Tournament rules: Based only on the directed graph on candidates with an edge from a to b if a beats b in pairwise election (a tournament). Also called Type 1 rules.

Weighted tournament rules: Based only on information in the weighted tournament (each edge in the tournament is labeled by how often a beats b). Type 2.

Additional information: Type 3.

Single Transferable Vote/Instant Runoff: repeatedly kick out the person with the least first place votes

Ranked Pairs: add edges in decreasing order of weight, throw away edges that cause a cycle

Food for thought: should we have STV for the primary?

Food for thought: classify rules as 1, 2, 3.

Approval Voting

Each voter provides a set of “approved” candidates, with no ranking

The candidate with the most number of approvals wins (ties broken arbitrarily)

Is this a good rule? Depends on the assumptions:

— Assumption 1: Voters truly have dichotomous preferences: very good properties

— Assumption 2: Voters have arbitrary rankings as preferences, but are forced to collapse them into two categories: not a very good rule

Approval voting under dichotomous preferences

Equivalent to a scoring rule that assigns 1’s and 0’s to the two preference classes

Equivalent to finding the Condorcet winner

Unites Borda and Condorcet!

Strategyproof

— Assuming no voter approves of every candidate or 0 candidates

A great template for this class — prove strong properties under assumptions on voter utilities

Participatory Budgeting

Make a budget collaboratively or via voting of some sort.

— N voters, M expense items/projects.

— Assume only expense items are on the ballot.

— Total budget available is B. Cost of item j is c_j. Assume that all costs and B are positive integers.

— Assume items can be chosen fractionally (NP hard otherwise even for one voter)

— Feasible solution: x = <x₁, x₂, … x_M> such that x ≥ 0, x ≤ c, and ∑_{Projects j} x_j ≤ B.

Good models of User utility/cost?

Linear utility: Voter i has utility u_i,j for project j, and U_i(x) = ∑_{Projects j} u_i,j x_j

Overlap utility: User i has ideal budget z_i = <z_i,1, z_i,2, … z_i,M>

— User i’s utility for budget x is given by U_i(x) = ∑_{Projects j} min{z_i,j , x_j}

Discussion Points:

— Natural Notions of cost? Connections to utilities?

— How can we elicit utilities or ideal budgets? (what form should the vote take)?

— Natural notions of strategy-proofness?

Knapsack Voting

Ask users for a full budget

How would you aggregate?

Strategy-proofness?

Connections to Approval Voting

Other properties: Proportionality? Pareto-Optimality?