On effectively computable realizations of choice functions: Dedicated to Professors Kenneth J. Arrow and Anil Nerode

Let X be a compact, convex subset of R_n, and let $\text{〈R(X),}\text{F}{}_{\mathrm{R}}\text{〉}$ be a recursive space of alternatives, where R(X) is the image of X in a recursive metric space, and $\text{F}{}_{\mathrm{R}}$ is the family of all recursive subsets of R(X). If $\text{C:}\text{F}{}_{\mathrm{R}}\text{→}\text{F}{}_{\mathrm{R}}$ is a non-trivial recursively representable choice function that is rational in the sense of Richter, we prove that C has no recursive realization within Church's Thesis. Our proof is not a diagonalization argument and uses no paradoxical statements from formal systems. Instead, the proof is a Kleene-Post reduction style argument and uses the Turing equivalence between mechanical devices of computation and the recursive functions of Gödel and Kleene.     

Random utility models with all choice probabilities expressible as ‘functions’ of the binary choice probabilities

Given the absence of non-trivial decision rules which are strategy-proof in the Gibbard-Satterthwaite sense, Peleg and Sen have suggested that one might search for decision rules under which there will be always some Nash equilibrium yielding the same outcome as would be yielded by honest voting. This paper shows that most decision rules based on pairwise comparison will fail to satisfy the requirement of Peleg and Sen if one imposes the additional condition that the relevant Nash equilibrium should consist of undominated voting strategies only (a most reasonable condition in the absence of cooperation). It is also shown that under most decision rules based on pairwise comparisons, it will not be possible either to ensure that the outcome of honest voting will be always an outcome of sophisticated voting (in Farquharson's sense) or to ensure that the outcome of honest voting will be always a core outcome.     

Complexity properties of recursively enumerable sets andbsQ-completeness

The notions of boundedly strongly effectively speedable set and boundedly effectively speedable set are introduced. It is proved that the notions of boundedly strongly effectively speedable set, boundedly effectively speedable set, creative set, andbsQ-complete recursively enumerable set are equivalent. Translated fromMatematicheskie Zametki, Vol. 68, No. 4, pp. 554–559, October, 2000.     

Restricted domains,arrow-social welfare functions and noncorruptible and non-manipulable social choice correspondences: The case of private alternatives

An n-person social choice problem is considered in which the alternatives are n dimensional vectors, with the ith component of such a vector being the part of the alternatives affecting individual i alone. Assuming that individuals are selfish (individual i must be indifferent between any two alternatives with the same components), that they may be indifferent among alternatives and that each individual may choose his preferences out of a different set of permissible preferences, we prove that any set of restricted domains of preferences admits an n person non-dictatorial Arrow-type social welfare function if and only if it admits a two-person Arrow-type social welfare function: we characterize all the sets of restricted domains of preferences which admit two-person Arrow-type social welfare functions (and therefore also admit n-person Arrow-type social welfare functions) and then we prove that we also characterized all the sets of restricted domains of preferences which admit nondictatorial, nonmanipulable, noncorruptible and rational social choice correspondences.     

Mapping properties of the zero-balanced hypergeometric functions

In this paper, the order of convexity of $z_2{F}_1(a,b;c;z)$ is given under certain conditions on the positive real parameters a, b and c. We show also that the image domains of the unit disc $\mathbb{D}$ under some shifted zero-balanced hypergeometric functions $z_2{F}_1(a,b;a+b;z)$ are convex and bounded by two horizontal lines. This solves a problem raised by Ponnusamy and Vuorinen in [10].     

Calculating the derivative of piecewise functions

Exercises involving the calculation of the derivative of piecewise defined functions are common in calculus, with the aim of consolidating beginners’ knowledge of applying the definition of the derivative. In such exercises, the piecewise function is commonly made up of two smooth pieces joined together at one point. A strategy which avoids using the definition of the derivative is to find the derivative function of each smooth piece and check whether these functions agree at the chosen point. Showing that this strategy works together with investigating discontinuities of the derivative is usually beyond a calculus course. However, we shall show that elementary arguments can be used to clarify the calculation and behaviour of the derivative for piecewise functions.     

The Generalization Paradox of Ensembles

Deconvolution is usually regarded as one of the ill-posed problems in applied mathematics if no constraints on the unknowns are assumed. This article discusses the idea of well-defined statistical models being a counterpart of the notion of well-posedness. We show that constraints on the unknowns such as positivity and sparsity can go a long way towards overcoming the ill-posedness in deconvolution. We show how these issues are dealt with in a parametric deconvolution model introduced recently. From the same perspective we take a fresh look at two familiar deconvolvers: the widely used Jansson method and another one that minimizes the Kullback-Leibler divergence between observations and fitted values. In the latter case, we point out that in the context of deconvolution and the general linear inverse problems with positivity contraints, a counterpart of the EM algorithm exists for the problem of minimizing the Kullback-Leibler divergence. We graphically compare the performance of these deconvolvers using data simulated from a spike-convolution model and DNA sequencing data.     

The connectivity and minimum degree of circuit graphs of matroids

Let G be the circuit graph of any connected matroid M with minimum degree 5（G）. It is proved that its connectivity κ（G） ≥2｜E（M） - B（M）｜ - 2. Therefore 5（G） ≥ 2｜E（M） - B（M）｜ - 2 and this bound is the best possible in some sense.     

Post's Problem for Reducibilities of Bounded Complexity

In this paper we consider the we known method by E. Post of solving the problem of construction of recursively enumerable sets that have a degree intermediate between the degrees of recursive and complete sets with respect to a given reducibility. Post considered reducibilities ≤_m, ≤_btt, ≤_tt and ≤_T and solved the problem for al of them except ≤_T. Here we extend Post's original method of construction of incomplete sets onto two wide classes of sub‐Turing reducibilities what were studying in [1, 2].     

On the lower bound for a class of harmonic functions in the half space

The main objective is to derive a lower bound from an upper one for harmonic functions in the half space, which extends a result of B. Y. Levin from dimension 2 to dimension n ≥ 2. To this end, we first generalize the Carleman's formula for harmonic functions in the half plane to higher dimensional half space, and then establish a Nevanlinna's representation for harmonic functions in the half sphere by using Hörmander's theorem.     

Alternative proofs for inequalities of some trigonometric functions

By using an identity relating to Bernoulli's numbers and power series expansions of cotangent function and logarithms of functions involving sine function, cosine function and tangent function, four inequalities involving cotangent function, sine function, secant function and tangent function are established.     

Realization ofk-valued functions by circuits of functional elements

The realization of functions fromP _k by circuits of functional elements in arbitrary bases is studied. Translated fromMatematicheskie Zametki, Vol. 64, No. 3, pp. 431–436, September, 1998.     

On Riemann surfaces of analytic eigenvalue functions

If y(t)=y(t;μ ,λ) is the solution of the differential equation y”+(λ +μ w(t))y=0, a≤ t≤ b, determined by the initial conditions y(a)=0, y’(a)=1, then F(μ ,λ) =y(b;μ ,λ) is an entire function of two variables. The zeros of F are the eigenpairs of a two-parameter Sturm–Liouville problem. The multi-valued solution λ (μ) of F(μ ,λ) =0 is introduced, and the connectedness of its underlying Riemann surface is investigated. The results are extensions of those previously obtained by Schäfke. As an example, the Lamé equation is considered.     

The products of three theta functions and the general cubic theta functions

In this paper we establish two theta function identities with four parameters by the theory of theta functions. Using these identities we introduce common generalizations of Hirschhorn-Garvan-Borwein cubic theta functions, and also re-derive the quintuple product identity, one of Ramanujan＇s identities, Winquist＇s identity and many other interesting identities.     

Geometrical embeddings of distributions into algebras of generalized functions

We use spectral theory to produce embeddings of distributions into algebras of generalized functions on a closed (compact without boundary) Riemannian manifold. These embeddings are invariant under isometries and preserve the singularity structure of the distributions (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)