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’.     

On distribution of semiprime numbers

A semiprime is a natural number which is the product of two (possibly equal) prime numbers. Let y be a natural number and g(y) be the probability for a number y to be semiprime. In this paper we derive an asymptotic formula to count g(y) for large y and evaluate its correctness for different y. We also introduce strongly semiprimes, i.e., numbers each of which is a product of two primes of large dimension, and investigate distribution of strongly semiprimes.     

On iterative methods for solving equations with covering mappings

In this paper we propose an iterative method for solving the equation Υ(x, x) = y, where the mapping Υ acts in metric spaces and is covering in the first argument and Lipschitzian in the second one. Each subsequent element x _i+1 of the sequence of iterations is defined by the previous one as a solution to the equation Υ(x, x _i) = y _i, where y _i can be an arbitrary point sufficiently close to y. Conditions for convergence and error estimates are obtained. The method proposed is an iterative development of the Arutyunov method for finding coincidence points of mappings. In order to determine x _i+1 in practical implementation of the method in linear normed spaces, it is proposed to perform one step by using the Newton–Kantorovich method. The thus-obtained method of solving the equation of the form Υ(x, u) = ψ(x) ? φ(u) coincides with the iterative method proposed by A.I. Zinchenko,M.A. Krasnosel’skii, and I.A. Kusakin.     

Two finite embedding theorems for partial 3-quasigroups

In this paper it is shown that a finite partial (x, x, y) = y 3-quasigroup can be embedded in a finite (x, x, y) = y 3-quasigroup. This result coupled with the technique of proof is then used to show that a finite partial almost Steiner 3-quasigroup {(x, x, y) = y, (x, y, z) = (x, z, y) = (y, x, z)} can be embedded in a finite almost Steiner 3-quasigroup. Almost Steiner 3-quasigroups are of more than passing interest because just like Steiner 3-quasigroups ( = Steiner quadruple systems) all of their derived quasigroups are Steiner quasigroups.     

An optimal filtering method for stable analytic continuation

In this paper, we consider the problem of numerical analytic continuation of an analytic function f(z)=f(x+iy) on a strip domain Ω⁺={z=x+iy∈C∣x∈R,0<y<y₀}, where the data is given approximately only on the real axis y=0. This problem is severely ill-posed: the solution does not depend continuously on the given data. A novel method (filtering) is used to solve this problem and an optimal error estimate with Hölder type is proved. Numerical examples show that this method works effectively.     

On powersmooth numbers

A natural number n is called y-smooth (y-powersmooth, respectively) for a positive number y if every prime (prime power) dividing n is bounded from above by y. Let ψ(x, y) and ψ*(x, y) denote the quantity of y-smooth and y-powersmooth integers restricted by x, respectively. In this paper we investigate function ψ*(x, y) in general. We derive formulas for finding exact calculation of ψ*(x, y) for large x and relatively small y and give theoretical estimates for this function and for a function of the greatest powersmooth integer. This results can be used in the cryptography and number theory to estimate the convergence of factorization algorithms.     

One-step 9-stage Hermite–Birkhoff–Taylor ODE solver of order 10

A one-step 9-stage Hermite–Birkhoff–Taylor method of order 10, denoted by HBT(10)9, is constructed for solving nonstiff systems of first-order differential equations of the form y′=f(x,y), y(x ₀)=y ₀. The method uses y′ and higher derivatives y ⁽²⁾ to y ⁽⁴⁾ as in Taylor methods and is combined with a 9-stage Runge–Kutta method. Forcing a Taylor expansion of the numerical solution to agree with an expansion of the true solution leads to Taylor- and Runge–Kutta-type order conditions which are reorganized into Vandermonde-type linear systems whose solutions are the coefficients of the method. The new method has a larger scaled interval of absolute stability than Dormand–Prince DP(8,7)13M. The stepsize is controlled by means of y ⁽²⁾ and y ⁽⁴⁾. HBT(10)9 is superior to DP(8,7)13M and Taylor method of order 10 in solving several problems often used to test high-order ODE solvers on the basis of the number of steps, CPU time, and maximum global error. These numerical results show the benefits of adding high-order derivatives to Runge–Kutta methods.     

Latin square and intersection of surface

A technique is developed here to estimate an unknown curve joining two points in a three dimensional Euclidean space. A special application presented here is a computer procedure to determine the intersection of two arbitrary given smooth surfaces. The method used is to assume that y is a function of x and the set (x,y(x)) lies on the projection of the intersection of two surfaces. The function y is determined by least square curve fitting on a Latin square of experimental values. The procedure is written in APL (A Programming Language). A set of preliminary results is presented. The results indicate that this is a successful procedure for some simple surfaces, including some conic surfaces.     

A one-step 7-stage Hermite-Birkhoff-Taylor ODE solver of order 11

