Permutations of separable preference orders

The notion of separability is important in economics, operations research, and political science, where it has recently been studied within the context of referendum elections. In a referendum election on n questions, a voter's preferences may be represented by a linear order on the 2ⁿ possible election outcomes. The symmetric group of degree 2ⁿ, S_2ⁿ, acts in a natural way on the set of all such linear orders. A permutation σ∈S_2ⁿ is said to preserve separability if for each separable order ?, σ(?) is also separable. Here, we show that the set of separability-preserving permutations is a subgroup of S_2ⁿ and, for 4 or more questions, is isomorphic to the Klein 4-group. Our results indicate that separable preferences are rare and highly sensitive to small changes. The techniques we use have applications to the problem of enumerating separable preference orders and to other broader combinatorial questions.     

Reasoning with various kinds of preferences: logic,non-monotonicity,and algorithms

As systems dealing with preferences become more sophisticated, it becomes essential to deal with various kinds of preference statements and their interaction. We introduce a non-monotonic logic distinguishing sixteen kinds of preferences, ranging from strict to loose and from careful to opportunistic, and two kinds of ways to deal with uncertainty, either optimistically or pessimistically. The classification of the various kinds of preferences is inspired by a hypothetical agent comparing the two alternatives of a preference statement. The optimistic and pessimistic way of dealing with uncertainty correspond on the one hand to considering either the best or the worst states in the comparison of the two alternatives of a preference statement, and on the other hand to the calculation of least or most specific “distinguished” preference orders from a set of preference statements. We show that each way to calculate distinguished preference orders is compatible with eight kinds of preferences, in the sense that it calculates a unique distinguished preference order for a set of such preference statements, and we provide efficient algorithms that calculate these unique distinguished preference orders. In general, optimistic kinds of preferences are compatible with optimism in calculating distinguished preference orders, and pessimistic kinds of preferences are compatible with pessimism in calculating distinguished preference orders. However, these two sets of eight kinds of preferences are not exclusive, such that some kinds of preferences can be used in both ways to calculate distinguished preference orders, and other kinds of preferences cannot be used in either of them. We also consider the merging of optimistically and pessimistically constructed distinguished preferences orders.     

NP-hardness results for the aggregation of linear orders into median orders

Given a collection Π of individual preferences defined on a same finite set of candidates, we consider the problem of aggregating them into a collective preference minimizing the number of disagreements with respect to Π and verifying some structural properties. We study the complexity of this problem when the individual preferences belong to any set containing linear orders and when the collective preference must verify different properties, for instance transitivity. We show that the considered aggregation problems are NP-hard for different types of collective preferences (including linear orders, acyclic relations, complete preorders, interval orders, semiorders, quasi-orders or weak orders), if the number of individual preferences is sufficiently large.     

Toward an arithmetic of polynomials

Summary ForR a commutative ring, which may have divisors of zero but which has no idempotents other than zero and one, we consider the problem of unique factorization of a polynomial with coefficients inR. We prove that, if the polynomial is separable, then such a unique factorization exists. We also define a Legendre symbol for a separable polynomial and a prime of commutative ring with exactly two idempotents in such a way that the symbols of classical number theory are subsumed. We calculate this symbol forR = Q in two cases where it has classically been of interest, namely quadratic extensions and cyclotomic extensions. We then calculate it in a situation which is new, namely the so called generalized cyclotomic extensions from a paper by S. Beale and D. K. Harrison. We study the Galois theory in the general ring situation and in particular define a category of separable polynomials (this is an extension of a paper by D. K. Harrison and M. Vitulli) and a cohomology theory of separable polynomials.     

Note on Morita Equivalence in Ring Extensions

It seems that Morita invariance judges of the importance of classes of ring extensions concerned. Miyashita introduced the notion of Morita equivalence in ring extensions, and he showed that the classes of G-Galois extensions and Frobenius extensions are Morita invariant. After that, Ikehata showed that the classes of separable extensions, Hirata separable extensions, symmetric extensions, and QF-extensions are Morita invariant. In this article, we shall prove that the classes of several extensions are Morita invariant. Further, we will give an example of the class of ring extensions which is not Morita invariant.     

A block coordinate gradient descent method for regularized convex separable optimization and covariance selection

