On the computability of quasi-transitive binary social choice rules in an infinite society and the halting problem

This paper investigates the computability problem of the existence of a vetoer and an oligarchy for quasi-transitive binary social choice rules (Mas-Colell and Sonnenschein in Rev Econ Stud 39:185–192, 1972) in a society with an infinite number of individuals (infinite society) according to the computable calculus (or computable analysis) by Aberth (Computable analysis, McGraw-Hill, New York, 1980; Computable calculus, Academic Press, Dublin, 2001). We will show the following results. The problem whether a quasi-transitive binary social choice rule which satisfies Pareto principle and independence of irrelevant alternatives (IIA) has a vetoer or has no vetoer in an infinite society is a nonsolvable problem, that is, there exists no ideal computer program for a quasi-transitive binary social choice rule which satisfies Pareto principle and IIA that decides whether it has a vetoer or has no vetoer. And it is equivalent to nonsolvability of the halting problem. We also show that if for any quasi-transitive binary social choice rule there exists an oligarchy in an infinite society, whether it is finite or infinite is a nonsolvable problem. A vetoer is an individual such that if he strictly prefers an alternative to another alternative, then the society prefers the former to the latter or is indifferent between them regardless of the preferences of other individuals, and an oligarchy is the minimal set of individuals which has dictatorial power and its each member is a vetoer. It will be shown that an oligarchy is a set of vetoers if it exists. This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Scientific Research (C), 20530165, and the Grant-in-Aid from the Zengin Foundation for Studies on Economics and Finance in Japan.     

On the continuity of representations of effectivity functions

An effectivity function assigns to each coalition of individuals in a society a family of subsets of alternatives such that the coalition can force the outcome of society’s choice to be a member of each of the subsets separately. A representation of an effectivity function is a game form with the same power structure as that specified by the effectivity function. In the present paper we investigate the continuity properties of the outcome functions of such representation. It is shown that while it is not in general possible to find continuous representations, there are important subfamilies of effectivity functions for which continuous representations exist. Moreover, it is found that in the study of continuous representations one may practically restrict attention to effectivity functions on the Cantor set. Here it is found that general effectivity functions have representations with lower or upper semicontinuous outcome function.     

On the existence of consistent rules to adjudicate conflicting claims: a constructive geometric approach

For the problem of adjudicating conflicting claims, a rule is consistent if the choice it makes for each problem is always in agreement with the choice it makes for each “reduced problem” obtained by imagining that some claimants leave with their awards and reassessing the situation from the viewpoint of the remaining claimants. We develop a general technique to determine whether a given two-claimant rule admits a consistent extension to general populations, and to identify this extension if it exists. We apply the technique to a succession of examples. I gratefully acknowledge support from NSF under grant SBR-9731431 and SES 0214691, and the comments of Carmen Bevia, Rodrigo Velez, Chun-Hsien Yeh, and a referee.     

Cores of effectivity functions and implementation theory

In a committee where cooperative voting occurs, effectivity functions describe the blocking power of coalitions. It is a binary relation that says for each coalition T and each subset of outcomes B whether or not T can force the final outcome within B. The corresponding cooperative stability notion generalizes the familiar core of a simple game. We study those effectivity functions yielding a non-empty core for all preference profiles, of which additive effectivity functions are an example. This proves to be closely related to implementation by means of the strong equilibrium concept.     

Model selection in univariate time series forecasting using discriminant analysis

When a large number of time series are to be forecast on a regular basis, as in large scale inventory management or production control, the appropriate choice of a forecast model is important as it has the potential for large cost savings through improved accuracy. A possible solution to this problem is to select one best forecast model for all the series in the dataset. Alternatively one may develop a rule that will select the best model for each series. Fildes (1989) calls the former an aggregate selection rule and the latter an individual selection rule. In this paper we develop an individual selection rule using discriminant analysis and compare its performance to aggregate selection for the quarterly series of the M-Competition data. A number of forecast accuracy measures are used for the evaluation and confidence intervals for them are constructed using bootstrapping. The results indicate that the individual selection rule based on discriminant scores is more accurate, and sometimes significantly so, than any aggregate selection method.     

Constitutional implementation

We consider the problem of implementing a social choice correspondence H in Nash equilibrium when the constitution of the society is given by an effectivity function E. It is assumed that the effectivity function of , is a sub-correspondence of E. We found necessary and efficient conditions for a game form to implement H (in Nash equilibria), and to satisfy, at the same time, that , the effectivity function of , is a sub-correspondence of (which guarantees that is compatible with E). We also find sufficient conditions for the coincidence of the set of winning coalitions of and , and for . All our results are sharp as is shown by suitable examples. Received: 15 December 2000 / Accepted: 3 September 2001     

On the equivalence of the Arrow impossibility theorem and the Brouwer fixed point theorem when individual preferences are weak orders

