# on 16-Apr-2017 (Sun)

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

#### Flashcard 1530923191564

Tags
#computation #social-choice
Question
Contagion Lemma
Answer
C being weakly decisive for a versus b implies C being (not just weakly) decisive for all pairs of alternatives.

status measured difficulty not learned 37% [default] 0

#### pdf

cannot see any pdfs

#### Annotation 1530925550860

 #computation #social-choice We call a coalition C ⊆ N of individuals a decisive coalition for alternative a versus alternative b if $$N_{a\succ b}^P\supseteq C$$ implies $$a\succ b$$
status not read

#### pdf

cannot see any pdfs

#### Flashcard 1530930269452

Tags
#computation #social-choice
Question
We call a coalition C ⊆ N of individuals a decisive coalition for alternative a versus alternative b if $$N_{a\succ b}^P\supseteq C$$ implies [...]
Answer
$$a\succ b$$

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
We call a coalition C ⊆ N of individuals a decisive coalition for alternative a versus alternative b if $$N_{a\succ b}^P\supseteq C$$ implies $$a\succ b$$

#### Original toplevel document (pdf)

cannot see any pdfs

#### Flashcard 1530931842316

Tags
#computation #social-choice
Question
We call a coalition C ⊆ N of individuals a [...] for alternative a versus alternative b if $$N_{a\succ b}^P\supseteq C$$ implies $$a\succ b$$
Answer
decisive coalition

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
We call a coalition C ⊆ N of individuals a decisive coalition for alternative a versus alternative b if $$N_{a\succ b}^P\supseteq C$$ implies $$a\succ b$$

#### Original toplevel document (pdf)

cannot see any pdfs

#### Annotation 1530933415180

 #computation #decisive-coalition #dictatorship #paretian #social-choice #weakly To say that f is weakly Paretian is the same as to say that the grand coalition N is decisive, and to say that f is dictatorial is the same as to say that there exists a singleton that is decisive.
status not read

#### pdf

cannot see any pdfs

#### Flashcard 1530937347340

Tags
#computation #decisive-coalition #dictatorship #paretian #social-choice #weakly
Question
To say that f is [...] is the same as to say that the grand coalition N is decisive, and to say that f is dictatorial is the same as to say that there exists a singleton that is decisive.
Answer
weakly Paretian

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
To say that f is weakly Paretian is the same as to say that the grand coalition N is decisive, and to say that f is dictatorial is the same as to say that there exists a singleton that is decisive.

#### Original toplevel document (pdf)

cannot see any pdfs

#### Flashcard 1530938920204

Tags
#computation #decisive-coalition #dictatorship #paretian #social-choice #weakly
Question
To say that f is weakly Paretian is the same as to say that the grand coalition N is decisive, and to say that f is [...] is the same as to say that there exists a singleton that is decisive.
Answer
dictatorial

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
To say that f is weakly Paretian is the same as to say that the grand coalition N is decisive, and to say that f is dictatorial is the same as to say that there exists a singleton that is decisive.

#### Original toplevel document (pdf)

cannot see any pdfs

#### Flashcard 1530940493068

Tags
#computation #decisive-coalition #dictatorship #paretian #social-choice #weakly
Question
To say that f is weakly Paretian is the same as [...], and to say that f is dictatorial is the same as to say that there exists a singleton that is decisive.
Answer
to say that the grand coalition N is decisive

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
To say that f is weakly Paretian is the same as to say that the grand coalition N is decisive, and to say that f is dictatorial is the same as to say that there exists a singleton that is decisive.

#### Original toplevel document (pdf)

cannot see any pdfs

#### Flashcard 1530942065932

Tags
#computation #decisive-coalition #dictatorship #paretian #social-choice #weakly
Question
To say that f is weakly Paretian is the same as to say that the grand coalition N is decisive, and to say that f is dictatorial is the same as to say [...]
Answer
that there exists a singleton that is decisive.

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
To say that f is weakly Paretian is the same as to say that the grand coalition N is decisive, and to say that f is dictatorial is the same as to say that there exists a singleton that is decisive.

#### Original toplevel document (pdf)

cannot see any pdfs

#### Flashcard 1530943638796

Tags
#computation #social-choice
Question
An SWF f is weakly Paretian if
Answer
for any two alternatives a, b ∈ A, it is the case that, if $$a\succ_i b$$ for all individuals i ∈ N, then also $$a\succ b$$.

status measured difficulty not learned 37% [default] 0

#### pdf

