on 16-Apr-2017 (Sun)

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

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.

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

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

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.

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.

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.

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.

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.

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.

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

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

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

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.

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

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

. 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