We will show that in the case where there are two individuals and three alternatives (or under the assumption of the free-triple property), and individual preferences are weak orders (which may include indifference relations), the Arrow impossibility theorem [Arrow, K.J., 1963. Social Choice and Individual Values, second ed. Yale University Press] that there exists no binary social choice rule which satisfies the conditions of transitivity, Pareto principle, independence of irrelevant alternatives, and non-existence of dictator is equivalent to the Brouwer fixed point theorem on a 2-dimensional ball (circle). Our study is an application of ideas by Chichilnisky [Chichilnisky, G., 1979. On fixed points and social choice paradoxes. Economics Letters 3, 347–351] to a discrete social choice problem, and also it is in line with the work by Baryshnikov [Baryshnikov, Y., 1993. Unifying impossibility theorems: a topological approach. Advances in Applied Mathematics 14, 404–415].     

A social choice function implementable via backward induction with values in the ultimate uncovered set

We prove the existence of a social choice function implementable via backward induction which always selects within the ultimate uncovered set. Whereas the uncovered set is the set of maximal elements of the covering relation, the ultimate uncovered set is the set obtained by iterative application of this covering operation. Dutta and Sen (1993) showed that any social choice function which is the solution of a generalized binary voting procedure is implementable via backward induction. Our result follows from Dutta and Sen's theorem, in that we construct a binary voting procedure always selecting within the ultimate uncovered set. We use the classical multistage elimination procedure, which always selects an alternative within the uncovered set. When this procedure is also used to select among all of the possible agendas or orderings of alternatives within the procedure, the alternative selected (from the agenda selected) will be within the uncovered set of the uncovered set. Our result follows from repeated application of this construction. Intuitively, the procedure constructed consists of requiring agents to vote on how they should vote and so on. Received: 7 April 1997 / Accepted: 15 October 1998     

A topological approach to Wilson’s impossibility theorem

We will present a topological approach to Wilson’s impossibility theorem [Wilson, R.B., 1972. Social choice theory without the Pareto principle. Journal of Economic Theory 5, 478–486] that there exists no non-null binary social choice rule which satisfies transitivity, independence of irrelevant alternatives, non-imposition and has no dictator nor inverse dictator. Our research is in line with the studies of topological approaches to discrete social choice problems initiated by [Baryshnikov, Y., 1993. Unifying impossibility theorems: a topological approach. Advances in Applied Mathematics 14, 404–415]. This paper extends the result about the Arrow impossibility theorem shown in [Tanaka, Y., 2006. A topological approach to the Arrow impossibility theorem when individual preferences are weak orders. Applied Mathematics and Computation 174, 961–981] to Wilson’s theorem.     

On properties of division rules lifted by bilateral consistency

We consider the problem of adjudicating conflicting claims in the context of a variable population. A property of rules is “lifted” if whenever a rule satisfies it in the two-claimant case, and the rule is bilaterally consistent, it satisfies it for any number of claimants. We identify a number of properties that are lifted, such as equal treatment of equals, resource monotonicity, composition down and composition up, and show that continuity, anonymity and self-duality are not lifted. However, each of these three properties is lifted if the rule is resource monotonic.     

Strategic behavior in non-atomic games

In order to remedy the possible loss of strategic interaction in non-atomic games with a societal choice, this study proposes a refinement of Nash equilibrium, strategic equilibrium. Given a non-atomic game, its perturbed game is one in which every player believes that he alone has a small, but positive, impact on the societal choice; and a distribution is a strategic equilibrium if it is a limit point of a sequence of Nash equilibrium distributions of games in which each player’s belief about his impact on the societal choice goes to zero. After proving the existence of strategic equilibria, we show that all of them must be Nash. We also show that all regular equilibria of smooth non-atomic games are strategic. Moreover, it is displayed that in many economic applications, the set of strategic equilibria coincides with that of Nash equilibria of large finite games.     

A policy-based rationalization of collective rules: Dimensionality,specialized houses,and decentralized authority

We offer a policy-basis for interpreting, justifying, and designing (3, 3)-political rules, a large class of collective rules analogous to those governing the selection of papers in peer-reviewed journals, where each referee chooses to accept, reject, or invite a resubmission of a paper, and an editor aggregates his own and referees’ opinions into one of these three recommendations. We prove that any such rule is a weighted multicameral rule: a policy is collectively approved at a given level if and only if it is approved by a minimal number of chambers — the dimension of the rule — where each chamber evaluates a different aspect of the policy using a weighted rule, with each evaluator’s weight or authority possibly varying across chambers depending on his area(s) of expertise. These results imply that a given rule is only suitable for evaluating finite-dimensional policies whose dimension corresponds to that of the rule, and they provide a rationale for using different rules to pass different policies even within the same organization. We further introduce the concept of compatibility with a rule and exploit its topological properties to propose a method to construct integer weights corresponding to evaluators’ possible judgments under a given rule, which are more intuitive and easier to interpret for policymakers. Our findings shed light on multicameralism in political institutions and multi-criteria group decision-making in the firm. We provide applications to peer review politics, rating systems, and real-world organizations.     

A coalitional game-theoretic model of stable government forms with umpires

