Do you want BuboFlash to help you learning these things? Click here to log in or create user.

Question

What is a refinement of a partial order in the context of social choice theory?

Answer

Let \(\mathcal{P}\)( X ) be the class of partial orders on the set of alternatives X . The linear order ( \(\succ^l\) ) ∈ \(\mathcal{L}\)( X ) refines the partial order (\(\succ^p\)) ∈ \(\mathcal{P}\) ( X ) if (\(\succ^l\)) ⊇ (\(\succ^p\)).

status | not learned | measured difficulty | 37% [default] | last interval [days] | |||
---|---|---|---|---|---|---|---|

repetition number in this series | 0 | memorised on | scheduled repetition | ||||

scheduled repetition interval | last repetition or drill |

Question

What is a possible winner in the context of social choice theory?

Answer

Definition: Given a partial profile R ∈ \(\mathcal{P}(X)^n\), an alternative x* ∈ X is called a possible winner under voting rule F if x* ∈ F ( R* ) for some profile of linear ballots R*∈\(\mathcal{L}(X)^n\) that refines R .

status | not learned | measured difficulty | 37% [default] | last interval [days] | |||
---|---|---|---|---|---|---|---|

repetition number in this series | 0 | memorised on | scheduled repetition | ||||

scheduled repetition interval | last repetition or drill |

Question

What is a Necessary Winner in social choice theory?

Answer

Given a profile of partial ballots R ∈ \(\mathcal{P}(X)^n\) , an alternative x* ∈ X is called a necessary winner under voting rule F if x* ∈ F ( R* ) for all profiles of linear ballots R* ∈ \(\mathcal{L}(X)^n\) that refine R .

status | not learned | measured difficulty | 37% [default] | last interval [days] | |||
---|---|---|---|---|---|---|---|

repetition number in this series | 0 | memorised on | scheduled repetition | ||||

scheduled repetition interval | last repetition or drill |

#computation #social-choice

A commonly used model, adopted widely in machine learning is the Mallows φ-model (Mallows, 1957). It is parameterized by a modal or reference ranking σ and a dispersion parameter φ ∈ (0, 1]; and for any rank- ing r we define: P (r; σ, φ) = 1 Z φ d(r,σ ) , where d is the Kendall tau distance and Z = r φ d(r ,σ ) = 1 ·(1 + φ) · (1 +φ + φ 2 ) ···(1 +···+φ m−1 ) is a normalization constant. 6 When φ = 1 we obtain the uniform distribution over rankings (i.e., impar- tial culture), and as φ → 0 we approach the distribution that concentrates all mass on σ .

status | not read | reprioritisations | ||
---|---|---|---|---|

last reprioritisation on | reading queue position [%] | |||

started reading on | finished reading on |

Tags

#computation #social-choice

Question

In Mallows φ-model of cultures in social choice, what do we obtain for φ=1, φ=0 respectively?

Answer

When φ = 1 we obtain the uniform distribution over rankings (i.e., impar- tial culture), and as φ → 0 we approach the distribution that concentrates all mass on σ .

status | not learned | measured difficulty | 37% [default] | last interval [days] | |||
---|---|---|---|---|---|---|---|

repetition number in this series | 0 | memorised on | scheduled repetition | ||||

scheduled repetition interval | last repetition or drill |

#computation #social-choice

First, it is easy to observe that if the number m of alternatives A is bounded—assuming voters are not weighted (we briefly discuss weighted voters in what follows) and the voting rule satisfies anonymity—then both PW and NW are computable in polynomial time if the voting rule supports polynomial winner determination (Conitzer et al., 2007; Walsh, 2007). This is so because there are only a constant number of distinct votes b = m! that may be cast by any voter. By anonymity, the number of voters casting each vote is sufficient to determine a winner, and there are at most (n + 1) b such “count” profiles that need to be enumerated

status | not read | reprioritisations | ||
---|---|---|---|---|

last reprioritisation on | reading queue position [%] | |||

started reading on | finished reading on |

Question

State the Possible Winner Problem as a decision problem given a voting rule F.

Answer

PossibleWinner(F )

Instance: Profile of partial ballots R ∈ \(\mathcal{P}(x)^n\) ; alternative x* ∈ X.

Question: Is x* a possible winner under voting rule F ?

Instance: Profile of partial ballots R ∈ \(\mathcal{P}(x)^n\) ; alternative x* ∈ X.

Question: Is x* a possible winner under voting rule F ?

status | not learned | measured difficulty | 37% [default] | last interval [days] | |||
---|---|---|---|---|---|---|---|

repetition number in this series | 0 | memorised on | scheduled repetition | ||||

scheduled repetition interval | last repetition or drill |