The generation of a social welfare function under ordinal preferences

Against the background of recent impossibility theorems, the paper establishes a number of rules for the formation of social preferences to ensure the generation of a Bergson-Samuelson social welfare function of the desired ‘individualistic’ form. It demonstrates that such welfare functions can indeed exist under conditions of simply ordinality of individual preferences and a lack of interpersonal comparability, for the general n-person case with only weak restrictions upon individual preferences. A valuable tool of social welfare theory for the single-profile case is therefore restored under a wide set of conditions. By examining Kemp and Ng's justification for their A3 condition in this context, we are able also to highlight a number of key differences between the conditions satisfied by many political constitutions and the requirements for achieving the positive existence of a Bergson-Samuelson social welfare function. In particular the paper focusses here on the weighting systems on individual preferences that are consistent with generating an individualistic welfare function and examines the information content of individual ordinal preferences which must be utilized if the desired welfare function is to result.     

An impossibility result concerningn-person bargaining games

In this note we show that a solution proposed byRaiffa for two-person bargaining games, which has recently been axiomatized byKalai/Smorodinsky, does not generalize in a straightforward manner to generaln-person bargaining games. Specifically, the solution is not Pareto optimal on the class of alln-person bargaining games, and no solution which is can possess the other properties which characterizeRaiffa's solution in the two-person case.     

Perfect information stochastic games and related classes

Forn-person perfect information stochastic games and forn-person stochastic games with Additive Rewards and Additive Transitions (ARAT) we show the existence of pure limiting average equilibria. Using a similar approach we also derive the existence of limiting average ε-equilibria for two-person switching control stochastic games. The orderfield property holds for each of the classes mentioned, and algorithms to compute equilibria are pointed out.     

Special domains and nonmanipulability

We investigate domains on which a nonmanipulable, nondictatorial social choice function exists, having at least three distinct values. We do not make the assumptions of Kalai and Muller (1977). We classify all such 2-person functions on the domain which is the cyclic group Z_m. We show that for any domain containing Z_m, existence for 2 voters and existence for some n > 2 voters are equivalent. We show that for an n-person, onto, nonmanipulable social choice function F on Z_m, F(P₁, P₂,…, P_n) {x₁, x₂,…, x_n} always, x_i being the most preferred alternative under preference P_i. We show that no domain containing the dihedral group admits such a social choice function. We show that there exists a domain on which all k-tuples are free for arbitrarily large k, for which such a social choice function does exist.     

On infinite graphs with a specified number of colorings

In this paper we construct a planar graph of degree four which admits exactly N_u 3-colorings, we prove that such a graph must have degree at least four, and we consider various generalizations. We first allow our graph to have either one or two vertices of infinite degree and/or to admit only finitely many colorings and we note how this effects the degrees of the remaining vertices. We next consider n-colorings for n>3, and we construct graphs which we conjecture (but cannot prove) are of minimal degree. Finally, we consider nondenumerable graphs, and for every 3 <n<ω and every infinite cardinal k we construct a graph of cardinality k which admits exactly kn-colorings. We also show that the number of n-colorings of a denumerable graph can never be strictly between N_u and 2^N_u and that an appropriate generalization holds for at least certain nondenumerable graphs.     

Upper Semicontinuity of Morse Sets of a Discretization of a Delay-Differential Equation: An Improvement

In this paper, we consider a discrete delay problem with negative feedback x(t)=f(x(t), x(t−1)) along with a certain family of time discretizations with stepsize 1/n. In the original problem, the attractor admits a nice Morse decomposition. We proved in (T. Gedeon and G. Hines, 1999, J. Differential Equations151, 36-78) that the discretized problems have global attractors. It was proved in (T. Gedeon and K. Mischaikow, 1995, J. Dynam. Differential Equations7, 141-190) that such attractors also admit Morse decompositions. In (T. Gedeon and G. Hines, 1999, J. Differential Equations151, 36-78) we proved certain continuity results about the individual Morse sets, including that if f(x, y)=f(y), then the individual Morse sets are upper semicontinuous at n=∞. In this paper we extend this result to the general case; that is, we prove for general f(x, y) with negative feedback that the Morse sets are upper semicontinuous.     