cannot see any pdfs

#### Annotation 1530946784524

 #computation #independent-of-irrelevant-alternatives #social-choice A social welfare function f is independent of irrelevant alternatives if, for any two alternatives a, b ∈ A, the relative ranking of a and b by the social preference order only depends on the relative rankings of a and b provided by the individuals
status not read

#### pdf

cannot see any pdfs

#### Flashcard 1530949143820

Tags
#computation #independent-of-irrelevant-alternatives #social-choice
Question
A social welfare function f is [...] if, for any two alternatives a, b ∈ A, the relative ranking of a and b by the social preference order only depends on the relative rankings of a and b provided by the individuals
Answer
independent of irrelevant alternatives

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
A social welfare function f is independent of irrelevant alternatives if, for any two alternatives a, b ∈ A, the relative ranking of a and b by the social preference order only depends on the relative rankings of a and b provided by the individuals

#### Original toplevel document (pdf)

cannot see any pdfs

#### Flashcard 1530950716684

Tags
#computation #independent-of-irrelevant-alternatives #social-choice
Question
A social welfare function f is independent of irrelevant alternatives if, for any two alternatives a, b ∈ A, the relative ranking of a and b by the social preference order only depends on [...]
Answer
the relative rankings of a and b provided by the individuals

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
A social welfare function f is independent of irrelevant alternatives if, for any two alternatives a, b ∈ A, the relative ranking of a and b by the social preference order only depends on the relative rankings of a and b provided by the individuals

#### Original toplevel document (pdf)

cannot see any pdfs

#### Flashcard 1530952289548

Tags
#computation #social-choice
Question
Splitting Lemma
Answer
we can always split a decisive coalition C into two nonempty subsets C 1 ,C 2 with C 1 ∪ C 2 = C and C 1 ∩ C 2 =∅ such that one of C 1 and C 2 is decisive for all pairs as well.

status measured difficulty not learned 37% [default] 0

#### pdf

cannot see any pdfs

#### Annotation 1530954648844

 #computation #social-choice We call C weakly decisive for a vs. b if we have at least that $$N_{a\succ b}^P=C$$ implies $$a\succ b$$
status not read

#### pdf

cannot see any pdfs

#### Flashcard 1530957794572

Tags
#computation #social-choice
Question
We call C weakly decisive for a vs. b if we have at least that [...] implies $$a\succ b$$
Answer
$$N_{a\succ b}^P=C$$

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
We call C weakly decisive for a vs. b if we have at least that $$N_{a\succ b}^P=C$$ implies $$a\succ b$$

#### Original toplevel document (pdf)

cannot see any pdfs

#### Flashcard 1530961202444

Tags
#arrows-impossibility-theorem #computation #proof #social-choice
Question
Outline Proof: (Arrow, 1951). When there are three or more alternatives, then every SWF that is weakly Paretian and IIA must be a dictatorship. Hint: use two important lemmas.
Answer
Prove Contagion Lemma using weak Pareto and IIA. Prove Splitting Lemma using Contagion Lemma, transitivity, weak Pareto and IIA. Apply Splitting Lemma multiple times.

status measured difficulty not learned 37% [default] 0

#### pdf

cannot see any pdfs

#### Flashcard 1530965134604

Tags
#arrows-impossibility-theorem #computation #social-choice
Question
Arrow's Impossibility Theorem?
Answer
When there are three or more alternatives, then every SWF that is weakly Paretian and IIA must be a dictatorship.

status measured difficulty not learned 37% [default] 0

#### pdf

cannot see any pdfs

#### Flashcard 1530968280332

Tags
#computation #social-choice
Question
What is the problem with many results of classical social choice theory?
Answer
They neglected the computational effort required to determine the outcome of the rules they sought to characterize.

status measured difficulty not learned 37% [default] 0

#### pdf

cannot see any pdfs

#### Annotation 1530970639628

 #computation #social-choice The practical acceptability of a voting rule or a fair allocation mechanism depends not only on its normative properties, but also on its implementability in a reasonable time frame.
status not read

#### pdf

cannot see any pdfs

#### Flashcard 1530973785356

Tags
#computation #social-choice
Question
The practical acceptability of a voting rule or a fair allocation mechanism depends not only on its [...], but also on its implementability in a reasonable time frame.
Answer
normative properties

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
The practical acceptability of a voting rule or a fair allocation mechanism depends not only on its normative properties, but also on its implementability in a reasonable time frame.

#### Original toplevel document (pdf)