A one-step 7-stage Hermite-Birkhoff-Taylor method of order 11, denoted by HBT(11)7, is constructed for solving nonstiff first-order initial value problems y^′=f(t,y), y(t₀)=y₀. The method adds the derivatives y^′ to y⁽⁶⁾, used in Taylor methods, to a 7-stage Runge-Kutta method of order 6. Forcing an expansion of the numerical solution to agree with a Taylor expansion of the true solution to order 11 leads to Taylor- and Runge-Kutta-type order conditions. These conditions are reorganized into Vandermonde-type linear systems whose solutions are the coefficients of the method. The new method has a larger scaled interval of absolute stability than the Dormand-Prince DP87 and a larger unscaled interval of absolute stability than the Taylor method, T11, of order 11. HBT(11)7 is superior to DP87 and T11 in solving several problems often used to test higher-order ODE solvers on the basis of the number of steps, CPU time, and maximum global error. Numerical results show the benefit of adding high-order derivatives to Runge-Kutta methods.     

Ordinary differential equations invariant under translation in the independent variable and rescaling: The Lagrangian formulation

The Lagrangian formulation of the class of general second-order ordinary differential equations invariant under translation in the independent variable and rescaling is presented. The differential equations arising from this analysis are analysed using the Painlevé test. The well-known differential equation, y^″+yy^′+ky³=0, is a unique member of this class when k=3 since it is linearisable by a point transformation. A wider subset is shown to be linearisable by means of a nonlocal transformation.     

Computer Algebra and Bifurcations

In this paper we will present the family of Newton algorithms. From the computer algebra point of view, the most basic of them is well known for the local analysis of plane algebraic curves f(x,y)=0 and consists in expanding y as Puiseux series in the variable x. A similar algorithm has been developped for multi-variate algebraic equations and for linear differential equations, using the same basic tools: a “regular” case, associated with a “simple” class of solutions, and a “simple” method of calculus of these solutions; a Newton polygon; changes of variable of type ramification; changes of unknown function of two types y=ct ^μ+? or y=exp?(c/t ^μ)?. Our purpose is first to define a “regular” case for nonlinear implicit differential equations f(t,y,y′)=0. We will then apply the result to an explicit differential equation with a parameter y′=f(y,α) in order to make a link between the expansions of the solutions obtained by our local analysis and the classical theory of bifurcations.     

On the polynomial mixed 0–1 fractional programming problems

This paper proposes a new method of solving polynomial mixed 0–1 fractional programming (P01FP) problems to obtain a global optimum. Given a polynomial 0–1 term x₁x₂,…,x_ny, where x_i is a 0–1 variable and y is a continuous variable; we develop a linearization technique to transfer the x₁x₂,…,x_ny term into a set of mixed 0–1 linear inequalities. Based on this technique, the P01FP can then be solved by a branch-and-bound method to obtain the global solution.     

On convex quadratic programs with linear complementarity constraints

The paper shows that the global resolution of a general convex quadratic program with complementarity constraints (QPCC), possibly infeasible or unbounded, can be accomplished in finite time. The method constructs a minmax mixed integer formulation by introducing finitely many binary variables, one for each complementarity constraint. Based on the primal-dual relationship of a pair of convex quadratic programs and on a logical Benders scheme, an extreme ray/point generation procedure is developed, which relies on valid satisfiability constraints for the integer program. To improve this scheme, we propose a two-stage approach wherein the first stage solves the mixed integer quadratic program with pre-set upper bounds on the complementarity variables, and the second stage solves the program outside this bounded region by the Benders scheme. We report computational results with our method. We also investigate the addition of a penalty term y ^T Dw to the objective function, where y and w are the complementary variables and D is a nonnegative diagonal matrix. The matrix D can be chosen effectively by solving a semidefinite program, ensuring that the objective function remains convex. The addition of the penalty term can often reduce the overall runtime by at least 50 %. We report preliminary computational testing on a QP relaxation method which can be used to obtain better lower bounds from infeasible points; this method could be incorporated into a branching scheme. By combining the penalty method and the QP relaxation method, more than 90 % of the gap can be closed for some QPCC problems.     

More bounds for eigenvalues

A method introduced by Leighton [J. Math. Anal. Appl.35, 381–388 (1971)] for bounding eigenvalues has been extended to include problems of the form ?y″ + p(x) y = λy, when p(x) ? 0 on [0, 1]. The boundary conditions are the general homogeneous conditions y(0) ? ay′(0) = 0 = y(1) + by′(1), where 0 ? a, b ? ∞. Upper and lower bounds for the eigenvalues of these problems are obtained, and these bounds may be made as close together as desired, thereby allowing λ to be estimated precisely.     

One-step 5-stage Hermite-Birkhoff-Taylor ODE solver of order 12

