The generation of clones with majority operations

A theorem by Baker and Pixley implies that any clone on a finite set is finitely generated if it contains a near-unanimity operation. This raises the question of what arity the generating operations must have. In this paper, we solve the last open bits of this problem for the majority case by showing that 5 and 8 are the smallest integers k such that every clone with a majority operation on a 3 and 4-element set, respectively, is generated by its k-ary part.     

On clones generated by primitive-positive operations of Tarski's relation algebras

Received November 29, 1996; accepted in final form September 5, 1997.     

On signed majority total domination in graphs

We initiate the study of signed majority total domination in graphs. Let G = (V, E) be a simple graph. For any real valued function f: V and S V, let . A signed majority total dominating function is a function f: V {–1, 1} such that f(N(v)) 1 for at least a half of the vertices v V. The signed majority total domination number of a graph G is = min{f(V): f is a signed majority total dominating function on G}. We research some properties of the signed majority total domination number of a graph G and obtain a few lower bounds of .This research was supported by National Natural Science Foundation of China.     

On Boolean primitive positive clones

Kuznecov introduced the concept of primitive positive clones and proved in 1977 that there are 25 Boolean primitive positive clones in a notoriously unavailable article. This paper presents a new proof of his result, relating it to Post's lattice and exhibiting finite bases for those clones.     

Strict majority functions on graphs

An opinion function on a graph G = (V, E) is a function f: V → {−1, +1}. The vote of a vertex v is the sum of these function values over the closed neighborhood of v. A strict majority function on a graph G is an opinion function for which more than half of the vertices have a positive vote. The strict majority number of G is the minimum sum of the values in a strict majority function of G. We prove the conjecture of Cockayne and Mynhardt (Ars. Combin. 43 (1996), 235–245) that every tree has strict majority number at most 2. We also prove that every graph has strict majority number at most 4. Both bounds are sharp. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 49–56, 1998     

A method for aggregating ordinal assessments by a majority decision rule

A new method for aggregating ordinal assessments of individuals is proposed to obtain a collective preference ordering of alternatives. The method converts the ordinal assessments to collective pairwise comparisons of the alternatives and incorporates a deduction process to yield transitively consistent pairwise comparisons with respect to majority principle, and hence yields a linear order of the alternatives. Its algorithm is presented and its properties are studied. The method is applied to an opinion survey concerning quality of life, and a collective ordering of items pertaining to the quality of life is obtained with respect to their importance.     

Separation of clones of cooperations by cohyperidentities

An n-ary cooperation is a mapping from a nonempty set A to the nth copower of A. A clone of cooperations is a set of cooperations which is closed under superposition and contains all injections. Coalgebras are pairs consisting of a set and a set of cooperations defined on this set. We define terms for coalgebras, coidentities and cohyperidentities. These concepts will be applied to give a new solution of the completeness problem for clones of cooperations defined on a two-element set and to separate clones of cooperations by coidentities.     

An axiomatic characterization of different majority concepts

A lot of decision support systems use some kind of aggregation procedure based on the concept of majority, but not always the same one; it can be simple majority, weak majority or one of the many other kinds of majority. This paper attempts to present the main variants of majority and to characterize them in a uniform way. Consequently, it is now easier to compare different kinds of majority and to understand the dissimilarities (or similarities) between them. This should help decision analysts willing to use a majority procedure to choose the right one for their problem and context.     

Some universal properties of the category of clones

In [6], O. C. García and W. Taylor asked if the breadth of the lattice of interpretability types of varieties is uncountable. The present paper solves the problem by two different constructions. Both of them show that any cardinal number is the cardinality of an antichain in the named lattice and that the existence of a proper class antichain is equivalent to the negation of Vopěnka's principle. The first construction gives in a way a minimal solution of the problem, whereas the second one gives stronger results about the category of clones. Received November 12, 1999; accepted in final form June 19, 2001.     

Different ways to represent weighted majority games

It is well known that every simple game is the intersection of weighted majority games. the aim of this paper is to gather together various ways of expressing weighted majority games and, for each game of this type, to give the simplest way to define it. Normalized representations, the parameters of a simple game and the characteristic invariants of a complete game merit special attention. Research partially supported by projects PR9509 of the Polytechnic University of Catalonia and PB96-0493 of DGES     

Improved bounds for the randomized decision tree Complexity of recursive majority