In this paper a government form is modeled as an effectivity function scheme (EFS) i.e. a parameterized family of effectivity functions having admissible weight-profiles of assemblies as the relevant parameters. Working in a 2-jurisdiction outcome space we show that the existence of umpires is consistent with strong core-stability of both neo-parliamentary and semi-presidential government forms provided that the majority formation rule is collegial, namely there is one electorally fixed minimal majority coalition.      

Repeated implementation and complexity considerations

A game form is commitment-free if single actions of players do not have physical consequences, i.e., affect the continuation game. Such game can be thought to represent inifinite interaction with complete patience. A choice rule can be Nash implemented via a commitment-free mechanism if and only if it coincides with the feasible set of a normal form game. However, when players are complexity averse (in the lexicographic sense), then any Nash implementable choice rule becomes available. I am very grateful to Matt Jackson and a referee for their comments. I also thank Klaus Kultti and Hannu Salonen for useful conversations.     

Nash implementing social choice rules with restricted ranges

We consider Nash implementation of social choice rules with restricted ranges, i.e., where some of the available alternatives are chosen at no preference profile. We show that the appropriate adaptation of Maskin monotonicity to this context depends on the range of the mechanisms: the wider is this range, the weaker is the monotonicity condition to be used. As a result, mechanisms employing outcome functions which allow for out-of-range alternatives at off-equilibrium messages can Nash implement social choice rules which fail to be Nash implementable by mechanisms whose ranges are restricted to the range of the social choice rule to be implemented. The Walrasian social choice correspondence is a particular instance of this. Moreover, social choice rules which are not Maskin monotonic can be “monotonized” by the addition of artificial out-of-range alternatives—a point we illustrate through Solomon’s Dilemma.     

Corporate social responsibility and economic performance

We describe some perspectives on corporate social responsibility (CSR), in order to provide a context for considering the strategic motivations and implications of CSR. Based on this framework, which is based on characterizing optimal firm decision-making and underlies most existing work on CSR, we propose an agenda for further theoretical and empirical research on CSR. We then summarize and relate the articles in this special issue to the proposed agenda.     

Hierarchies of power in non-binary social choice

In the context of fixed agenda social choice correspondences, and by imposing usual axioms, we prove that power is distributed among either a non-complete hierarchy of dictators or of individuals with veto power in the society, which allows us to explicitly describe the social choice set as an alternative maximization process.     

Inefficiency of equilibria in digital mechanisms with continuous valuations

A digital mechanism is defined as an iterative procedure in which bidders select an action, from a finite set, in each iteration. When bidders have continuous valuations and make strategic reports, we show that any ex post implementation of the Vickrey choice rule via such a mechanism needs infinitely many iterations for almost all realizations of the bidders’ valuations. Thus, when valuations are drawn from a continuous probability distribution, the Vickrey choice rule can only be used at the expense of a running time that is infinite with probability one. This infeasibility result even holds in the case of two bidders and the Vickrey choice rule only being required to be established with probability one. Establishing the efficient allocation when the $n$ bidders’ report truthfully contrasts starkly to the previous setting: a bisection procedure has a finite running time almost always, and an expected number of reports are equal to $2n$. Using a Groves payment scheme rather than Vickrey’s second price payment scheme somewhat mitigates the problem. We provide an example mechanism with a Groves payment scheme, in which the running time of the mechanism in equilibrium is finite with probability $\frac{1}{2}$.     

Acyclicity,anonymity, and prefilters

We analyze the decisiveness structures associated with acyclical collective choice rules. In particular, we examine the consequences of adding anonymity to weak Pareto, thereby complementing earlier results on acyclical social choice. Both finite and countably infinite populations are considered. As established in contributions by Donald Brown and by Jeffrey Banks, acyclical social choice is closely linked to prefilters in the presence of the weak Pareto principle. We introduce the notion of a conditional prefilter and use it to generalize their results. In the finite-population case, adding anonymity implies that the collection of decisive sets is a special case of a conditional prefilter. We then identify the decisiveness structure that results from adding anonymity to the weak Pareto principle. Moving to infinite populations, we obtain the decisive set that consists of the entire population as a possibility, along with a new class of prefilters that we refer to as symmetric free Fréchet prefilters. The choice of the term Fréchet prefilter is motivated by the observation that they share a defining property with the well-known Fréchet filter—namely, that all sets in the requisite collection are such that their complement is finite.     

The dynamics of public opinion under majority rules

This note explains the process of public opinion formation via a locally interactive, space-time analysis. The model we use is a special case of the general framework for modelling social interaction proposed in Blume and Durlauf (2001). In the reduced form of the model we study how each individual, when faced with the choice of one, out of two, opinions, tends to conform to the opinion held by the majority of her neighbours. We consider different, symmetric and asymmetric, majority rules. Depending on the specific behavioral rule, the aggregate process of opinion formation may display contagion on one specific opinion, or consensus among all individuals in the population, or co-existence of both opinions. Whenever consensus obtains, we observe the formation of homogeneous areas ( clusters) that seem almost stationary along the dynamics. The authors wish to thank A. Postelwaite and two anonymous referees for very helpful suggestions.