# on 07-May-2017 (Sun)

#### Flashcard 1600035884300

Question
What is a refinement of a partial order in the context of social choice theory?
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 measured difficulty not learned 37% [default] 0

#### pdf

cannot see any pdfs

#### Flashcard 1600039292172

Question
What is a possible winner in the context of social choice theory?
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 measured difficulty not learned 37% [default] 0

#### pdf

cannot see any pdfs

#### Flashcard 1600041651468

Question
What is a Necessary Winner in social choice theory?
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 measured difficulty not learned 37% [default] 0

#### pdf

cannot see any pdfs

#### Annotation 1600044010764

 #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 σ .

#### pdf

cannot see any pdfs

#### Flashcard 1600045583628

Tags
#computation #social-choice
Question
In Mallows φ-model of cultures in social choice, what do we obtain for φ=1, φ=0 respectively?
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 measured difficulty not learned 37% [default] 0

#### pdf

cannot see any pdfs

#### Annotation 1600047942924

 #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

#### pdf

cannot see any pdfs

#### Flashcard 1600051350796

Question
State the Possible Winner Problem as a decision problem given a voting rule F.
Instance: Profile of partial ballots R ∈ $$\mathcal{P}(x)^n$$ ; alternative x* ∈ X.