We consider the randomized decision tree complexity of the recursive 3‐majority function. We prove a lower bound of for the two‐sided‐error randomized decision tree complexity of evaluating height h formulae with error . This improves the lower bound of given by Jayram, Kumar, and Sivakumar (STOC'03), and the one of given by Leonardos (ICALP'13). Second, we improve the upper bound by giving a new zero‐error randomized decision tree algorithm that has complexity at most . The previous best known algorithm achieved complexity . The new lower bound follows from a better analysis of the base case of the recursion of Jayram et al. The new algorithm uses a novel “interleaving” of two recursive algorithms. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 612–638, 2016     

Voting power in a system of compound majority rule

In 1973, the United States Supreme Court ruled that a water district's voting scheme that apportioned votes on the basis of the assessed valuation of acreage in the district was constitutional. Among the justifications for the constitutionality of this scheme was the concurrent requirement that legislation be approved by a majority of voters as well as by a majority of weighted votes. However, analysis of this voting scheme in game-theoretic terms indicates that this justification is only partial: when two sets of winning coalitions must form simultaneously in order to pass legislation, the voting power of each voter in the combined system equals the mean of the voting power afforded each voter in each simple system. The results can be generalized to three or more concurrent requirements.     

Simple majority voting isn't special

Simple majority voting is compared with several other representative voting systems with respect to the frequency with which various anomalies occur. Whether strong or weak preferences are used, for each anomaly type simple majority voting yields neither highest nor lowest frequencies.     

Symmetric operations in algebraic cobordism

In this article we describe certain new cohomological operations in algebraic cobordisms. These operations give the natural obstructions for the cobordism class to be represented by the embedding. Also, they permit to work with algebraic cobordisms and Chow groups in a more subtle way than the Landweber-Novikov operations (related to 2-torsion effects). We describe applications to the computation of the algebraic cobordisms of a Pfister quadrics and to the problem of rationality of cycles.     

A maximal clone of monotone operations which is not finitely generated

There is only one maximal clone on a set of at most eight elements which has not been known to be finitely generated. We show that it is not finitely generated.     

The capacity of majority rule

Let 𝔹ⁿ={−1, 1}ⁿ denote the vertices of the n-dimensional cube. Let U(m) be a random m-element subset of 𝔹ⁿ and suppose w ∈𝔹ⁿ is a vertex closest to the centroid of U(m). Using a large deviation, multivariate local limit theorem due to Richter, we show that n/π log n is a threshold function for the property that the convex hull of U(m) is contained in the positive half-space determined by w . The decision problem considered here is an instance of binary integer programming, and the algorithm selecting w as the vertex closest to the centroid of U(m) has been previously dubbed majority rule in the context of learning binary weights for a perceptron. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 83–109, 1998     

M-solid varieties generated by lattices

Following W. Taylor, we define an identity to be hypersatisfied by a variety V iff, whenever the operation symbols of V are replaced by arbitrary terms (of appropriate arity) in the operations of V, then the resulting identity is satisfied by V in the usual sense. Whenever the identity is hypersatisfied by a variety V, we shall say that is a hyperidentity of V, or a V hyperidentity. When the terms being substituted are restricted to a submonoid M of all the possible choices, is called an M-hyperidentity, and a variety V is M-solid if each identity is an M-hyperidentity. In this paper we examine the solid varieties whose identities are lattice M-hyperidentities. The M-solid varieties generated by the variety of lattices in this way provide new insight on the construction and representation of various known classes of non-commutative lattices. Received October 8, 1999; accepted in final form March 22, 2000.     

Minimal clones—a minicourse

This paper provides an elementary introduction to minimal clones, as well as a survey of recent trends and results. Received September 27, 2002; accepted in final form October 10, 2002.     

Minimal distortion morphs generated by time-dependent vector fields

A morph between two Riemannian n-manifolds is an isotopy between them together with the set of all intermediate manifolds equipped with Riemannian metrics. We propose measures of the distortion produced by some classes of morphs and diffeomorphisms between two isotopic Riemannian n-manifolds and, with respect to these classes, prove the existence of minimal distortion morphs and diffeomorphisms. In particular, we consider the class of time-dependent vector fields (on an open subset Ω of Rn+1 in which the manifolds are embedded) that generate morphs between two manifolds M and N via an evolution equation, define the bending and the morphing distortion energies for these morphs, and prove the existence of minimizers of the corresponding functionals in the set of time-dependent vector fields that generate morphs between M and N and are L² functions from [0,1] to the Sobolev space .