An associated maximization problem for two-person nonzero-sum separable games

It has been shown that two-person zero-sum separable games are associated with a maximization problem involving the cones and dual cones of the generalized moments of the players' mixed strategy sets. In this note it is observed that those results extend almost immediately to two-person nonzero-sum separable games, but that then-person extension does not follow except in a special case.     

Hypercyclic subspaces for Fréchet space operators

A continuous linear operator is hypercyclic if there is an x∈X such that the orbit {Tnx} is dense, and such a vector x is said to be hypercyclic for T. Recent progress show that it is possible to characterize Banach space operators that have a hypercyclic subspace, i.e., an infinite dimensional closed subspace H⊆X of, except for zero, hypercyclic vectors. The following is known to hold: A Banach space operator T has a hypercyclic subspace if there is a sequence (ni) and an infinite dimensional closed subspace E⊆X such that T is hereditarily hypercyclic for (ni) and Tni→0 pointwise on E. In this note we extend this result to the setting of Fréchet spaces that admit a continuous norm, and study some applications for important function spaces. As an application we also prove that any infinite dimensional separable Fréchet space with a continuous norm admits an operator with a hypercyclic subspace.     

Metric n-Lie Algebras

An n-Lie algebra is said to be metric if it is endowed with an invariant, non-degenerate, symmetric bilinear form. We prove that any simple n-Lie algebra over an algebraically closed field of characteristic zero admits a unique metric structure and vice versa. Further, we present two metric n-Lie algebras, which are indecomposable but admit many more metric structures.     

Constrainedn-person games

The usual properties of a characteristic function game were derived byvon Neumann andMorgenstern from the properties of a game in normal form. In this paper we give a linear programming principle for the calculation of the characteristic function. The principle is a direct application ofCharnes' linear programming method for the calculation of the optimal strategies and the value of a two-person zero-sum game. The linear programming principle gives another method for proving the standard properties of a characteristic function when it is derived from a game in normal form. Using an idea originated byCharnes for two person games, we develop the concept of a constrainedn-person game as a simple, practical extension of ann-person game. However the characteristic function for a constrainedn-person game may not satisfy properties, such as superadditivity, usually associated with a characteristic function.     

Embedding Certain Infinitely Connected Subsets of Bordered Riemann Surfaces Properly into ℂ2

We prove that certain infinitely connected domains D in a bordered Riemann surface, which admits a holomorphic embedding into C ², admit a proper holomorphic embedding into C ². We also prove that certain infinitely connected open subsets D⊂ℂ admit a proper holomorphic embedding into ℂ².      

A distributed social choice protocol for combinatorial domains

In this paper, we study the problem of collective decision-making over combinatorial domains, where the set of possible alternatives is a Cartesian product of (finite) domain values for each of a given set of variables, and these variables are not preferentially independent. Due to the large alternative space, most common rules for social choice cannot be directly applied to compute a winner. In this paper, we introduce a distributed protocol for collective decision-making in combinatorial domains, which enjoys the following desirable properties: (i) the final decision chosen is guaranteed to be a Smith member; (ii) it enables distributed decision-making and works under incomplete information settings, i.e., the agents are not required to reveal their preferences explicitly; (iii) it significantly reduces the amount of dominance testings (individual outcome comparisons) that each agent needs to conduct, as well as the number of pairwise comparisons; (iv) it is sufficiently general and does not restrict the choice of preference representation languages.     

Multivalued social choice functions and strategic manipulation with counterthreats

In this paper, we examine the manipulability properties of social decision rules which select a non-empty subset of the set of alternatives. Assuming that if an individual prefers x to y, then he prefers the outcome set {x, y} to {y}, and also {x} to {x, y}, we show that a wide class of scf's which allow ties even in pairwise choice violates one of the weakest notions of strategyproofness — a single individual can profitably misrepresent his preferences, even when he takes into account the possibility of countercoalitions. This class of scf's also violates exact consistency — no equilibrium situation gives the same outcome set as the ‘true profile’.     

阿罗不可能性定理的几个等价形式

