Edited, memorised or added to reading list

on 07-May-2017 (Sun)

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

Flashcard 1600035884300

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\)).

statusnot learnedmeasured difficulty37% [default]last interval [days]               
repetition number in this series0memorised on               scheduled repetition               
scheduled repetition interval               last repetition or drill

pdf

cannot see any pdfs







Flashcard 1600039292172

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 .

statusnot learnedmeasured difficulty37% [default]last interval [days]               
repetition number in this series0memorised on               scheduled repetition               
scheduled repetition interval               last repetition or drill

pdf

cannot see any pdfs







Flashcard 1600041651468

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 .

statusnot learnedmeasured difficulty37% [default]last interval [days]               
repetition number in this series0memorised on               scheduled repetition               
scheduled repetition interval               last repetition or drill

pdf

cannot see any pdfs







#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 σ .
statusnot read reprioritisations
last reprioritisation on reading queue position [%]
started reading on finished reading 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?
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 σ .

statusnot learnedmeasured difficulty37% [default]last interval [days]               
repetition number in this series0memorised on               scheduled repetition               
scheduled repetition interval               last repetition or drill

pdf

cannot see any pdfs







#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
statusnot read reprioritisations
last reprioritisation on reading queue position [%]
started reading on finished reading on

pdf

cannot see any pdfs




Flashcard 1600051350796

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 ?

statusnot learnedmeasured difficulty37% [default]last interval [days]               
repetition number in this series0memorised on               scheduled repetition               
scheduled repetition interval               last repetition or drill

pdf

cannot see any pdfs