A one-step 5-stage Hermite-Birkhoff-Taylor method, HBT(12)5, of order 12 is constructed for solving nonstiff systems of differential equations y^′=f(t,y), y(t₀)=y₀, where y∈Rⁿ. The method uses derivatives y^′ to y⁽⁹⁾ as in Taylor methods combined with a 5-stage Runge-Kutta method. Forcing an expansion of the numerical solution to agree with a Taylor expansion of the true solution to order 12 leads to Taylor- and Runge-Kutta-type order conditions which are reorganized into Vandermonde-type linear systems whose solutions are the coefficients of the method. HBT(12)5 has a larger interval of absolute stability than Dormand-Prince DP(8, 7)13M and Taylor method T12 of order 12. The new method has also a smaller norm of principal error term than T12. It is superior to DP(8, 7)13M and T12 on the basis the number of steps, CPU time and maximum global error on common test problems. The formulae of HBT(12)5 are listed in an appendix.     

A non-linear structure preserving matrix method for the low rank approximation of the Sylvester resultant matrix

A non-linear structure preserving matrix method for the computation of a structured low rank approximation of the Sylvester resultant matrix S(f,g) of two inexact polynomials f=f(y) and g=g(y) is considered in this paper. It is shown that considerably improved results are obtained when f(y) and g(y) are processed prior to the computation of , and that these preprocessing operations introduce two parameters. These parameters can either be held constant during the computation of , which leads to a linear structure preserving matrix method, or they can be incremented during the computation of , which leads to a non-linear structure preserving matrix method. It is shown that the non-linear method yields a better structured low rank approximation of S(f,g) and that the assignment of f(y) and g(y) is important because may be a good structured low rank approximation of S(f,g), but may be a poor structured low rank approximation of S(g,f) because its numerical rank is not defined. Examples that illustrate the differences between the linear and non-linear structure preserving matrix methods, and the importance of the assignment of f(y) and g(y), are shown.     

An inverse non-Fourier heat conduction problem approach for estimating the boundary condition in electronic device

This study is intended to provide an inverse method for estimating the unknown boundary condition T(0,y,t) in a non-Fourier heat conduction electronic device. In this study, finite-difference methods are employed to discretize the problem domain, and then a linear inverse model is constructed to identify the unknown boundary condition. The present approach is to rearrange the matrix forms of the differential governing equations and to estimate the unknown conditions. Then, the linear least-squares method is adopted to obtain the solution.The results show that one measuring point is sufficient to estimate the unknown boundary condition T(0,y,t) without measurement errors. When considering the measurement errors, the magnitudes of the discrepancies in the boundary condition T(0,y,t) are directly proportional to the size of measurement errors. Due to the complicated reflection and interaction of the thermal waves, this phenomenon reflects the fact that the inverse non-Fourier heat conduction problem is different from the inverse Fourier heat conduction problem.In contrast to the traditional approach, the advantage of applying this method in inverse analysis is that no prior information is needed on the functional form of the unknown quantities. In addition, no initial guess is required and the calculation can be done in only one iteration.     

Hamming distance for conjugates

Let x,y be strings of equal length. The Hamming distanceh(x,y) between x and y is the number of positions in which x and y differ. If x is a cyclic shift of y, we say x and y are conjugates. We consider f(x,y), the Hamming distance between the conjugates xy and yx. Over a binary alphabet f(x,y) is always even, and must satisfy a further technical condition. By contrast, over an alphabet of size 3 or greater, f(x,y) can take any value between 0 and |x|+|y|, except 1; furthermore, we can always assume that the smaller string has only one type of letter.     

Parametric scaling of mathematical models

Parametric scaling, the process of extrapolation of a modelling result to new parametric conditions, is often required in model optimization, and can be important if the effects of parametric uncertainty on model predictions are to be quantified. Knowledge of the functional relationship between the model solution (y) and the system parameters (α) may also provide insight into the physical system underlying the model. This paper examines strategies for parametric scaling, assuming that only the nominal model solution y(α) and the associated parametric sensitivity coefficients (?y/?α, ?²y/?α², etc.) are known. The truncated Taylor series is shown to be a poor choice for parametric scaling, when y has known bounds. Alternate formulae are proposed which ‘build-in’ the constraints on y, thus expanding the parametric region in which the extrapolation may be valid. In the case where y has a temporal as well as a parametric dependence, the extrapolation may be further improved by removing from the Taylor series coefficients the ‘secular’ components, which refer to changes in the time scale of y(t), not to changes in y as a function of α.     

On a quasi-reversibility regularization method for a Cauchy problem of the Helmholtz equation

In this paper, we consider the Cauchy problem for the Helmholtz equation in a rectangle, where the Cauchy data is given for y=0 and boundary data are for x=0 and x=π. The solution is sought in the interval 0<y≤1. A quasi-reversibility method is applied to formulate regularized solutions which are stably convergent to the exact one with explicit error estimates.