在这篇短中。给出了关于社会福利函数F的防止策略性操纵的概念,并且证明了如果备选对象至少有三个。则下面结论是相互等价的：(1)F满足Pareto与IIA性质;(2)F满足Pareto与RID性质;(3)F是独裁的;(4)F是满的、正向响应的;(5)F是防止策略操纵的且F是满的。     

Symposium on combinatorial mathematics and optimal design

Let A₁,A₂,…,A_n be finite sets such that A_i?A_j for all i≠j. Let F be an intersecting family consisting of sets contained in some A_i, i=1,2,…,n. Chvátal conjectured that among the largest intersecting families, there is always a star. In this paper, we obtain another proof of a result of Schönheim: If A₁∩A₂∩?∩A_n≠?, then the conjecture is true. We also prove that if A_i∩A_jA_k = ? for all i≠j≠k≠i or if the independent system satisfies a hereditary tree structure, then the conjecture is also true.     

On the approximability of the minimum strictly fundamental cycle basis problem

We consider the problem of finding a strictly fundamental cycle basis of minimum weight in the cycle space associated with an undirected connected graph G, where a nonnegative weight is assigned to each edge of G and the total weight of a basis is defined as the sum of the weights of all the cycles in the basis. Several heuristics have been proposed to tackle this NP-hard problem, which has some interesting applications. In this paper we show that this problem is APX-hard, even when restricted to unweighted graphs, and hence does not admit a polynomial-time approximation scheme, unless P=NP. Using a recent result on the approximability of lower-stretch spanning trees (Elkin et al. (2005) [7]), we obtain that the problem is approximable within O(log²nloglogn) for arbitrary graphs. We obtain tighter approximability bounds for dense graphs. In particular, the problem restricted to complete graphs admits a polynomial-time approximation scheme.     

A Neo2 bayesian foundation of the maxmin value for two-person zero-sum games

A joint derivation of utility and value for two-person zero-sum games is obtained using a decision theoretic approach. Acts map states to consequences. The latter are lotteries over prizes, and the set of states is a product of two finite sets (m rows andn columns). Preferences over acts are complete, transitive, continuous, monotonie and certainty-independent (Gilboa and Schmeidler (1989)), and satisfy a new axiom which we introduce. These axioms are shown to characterize preferences such that (i) the induced preferences on consequences are represented by a von Neumann-Morgenstern utility function, and (ii) each act is ranked according to the maxmin value of the correspondingm × n utility matrix (viewed as a two-person zero-sum game). An alternative statement of the result deals simultaneously with all finite two-person zero-sum games in the framework of conditional acts and preferences.We are indebted to Jacques Drèze, Andreu Mas-Colell, Roger Myerson and Reinhard Selten for helpful comments.     

Foliations by stationary disks of almost complex domains

We study the problem of existence of stationary disks for domains in almost complex manifolds. As a consequence of our results, we prove that any almost complex domain which is a small deformation of a strictly linearly convex domain D⊂Cn with standard complex structure admits a singular foliation by stationary disks passing through any given internal point. Similar results are given for foliations by stationary disks through a given boundary point.     

Cycle systems without 2-colorings

In an m-cycle system C of order n the blocks are the vertex sets of n(n−1)/(2m) cycles C_i such that each edge of the complete graph K_n belongs to precisely one cycle C_i E C. We prove the existence of m-cycle systems that admit no vertex partition into two classes in such a way that each class meets every cycle of C. The proofs apply both constructive and probabilistic methods, and also some old and new facts about Steiner Triple Systems without large independent sets. © 1996 John Wiley & Sons, Inc.     

On finite simple groups acting on homology spheres

It is a consequence of the classical Jordan bound for finite subgroups of linear groups that in each dimension n there are only finitely many finite simple groups which admit a faithful, linear action on the n-sphere. In the present paper we prove an analogue for smooth actions on arbitrary homology n-spheres: in each dimension n there are only finitely many finite simple groups which admit a faithful, smooth action on some homology sphere of dimension n, and in particular on the n-sphere. We discuss also the finite simple groups which admit an action on a homology sphere of dimension 3, 4 or 5.