Constitutional implementation of social choice correspondences

A game form constitutionally implements a social choice correspondence if it implements it in Nash equilibrium and, moreover, the associated effectivity functions coincide. This paper presents necessary and sufficient conditions for a unanimous social choice correspondence to be constitutionally implementable, and sufficient and almost necessary conditions for an arbitrary (but surjective) social choice correspondence to be constitutionally implementable. It is shown that the results apply to interesting classes of scoring and veto social choice correspondences.     

On the reversal bias of the Minimax social choice correspondence

We introduce three different qualifications of the reversal bias in the framework of social choice correspondences. For each of them, we prove that the Minimax social choice correspondence is immune to it if and only if the number of voters and the number of alternatives satisfy suitable arithmetical conditions. We prove those facts thanks to a new characterization of the Minimax social choice correspondence and using a graph theoretical approach. We discuss the same issue for the Borda and Copeland social choice correspondences.     

Sub-core solutions of the problem of strong implementation

The problem of strong implementation is to determine which social choice correspondences (SCC) can be obtained as the strong equilibrium correspondence of a game form. We introduce the notion of the nucleus of an effectivity function. Under certain conditions, it yields the smallest implementable SCC having that effectivity function. We contrast it with the core, which yields the largest implementable SCC (as shown by Moulin and Peleg), and argue that the smaller solution should be preferred when available. Another result is that the known necessary conditions for implementability are not sufficient, except in the case of (at most) 3 alternatives.     

Existence of solutions for systems of generalized quasi‐equilibrium problems

In this paper, first of all, we consider a generalized game in choice form with 2 constraints and its corresponding equilibrium in choice. We assert new conditions under which the equilibrium in choice exists. As a consequence, we establish the existence of the equilibrium for generalized abstract economies. Then, we apply the obtained theorems to prove the existence of solutions for systems of quasi‐equilibrium problems. We do this by considering new hypotheses for the properties of the involved correspondences. This approach leads us to results which differ a lot from the ones existing in literature.     

Consistent and covariant solutions for TU games

One of the important properties characterizing cooperative game solutions is consistency. This notion establishes connections between the solution vectors of a cooperative game and those of its reduced game. The last one is obtained from the initial game by removing one or more players and by giving them the payoffs according to a specific principle (e.g. a proposed payoff vector). Consistency of a solution means that the restriction of a solution payoff vector of the initial game to any coalition belongs to the solution set of the corresponding reduced game. There are several definitions of the reduced games (cf., e.g., the survey of T. Driessen [2]) based on some intuitively acceptable characteristics. In the paper some natural properties of reduced games are formulated, and general forms of the reduced games possessing some of them are given. The efficient, anonymous, covariant TU cooperative game solutions satisfying the consistency property with respect to any reduced game are described.The research was supported by the NWO grant 047-008-010 which is gratefully acknowledgedReceived: October 2001     

A Modified Tikhonov Regularization for Linear Operator Equations

We construct with the aid of regularizing filters a new class of improved regularization methods, called modified Tikhonov regularization (MTR), for solving ill-posed linear operator equations. Regularizing properties and asymptotic order of the regularized solutions are analyzed in the presence of noisy data and perturbation error in the operator. With some accurate estimates in the solution errors, optimal convergence order of the regularized solutions is obtained by a priori choice of the regularization parameter. Furthermore, numerical results are given for several ill-posed integral equations, which not only roughly coincide with the theoretical results but also show that MTR can be more accurate than ordinary Tikhonov regularization (OTR).     

Non-binding agreements and fairness in commons dilemma games

Usually, common pool games are analyzed without taking into account the cooperative features of the game, even when communication and non-binding agreements are involved. Whereas equilibria are inefficient, negotiations may induce some cooperation and may enhance efficiency. In the paper, we propose to use tools of cooperative game theory to advance the understanding of results in dilemma situations that allow for communication. By doing so, we present a short review of earlier experimental evidence given by Hackett, Schlager, and Walker 1994 (HSW) for the conditional stability of non-binding agreements established in face-to-face multilateral negotiations. For an experimental test, we reanalyze the HSW data set in a game-theoretical analysis of cooperative versions of social dilemma games. The results of cooperative game theory that are most important for the application are explained and interpreted with respect to their meaning for negotiation behavior. Then, theorems are discussed that cooperative social dilemma games are clear (alpha- and beta-values coincide) and that they are convex (it follows that the core is “large”): The main focus is on how arguments of power and fairness can be based on the structure of the game. A second item is how fairness and stability properties of a negotiated (non-binding) agreement can be judged. The use of cheap talk in evaluating experiments reveals that besides the relation of non-cooperative and cooperative solutions, say of equilibria and core, the relation of alpha-, beta- and gamma-values are of importance for the availability of attractive solutions and the stability of the such agreements. In the special case of the HSW scenario, the game shows properties favorable for stable and efficient solutions. Nevertheless, the realized agreements are less efficient than expected. The realized (and stable) agreements can be located between the equilibrium, the egalitarian solution and some fairness solutions. In order to represent the extent to which the subjects obey efficiency and fairness, we present and discuss patterns of the corresponding excess vectors.     

The cohesiveness of subgroups in social networks: A view from game theory

A family of cohesiveness measures, based on game theoretical concepts, is proposed for subgroups in social networks. Given a communication situation, consisting of a coalitional game and a graph, both defined on the same set of players-nodes, cohesiveness of a subset is defined as the proportion of their worth that the players in subset retain, when the originally deterministic (restricted) graph becomes a probabilistic one (in a specific manner). Conditions on the game are given to reach some desirable properties.     

Computing tournament solutions using relation algebra and RelView