cannot see any pdfs

#### Flashcard 1530975358220

Tags
#computation #social-choice
Question
The practical acceptability of a voting rule or a fair allocation mechanism depends not only on its normative properties, but also on its [...].
Answer
implementability in a reasonable time frame

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
The practical acceptability of a voting rule or a fair allocation mechanism depends not only on its normative properties, but also on its implementability in a reasonable time frame.

#### Original toplevel document (pdf)

cannot see any pdfs

#### Annotation 1530977193228

 #computation #social-choice a decision problem P is defined as a pair L P ,Y P where L P is a formal language, whose elements are called instances, and Y P ⊆ L P is the set of positive instances.
status not read

#### pdf

cannot see any pdfs

#### Flashcard 1530979552524

Tags
#computation #social-choice
Question
a decision problem P is defined as a pair L P ,Y P where L P is a formal language, whose elements are called instances, and Y P ⊆ L P is the [...].
Answer
set of positive instances

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
a decision problem P is defined as a pair L P ,Y P where L P is a formal language, whose elements are called instances, and Y P ⊆ L P is the set of positive instances.

#### Original toplevel document (pdf)

cannot see any pdfs

#### Annotation 1530981125388

 #computation #decision-problem #graph-theory #social-choice the problem of deciding whether a directed graph is acyclic is defined by the set L P of all directed graphs, while Y P is the set of all directed acyclic graphs.
status not read

#### pdf

cannot see any pdfs

#### Flashcard 1530985057548

Tags
#computation #decision-problem #graph-theory #social-choice
Question
Give an example of a decision problem in terms of directed graphs and acyclic graphs.
Answer
the problem of deciding whether a directed graph is acyclic is defined by the set L P of all directed graphs, while Y P is the set of all directed acyclic graphs.

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
the problem of deciding whether a directed graph is acyclic is defined by the set L P of all directed graphs, while Y P is the set of all directed acyclic graphs.

#### Original toplevel document (pdf)

cannot see any pdfs

#### Annotation 1530986892556

 #computation #social-choice A function (or search) problem is a set (L P ,S P ,R P ), where L P, R P is a decision problem and S P is another formal language (the set of possible solutions) and R P ⊆ L P × S P is a relation between instances and solutions, where (I, S) ∈ R P means that S is a solution for I.
status not read

#### pdf

cannot see any pdfs

#### Annotation 1530992397580

 #computation #social-choice An example of a function (search) problem (L P, S P, R P) in terms of graph theory is: find a nondominated vertex in a directed graph, if any and find all vertices with maximum outdegree are both search problems. Solving the function problem on instance I ∈ L P consists in outputting some S ∈ S P such that (I,S) ∈ R P , if any, and “no solution” otherwise.
status not read

#### pdf

cannot see any pdfs

#### Flashcard 1530995543308

Tags
#computation #social-choice
Question
An example of a function (search) problem (L P, S P, R P) in terms of graph theory is: find a nondominated vertex in a directed graph, if any. Solving the function problem on instance I ∈ L P [...] and “no solution” otherwise.
Answer
consists in outputting some S ∈ S P such that (I,S) ∈ R P , if any,

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
arch) problem (L P, S P, R P ) in terms of graph theory is: find a nondominated vertex in a directed graph, if any and find all vertices with maximum outdegree are both search problems. Solving the function problem on instance I ∈ L P <span>consists in outputting some S ∈ S P such that (I,S) ∈ R P , if any, and “no solution” otherwise.<span><body><html>

#### Original toplevel document (pdf)

cannot see any pdfs

#### Annotation 1530997116172

 #computation #social-choice Formally, an algorithm is polynomial if there exists a k ∈$$\mathbb{N}$$ such that its running time is in O(n k ), where n is the size of the input. Here, O(n k ) denotes the class of all functions that, for large values of n, grow no faster than c · n k for some constant number c (this is the “Big-O notation”). For instance, when k = 1, the running time is linear, and when k = 2, the running time is quadratic in n.
status not read

#### pdf

cannot see any pdfs

#### Flashcard 1531000524044

Tags
#computation #social-choice
Question
Formally, an algorithm is polynomial if [...] Here, O(n k ) denotes the class of all functions that, for large values of n, grow no faster than c · n k for some constant number c (this is the “Big-O notation”). For instance, when k = 1, the running time is linear, and when k = 2, the running time is quadratic in n.
Answer
there exists a k ∈$$\mathbb{N}$$ such that its running time is in O(n k ), where n is the size of the input.

