Lecture 6: Social Choice Part 2

목차

Voting rules

A voting rule is a function f : R(U)ⁿ → F(U)

 

Every voting rule is usually seen as a Social Choice Function (SCF), but not always the other way round. 

- A SCF, defined by f: R(U)ⁿ × F(U) →  F(U), requires the definition of a feasible subset of the alternatives

- Some of the SCFs cannot be considered voting rules because they are not discriminatory enough.

 

Some properties of voting rules:

- Resoluteness: they should always yield a unique winner (𝑓 is resolute if | 𝑓 (R) |  = 1 for all preference profiles R

- Anonymity: symmetry w.r.t. agents (the votes count the same). 모든 투표는 동일하게 한 표.

- Neutrality: symmetry w.r.t. alternatives (e.g. if A wins with 30 votes, then B can also win with 30 votes)

 

However, these properties can often not be satisfied.

e.g. Two agents and two alternatives. 이 경우에는 Resoluteness를 만족시키지 못한다. A와 B 둘 다 당첨이기 때문.

 

 

Plurality Rule (최다 득표수)

Consider how often each alternative is ranked in the first place. (1등을 가장 많이 한 선택지가 당첨)

A common objection to rules such as the plurality rule is that an alternative ought to get some credit for being ranked, e.g. second place.

근데 Plurality rule 같은 경우에는 1등 선택지만 점수를 준다. 따라서, 2등 선택지나 다른 선택지는 아무 점수도 받지 못한다. 

 

 

Scoring rules

Under a scoring rule, the alternatives also get some score,

Under a scoring rule, each time an alternative is ranked i - th by some voter, it gets a particular score S¡

For a fixed number of alternatives m, we define a score vector

s = {s1, ... , sm} such that s1 ≥ ... ≥ sm, and s1 > sm

 

Plurality and Anti-plurality rules

 

Plurality rule: We can also define the plurality rule as a scoring rule. The score vector for the plurality rule is (1, 0, ..., 0). 

- The cumulative score of an alternative equals the number of voters by which it is ranked first

 

Anti-plurality rule: The score vector for the anti-plurality rule (a.k.a veto rule) is (1, ..., 1, 0). 

veto = (법안을) 거부하다. 즉, 꼴찌만 0점을 주는 방식.

 

Ex) Plurality and Anti-plurality rule

 

 

Borda's rule

Borda's rule: Alternative a gets k points from voter i, if i prefers a to k other alternatives, i.e. the score vectors is 

( | U | - 1, | U | - 2, ... , 0)

Borda's rule chooses those alternatives with the highest average rank in individual rankings 

즉, 보르다에서는 위의 방식으로 점수를 매긴 이후 가장 점수가 높은 대안이 당첨.

 

Ex) Borda's rule

 

 

Condorcet extensions

콩도르세 확장편에는 Condorcet winner, 즉 콩도르세 승자가 따로 존재한다. 위에 있었던 Scoring rules에서는 콩도르세 승자를 뽑지 못하는 경우도 있다.

Condorcet extension: rules to select Condorcet winner

Condorcet winner is an alternative that beats every other alternatives in pairwise majority comparisons

 

이 예시처럼 cycle이 나오는 경우에는 콩도르세 승자가 없다.

 

 

Ex) Condorcet extensions

 

→ 이 예시에서는 Scoring rule, 즉 Plurality (s2 = 0)나 Anti-plurality 방식을 썼을 때 b가 승자이다 (어떤 score vector를 사용하든 간에). 하지만, pairwise comparison, 즉 쌍별 비교를 하면 a가 b보다 더 선호되고 a가 c보다도 더 선호되기 때문에 a가 콩도르세 승자가 된다. 이 경우에도 Scoring rule을 썼을 때 승자와 콩도르세 승자가 다르다.

 

There are some rules that try to satisfy Condorcet's criterion: they are called Condorcet extensions. 

These rules will elect the Condorcet winner if there is one

They might also elect a winner when there is no Condorcet winner (different Condorcet extensions may elect different winners in the case of a cycle). → 즉, 콩도르세 승자가 없어도 승자를 뽑을 수 있다.

 

 

Copeland's rule:

An alternative gets a point for every pairwise majority win, and some fixed number of points between 0 and 1 (e.g. 0.5 point) for every pairwise tie