We describe a simple computing technique for the tournament choice problem. It rests upon relational modeling and uses the BDD-based computer system RelView for the evaluation of the relation-algebraic expressions that specify the solutions and for the visualization of the computed results. The Copeland set can immediately be identified using RelView’s labeling feature. Relation-algebraic specifications of the Condorcet non-losers, the Schwartz set, the top cycle, the uncovered set, the minimal covering set, the Banks set, and the tournament equilibrium set are delivered. We present an example of a tournament on a small set of alternatives, for which the above choice sets are computed and visualized via RelView. The technique described in this paper is very flexible and especially appropriate for prototyping and experimentation, and as such very instructive for educational purposes. It can easily be applied to other problems of social choice and game theory.     

Representation of characteristic function games by social choice functions

In Peleg's investigation of the representation of a simple game by a social choice function, it is shown that a special kind of proper symmetric simple game has its representation by employing the elimination procedure. In this paper, we consider a representation of a characteristic function game and explore general conditions under which the elimination procedure works effectively.     

The generalized Weierstrass system inducing surfaces of constant and nonconstant mean curvature in Euclidean three space

The generalized Weierstrass (GW) system is introduced and its correspondence with the associated two-dimensional nonlinear sigma model is reviewed. The method of symmetry reduction is systematically applied to derive several classes of invariant solutions for the GW system. The solutions can be used to induce constant mean curvature surfaces in Euclidean three space. Some properties of the system for the case of nonconstant mean curvature are introduced as well.     

Consistent social choice functions and systems of distinct representatives

This paper concerns Peleg's construction of a strongly consistent voting system. The authors characterize the alternatives selected by the corresponding social choice correspondence in terms of systems of distinct representatives. This result allows the use of ‘rapid’ computational algorithms for this correspondence.     

Equilibria of the Games in Choice Form

Equilibrium in choice is a solution-concept for noncooperative games defined in a general framework??the game in choice form. There are two leading ideas of the new definition. One is that the players?? preferences need not be explicitly represented, but earlier accepted solution concepts should be formally derived as particular cases. Secondly, the choice of a player need not be a best reply to the strategy combination of the others, if the choices of the other players are motivated for themselves and a best reply does not exist. It is shown that in the present framework are included classical models of game theory, and the new concept extends various known noncooperative solutions. The main technical results of the paper concern the existence of the equilibrium in choice. As particular cases, known results on the existence of classical solutions are found. Thus, our approach can be also seen as a general method for proving the existence of different solutions for noncooperative games.     

Minimal Zero Norm Solutions of Linear Complementarity Problems

In this paper, we study minimal zero norm solutions of the linear complementarity problems, defined as the solutions with smallest cardinality. Minimal zero norm solutions are often desired in some real applications such as bimatrix game and portfolio selection. We first show the uniqueness of the minimal zero norm solution for Z-matrix linear complementarity problems. To find minimal zero norm solutions is equivalent to solve a difficult zero norm minimization problem with linear complementarity constraints. We then propose a p norm regularized minimization model with p in the open interval from zero to one, and show that it can approximate minimal zero norm solutions very well by sequentially decreasing the regularization parameter. We establish a threshold lower bound for any nonzero entry in its local minimizers, that can be used to identify zero entries precisely in computed solutions. We also consider the choice of regularization parameter to get desired sparsity. Based on the theoretical results, we design a sequential smoothing gradient method to solve the model. Numerical results demonstrate that the sequential smoothing gradient method can effectively solve the regularized model and get minimal zero norm solutions of linear complementarity problems.     

Multi-attribute decision-making in individual and social choice

This paper provides an analysis of individual and social decision criteria for alternatives that are composed of several attributes. We derive additive and multiplicative criteria for individual decision-making with new axioms and apply these criteria to obtain new justifications of known social choice rules with a bargaining interpretation, namely the generalized utilitarian and Nash social choice functions. Unlike most axiomatizations of bargaining solutions, our approach is, to a large extent, based on the multi-attribute structure of the underlying alternatives and the resulting individual decision criteria instead of axioms that impose restrictions on the choice function directly.     

Approaches to collective decision making with fuzzy preference relations

Recent experimental studies show that the predictive accuracy of many of the solution concepts derived from the collective decision making theory leaves much to be desired. In a previous paper the author attempted to explain some of the inaccuracies in terms of the fuzzy indifference regions of the individuals participating in the voting game. This paper gives straightforward generalizations of the solutions concepts in terms of the fuzzy social or individual preference relations. It turns out that some of these new solution concepts cotain their nonfuzzy counterparts as subsets. Others, in turn, are subsets of their nonfuzzy counterparts. We also discuss a method of aggregating individual nonfuzzy preferences so as to get a fuzzy social preference relation and, furthermore, a nonfuzzy social choice set.     

A two-population game in observable double-ended queuing systems

In this study, the existing game theoretical framework is extended to strategic queuing in search of solutions for a two-population game in observable double-ended queuing systems with zero matching times. We show that multiple Nash equilibria and one unique subgame perfect Nash equilibrium exist in this game.     

Noncooperative facility location games

A noncooperative game theoretical approach is considered for the multifacility location problem. It turns out that the facility location game is a potential game in the sense of Monderer and Shapley and some properties of the game are studied.     

Dominance solvable games and trees

We study social choice functions represented by Moulin's dominance solvable games. We first show that dominance solvability of games is independent of the order in which dominated strategies are deleted. This implies that the perfect equilibrium of a game with perfect information generally coincides with its solution according to dominance solvability. Then we show that a large class of d-solvable games yields the same social choice functions as those represented by games of perfect information. We show that for three alternatives and all n relatively prime to 6 there exists a method of social choice fractional elimination, which can be represented by a kingmaker tree. This covers some cases not previously covered by Moulin. We also find numerous examples.