status measured difficulty not learned 37% [default] 0

#### Parent (intermediate) annotation

Open it
Formally, an algorithm is polynomial if there exists a k ∈$$\mathbb{N}$$ such that its running time is in O(n k ), where n is the size of the input. Here, O(n k ) denotes the class of all functions that, for large values of n, grow no faster than c · n k for some constant number c (this is the “Big-O notation”). For instance, wh

#### Original toplevel document (pdf)

cannot see any pdfs

#### Annotation 1531002096908

 #computation #social-choice The famous P = NP conjecture states that the hardest problems in NP do not admit polynomial-time algorithms and are thus not contained in P. Although this statement remains unproven, it is widely believed to be true. Hardness of a problem for a particular class intuitively means that the problem is no easier than any other problem in that class. Both membership and hardness are established in terms of reductions that transform instances of one problem into instances of another problem using computational means appropriate for the complexity class under consideration. Most reductions in this book rely on reductions that can be computed in time polynomial in the size of the problem instances, and are called polynomial-time reductions. Finally, a problem is said to be complete for a complexity class if it is both contained in and hard for that class. For instance, deciding whether a directed graph possesses a Hamiltonian cycle is NP-complete
status not read

#### pdf

cannot see any pdfs

#### Annotation 1531003669772

 #computation #social-choice Besides P and NP, several other classes will be used in this book. Given a decision problem P = L P ,Y P , the complementary problem of P is defined as P = L P ,L P \ Y P . Given a complexity class C, a decision problem belongs to the class coC if P belongs to C. Notably, coNP is the class of all decision problems whose complement is in NP. For instance, deciding that a directed graph does not possess a Hamiltonian cycle is in coNP (and coNP-complete).
status not read

#### pdf

cannot see any pdfs

#### Annotation 1531005242636

 #computation #social-choice 1 .5 basic concepts in theoretical computer science 19 C , we denote by C C the set of all problems that can be solved by an algorithm for C equipped with C -oracles, where a C -oracle solves a problem in C (or in coC ) in unit time. The class P 2 , defined as P NP , is thus the class of all decision problems that can be solved in polynomial time with the help of NP-oracles, which answer in unit time whether a given instance of a problem in NP is positive or not. The class P 2 is the subset of P 2 consisting of all decision problems that can be solved in polynomial time using “logarithmically many” NP-oracles. Equivalently, P 2 may be defined as the subset of P 2 for which a polynomial number of NP-oracles may be used, but these need to be queried in parallel, that is, we cannot use the answer to one oracle to determine what question to put to the next oracle. Finally, P 2 = NP NP and P 2 = co NP 2 . Thus, for instance, P 2 is the class of decision problems for which the correctness of a positive solution can be verified in polynomial time by an algorithm that has access to an NP-oracle. The following inclusions hold: P ⊆ NP, coNP ⊆ P 2 ⊆ P 2 ⊆ P 2 , P 2 . It is strongly believed that all these inclusions are strict, although none of them was actually proven to be strict. Interestingly, P 2 and (to a lesser extent) P 2 , P 2 and P 2 play an important role in computational social choice (and indeed, we find them referred to in Chapters 3, 4, 5, 8, 12, and 17). We occasionally refer to other complexity classes (such as PLS or #P) in the book; they are introduced in the chapter concerned. For a full introduction and an extensive overview of computational complexity theory, we refer the reader to Papadimitriou (1994) and Ausiello et al. (1999).
status not read

#### pdf

cannot see any pdfs

#### Annotation 1531006815500

 #computation #social-choice 1.5.2 Linear and Integer Programming One notable computational problem is that of solving linear programs. A linear program consists of a set of variables x j (1 j n), a set of constraints indexed by i (1 i m), and an objective. Constraint i is defined by parameters a ij (1 j n) and b i , resulting in the following inequality constraint: n j=1 a ij x j b i . The objective is defined by parameters c j , resulting in the following objective: n j=1 c j x j . The goal is to find a vector of nonnegative values for the x j that maximizes the value of the objective while still meeting all the constraints (i.e., all the inequalities should hold). Natural variants, such as not requiring variables to take nonnegative values, allowing equality constraints, having a minimization rather than a maximization objective, and so on, are not substantively different from this basic setup. There is a rich theory of linear programming; for the purpose of this book, what is most important to know is that linear programs can be solved to optimality in polynomial time. Thus, if a computational problem can be formulated as (equivalently, reduced to) a polynomial- sized linear program, then it can be solved in polynomial time.