The winners are alternatives with the greatest number of points 

 

Ex) Copeland's rule

 

 

Maximin rule

Under this rule, we consider the magnitude of pairwise election results (by how many voters one alternative was preferred to the other)

We evaluate every alternative by its worst pairwise defeat by another alternative

The winners are those who lose by the lowest margin in their worst pairwise defeats (if there are alternatives with no pairwise defeats) → Condorcet winner

Let (X, Y) denote the pairwise score for X against Y. The candidate selected by maximin is given by:

W = arg min (max ( d(X, Y) - d(Y, x) ) )

→ 이 공식을 풀어보면, 각 alternative 마다 가장 크게 진, 즉 worst pairwise defeats를 나열하고, 그중에서 min, 즉 가장 작은 alternative가 승자가 된다.

 

Ex) Maximin rule 1

 

Ex) Maximin rule 2

 

Maximin and for other voting rules, sometimes they are not resolute as can be seen in this example. (승자가 하나가 아니라 여러 개)

 

 

Nanson's rule:

Runoff method (i.e. multiple rounds). 한 번만 하는 게 아니라 하나씩 선택지를 없애면서 함.

Series of Borda elections (Schwartz variant): For each Borda election, exclude the alternative which have less than the average Borda score unless all alternatives have identical Borad score, in which case these candidates are declared the winners. 

즉, 보르다 계산법으로 점수들을 계산을 한 후에 평균 보르다 점수보다 낮으면 선택지에서 제외를 하나의 선택지가 남을 때까지 한다.

 

예시 1:

 

예시 2:

 

 

 

Other rules

There are many oher rules that are neither scoring rules, nor Condorcet extensions, for example:

 

Single Transferable Vote (STV):

- Looks for alterntives that are ranked in first place the least often, removes them from all voter's ballot, and repeats

- The alternative removed in the last round win

즉, 1등을 한 횟수가 가장 적은 선택지를 각 라운드마다 없애고 마지막에 남은 선택지가 당첨.

 

예시 1.

 

예시 2.

 

 

Strategic Manipulation (전략적 조작)

So far, we assumed that the true preferences of all agents are known (no agent is lying).

However, we only have access to their reported preferences.

This is an unrealistic assumption because agents might respresent their prefernees to exploit the voting rules.

 

예시. Plurality Rule

 

이 경우에서는 마지막에 있는 사람들은 b를 a보다 더 선호하므로 단합을 해서 투표를 바꿀 수도 있다. 이렇게 되면 a가 당첨이 안 되고 b가 당첨이 돼서 더 선호하는 결과가 된다 (Coalition).

 

예시. Borda Count

 

여기서도 b가 당첨이 되는데 두 번째에 있는 사람들이 a와 c를 바꿈으로써 c가 당첨되게 한다. (더 선호하는 결과)

 

Why avoid manipulation? (왜 조작하는 걸 방지해야 하는지)

- It can decrease fairness since manipulative skills are not spread evenly

- Hard to evaluate whether the outcome respects agent's "true preferences" or not

 

Unfortunately, every voting rule is susceptible to manipulation

 

The Gibbard-Satterthwaite Impossibility Theorem: every non-imposing, strategyproof, resolute voting rule is dictatorial when | U | ≥ 3

- Non-imposing: for every alternative, there exist a preference profile that would make that alternative win 

- Strategyproof: it is not manipulable (조작할 수 없는)

→ Alternative가 3개 이상일 때, voting rule이 non-dictatorship, non- manipulability, unrestricted domain을 만족하면 susceptible to strategic manipulation.

1. Non-dictatorship: the voting method must take into account the preferences of all voters.
2. Unrestricted domain: The voting method should be applicable to all possible combinations of preferences among the voters.

The Gibbard-Satterthwaite theorem requires that the voting rule is defined for all possible preferences profiles

However, if we restrict the domain of possible profiles, we might create strategyproof solutions

- Domain of single-peaked preferences e.g. when it is possible to establish a linear ordering of the alternatives

- Preferences are single-peaked if for every voter, the alternative will become less preferred for that voter

- if (x < y < z) or (z < y < x), then x  >¡  y implies y  >¡  z for every i ∈ N

e.g. Tax rate = {20%, 25%, 30%}