We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem includes the covariance selection problem that can be expressed as an ℓ ₁-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated as BCGD) for solving this class of nonsmooth separable problems with the coordinate block chosen by a Gauss-Seidel rule. The method is simple, highly parallelizable, and suited for large-scale problems. We establish global convergence and, under a local Lipschizian error bound assumption, linear rate of convergence for this method. For the covariance selection problem, the method can terminate in O(n³/e){O(n^3/\epsilon)} iterations with an e{\epsilon}-optimal solution. We compare the performance of the BCGD method with the first-order methods proposed by Lu (SIAM J Optim 19:1807–1827, 2009; SIAM J Matrix Anal Appl 31:2000–2016, 2010) for solving the covariance selection problem on randomly generated instances. Our numerical experience suggests that the BCGD method can be efficient for large-scale covariance selection problems with constraints.     

Are Biseparable Extensions Frobenius?

In Secion 1 we describe what is known of the extent to which a separable extension of unital associative rings is a Frobenius extension. A problem of this kind is suggested by asking if three algebraic axioms for finite Jones index subfactors are dependent. In Section 2 the problem in the title is formulated in terms of separable bimodules. In Section 3 we specialize the problem to ring extensions, noting that a biseparable extension is a two-sided finitely generated projective, split, separable extension. Some reductions of the problem are discussed and solutions in special cases are provided. In Section 4 various examples are provided of projective separable extensions that are neither finitely generated nor Frobenius and which give obstructions to weakening the hypotheses of the question in the title. In Section 5 we show that characterizations of the separable extensions among Frobenius extensions are special cases of a result for adjoint functors. Mathematics Subject Classifications (2000): 16L60, 16H05.     

Cyclic conjugacy separability and conjugacy separability of certain HNN extensions

Abstract

In this note, we give a criterion for certain HNN extensions of cyclic conjugacy separable (respectively conjugacy separable) groups with infinite cyclic associated subgroups to be again cyclic conjugacy separable (respectively conjugacy separable).

Communicated by Alexander Olshanskii     

Uniqueness theorems of entire functions sharing a nonzero complex number with their difference operators

In this paper, we deal with a uniqueness question of entire functions sharing a nonzero complex number with their difference operators. The results in this paper improve Theorem 1.1 in Liu and Yang (Arch. Math. 92 (2009), 270–278) and deal with Question 1 in Liu and Yang (2009), where the entire functions are of finite orders.     

Up methods in the allocation of indivisibilities when preferences are single-peaked

We consider allocation problems with indivisible goods when agents’ preferences are single-peaked. We propose natural rules (called up methods) to solve such a class of problems and axiomatically characterize them. We also prove that these methods can be interpreted as extensions to the indivisible case of the so-called equal distance rule.      

Asymptotic expansions and convergence rates for Euler’s approximations of semigroups

We provide optimal bounds for errors in Euler’s approximations of semigroups in Banach algebras and of semigroups of operators in Banach spaces. Furthermore, we construct asymptotic expansions for such approximations with optimal bounds for remainder terms. The sizes of errors are controlled by smoothness properties of semigroups. In this paper we use Fourier–Laplace transforms and a reduction of the problem to the convergence rates and asymptotic expansions in the Law of Large Numbers. The research was partially supported by the Lithuanian State Science and Studies Foundation, grant No. T-70/09. This paper was written in 2004. In the interim, several related articles were published; let us mention [14, 13, 15].     

Weak Coupling Limit and Localized Oscillations in Euclidean Invariant Hamiltonian Systems

We prove the existence of time-periodic and spatially localized oscillations (discrete breathers) in a class of planar Euclidean-invariant Hamiltonian systems consisting of a finite number of interacting particles. This result is obtained in an “anticontinuous” limit, where atomic masses split into two groups that have different orders of magnitude (the mass ratio tending to infinity) and several degrees of freedom become weakly coupled. This kind of approach was introduced by MacKay and Aubry (Nonlinearity 7:1623–1643, 1994) (and further developed by Livi et al. in Nonlinearity 10:1421–1434, 1997) for one-dimensional Hamiltonian lattices. We extend their method to planar Euclidean-invariant systems and prove the existence of reversible discrete breathers in a general setting. In addition, we show the existence of nonlinear normal modes near the anticontinuous limit.      

An Ergodic Decomposition Defined by Transition Probabilities