status not read

#### pdf

cannot see any pdfs

#### Flashcard 1531009699084

Question
The nose, like the rest of the face, has an [...] blood supply.
Answer
[default - edit me]

status measured difficulty not learned 37% [default] 0
Nasal Anatomy: Embryology, Skin and Soft Tissues, Blood Supply and Lymphatics
and columella. View Media Gallery Previous Next: Nerves Blood Supply and Lymphatics <span>The nose, like the rest of the face, has an abundant blood supply. The arterial supply to the nose may be principally divided into (1) branches from the internal carotid, namely the branches of the anterior and posterior ethmoid arteries from the ophth

#### Annotation 1531448528140

 #bayesianism #cognitive-science #computation #computational-psychology What Is Computational Cognitive Modeling? Research in computational cognitive mod- eling, or simply computational psychol- ogy, explores the essence of cognition (in- cluding motivation, emotion, perception, etc.) and various cognitive functionalities through developing detailed, process-based understanding by specifying corresponding computational models (in a broad sense) of representations, mechanisms, and pro- cesses. It embodies descriptions of cognition in computer algorithms and programs, based on computer science (Turing, 1950); that is, it imputes computational processes (in abroadsense)ontocognitivefunctions,and thereby it produces runnable computational models. Detailed simulations are then con- ducted based on the computational models (see, e.g., Newell, 1990; Rumelhart et al., 1986; Sun, 2002
status not read

#### pdf

cannot see any pdfs

#### Annotation 1531450101004

 #bayesianism #cognitive-science #computation #computational-psychology Computational models are mostly process-based theories, that is, they are mostly directed at answering the question of how human performance comes about; by what psychological mechanisms, processes, 1Therootsofcognitivesciencecan,ofcourse,be traced back to much earlier times. For example, Newell and Simon’s early work in the 1960s and 1970s has been seminal (see, e.g., Newell & Simon, 1976). The work of Miller, Galanter, and Pribram (1960) has also been highly influential. See Chap- ter 25 in this volume for a more complete historical perspective (see also Boden, 2006). and knowledge structures; and in what ways exactly. In this regard, note that it is also possible to formulate theories of the same phenomena through so-called product theories, which provide an accurate functional account of the phenomena but do not commit to a particular psychological mechanism or process (Vicente & Wang, 1998). Product theories may also be called blackbox theories or input-output theories. Product theories do not make predictions about processes (even though they may constrain processes). Thus, product theo- ries can be evaluated mainly by product measures. Process theories, in contrast, can be evaluated by using process measures when they are available and relevant (which are, relatively speaking, rare), such as eye movement and duration of pause in serial recall, or by using product measures, such as recall accuracy, recall speed, and so on. Evaluation of process theories using the latter type of measures can only be indirect, because process theories have to generate an output given an input based on the processes postulated by the theories (Vicente & Wang, 1998). Depending on the amount of process details specified, a computational model may lie somewhere along the continuum from pure product theories to pure process theories. There can be several different senses of “modeling” in this regard, as discussed in Sun and Ling (1998). The match of a model with human cognition may be, for exam- ple, qualitative (i.e., nonnumerical and rela- tive) or quantitative (i.e., numerical and ex- act). There may even be looser “matches” based on abstracting general ideas from ob- servations of human behaviors and then de- veloping them into computational models. Although different senses of modeling or matching human behaviors have been used, the overall goal remains the same, which is to understand cognition (human cogni- tion in particular) in a detailed (process- oriented) way. This approach of utilizing comp
status not read

#### pdf

cannot see any pdfs

#### Annotation 1531451673868

 #bayesianism #cognitive-science #computation #computational-psychology . As related by Hintzman (1990), “The common strategy of trying to reason backward from behav- ior to underlying processes (analysis) has drawbacks that become painfully apparent to those who work with simulation mod- els (synthesis). To have one’s hunches about how a simple combination of processes will behave repeatedly dashed by one’s own computer program is a humbling experience that no experimental psychologist should miss” (p. 111). One viewpoi
status not read

#### pdf

cannot see any pdfs

#### Flashcard 1531473431820

Question
regardless of
Answer
If something happens regardless of something else, it is not affected or influenced at all by that other thing.

status measured difficulty not learned 37% [default] 0

#### Flashcard 1531475528972

Tags
#english
Question
regardless off
Answer
this is the answer

status measured difficulty not learned 37% [default] 0