Our main goal in this paper is to prove that any transition probability P on a locally compact separable metric space (X,d) defines a Kryloff-Bogoliouboff-Beboutoff-Yosida (KBBY) ergodic decomposition of the state space (X,d). Our results extend and strengthen the results of Chap. 5 of Hernández-Lerma and Lasserre (Markov Chains and Invariant Probabilities, [2003]) and extend our KBBY-decomposition for Markov-Feller operators that we have obtained in Chap. 2 of our monograph (Zaharopol in Invariant Probabilities of Markov-Feller Operators and Their Supports, [2005]). In order to deal with the decomposition that we present in this paper, we had to overcome the fact that the Lasota-Yorke lemma (Theorem 1.2.4 in our book (op. cit.)) and two results of Lasota and Myjak (Proposition 1.1.7 and Corollary 1.1.8 of our work (op. cit.)) are no longer true in general in the non-Feller case. In the paper, we also obtain a “formula” for the supports of elementary measures of a fairly general type. The result is new even for Markov-Feller operators. We conclude the paper with an outline of the KBBY decomposition for a fairly large class of transition functions. The results for transition functions and transition probabilities seem to us surprisingly similar. However, as expected, the arguments needed to prove the results for transition functions are significantly more involved and are not presented here. We plan to discuss the KBBY decomposition for transition functions with full details in a small monograph that we are currently trying to write. I am indebted to Sean Meyn for a discussion that we had in November 2004, which helped me to significantly improve the exposition in this paper, and to two anonymous referees for useful recommendations.     

On allocation of redundant components for systems with dependent components

In this paper we consider the problem of optimal allocation of a redundant component for series, parallel and k-out-of-n systems of more than two components, when all the components are dependent. We show that for this problem is naturally to consider multivariate extensions of the joint bivariates stochastic orders. However, these extensions have not been defined or explicitly studied in the literature, except the joint likelihood ratio order, which was introduced by Shanthikumar and Yao (1991). Therefore we provide first multivariate extensions of the joint stochastic, hazard rate, reversed hazard rate order and next we provide sufficient conditions based on these multivariate extensions to select which component performs the redundancy.     

$\mathcal{C}^{2}$ surface diffeomorphisms have symbolic extensions

We prove that C²\mathcal{C}^{2} surface diffeomorphisms have symbolic extensions, i.e. topological extensions which are subshifts over a finite alphabet. Following the strategy of Downarowicz and Maass (Invent. Math. 176:617–636, 2009) we bound the local entropy of ergodic measures in terms of Lyapunov exponents. This is done by reparametrizing Bowen balls by contracting maps in a approach combining hyperbolic theory and Yomdin’s theory.     

Ramsey Properties of Finite Posets

An important problem in topological dynamics is the calculation of the universal minimal flow of a topological group. When the universal minimal flow is one point, we say that the group is extremely amenable. For the automorphism group of Fra?ssé structures, this problem has been translated into a question about the Ramsey and ordering properties of certain classes of finite structures by Kechris et al. (Geom Funct Anal 15:106–189, 2005). Using the Schmerl list (Schmerl, Algebra Univers 9:317–321, 1979) of Fra?ssé posets, we consider classes of finite posets with arbitrary linear orderings and linear orderings that are linear extensions of the partial ordering. We provide classification of each of these classes according to their Ramsey and ordering properties. Additionally, we extend the list of extremely amenable groups as well as the list of metrizable universal minimal flows.     

A stability criterion

We come up with an independent proof for a corollary to the main theorem in [1]. This corollary is the degenerate case of the main theorem (with empty sets B ₀ and B ₁) and establishes a stability criterion for a Henselian valued field. Such a proof is given here based on an analysis of tame and purely wild extensions made in [2].     

Gaussian elements of a semicontent algebra

The connection between a univariate polynomial having locally principal content and the content function acting like a homomorphism (the so-called Gaussian property) has been explored by many authors. In this work, we extend several such results to the contexts of multivariate polynomials, power series over a Noetherian ring, and base change of affine K-algebras by separable algebraically closed field extensions. We do so by using the framework of the Ohm–Rush content function. The correspondence is particularly strong in cases where the base ring is approximately Gorenstein or the element of the target ring is regular.     

Additive habit formation: consumption in incomplete markets with random endowments

We provide a detailed characterization of the optimal consumption stream for the additive habit-forming utility maximization problem, in a framework of general discrete-time incomplete markets and random endowments. This characterization allows us to derive the monotonicity and concavity of the optimal consumption as a function of wealth, for several important classes of incomplete markets and preferences. These results yield a deeper understanding of the fine structure of the optimal consumption and provide a further theoretical support for the classical conjectures of Keynes (The general theory of employment, interest and money. Cambridge University Press, Cambridge, 1936).     

Counterexamples to a triality theorem in “Canonical dual least square method”

In this short note we give two counterexamples to the Triality Theorem concerning the optimization problem presented in Ruan et al., Comput. Optim. Appl. (2008). In order to understand the problem first we introduce the framework of this paper and quote the theorem we have in view. Then, while trying to verify this theorem we encounter several difficulties and note their nature. We end by revealing our counterexamples.