Vol 77, No 3 (2016)

In situations when a group of people has to make a decision based on the set of individual preferences, they use a certain aggregation method, in particular, voting. One of the main problems for any non-dictatorial social choice rule is the possibility for the voters to achieve a more preferable outcome of the voting by misrepresenting their preferences. Such actions on behalf of the voters are called manipulation, or strategic voting. One approach used to compare social choice rules in terms of how hard they are to manipulate is to find the complexity classes of manipulation problems for a given aggregation method. In this work, we present a survey of the studies of complexity classes of manipulation problems under various model assumptions and constraints.

For the linear continuous nonstationary plants whose states are measured at fixed time instants, the notion of perturbation damping level was introduced as an index of joint impact of the initial and external perturbations on the worst-case objective output and terminal state. The H_∞-optimal laws of control were formulated as the state feedbacks minimizing the level of feedback damping of the closed-loop system.

Consideration was given to stabilization of the program motion of a holonomic mechanical system. A methodology of designing a nonlinear control stabilizing the given set of program motions was proposed. It relies on the Lyapunov vector function and a comparison system which enables one to control the stabilization process. At that, the generated control is robust in variations of the system parameters and allows for the uncontrollable forces.

We study the recognition problem for composite objects based on a probabilistic model of a piecewise regular object with thousands of alternative classes. Using the model’s asymptotic properties, we develop a new maximal likelihood enumeration method which is optimal (in the sense of choosing the most likely reference for testing on every step) in the class of “greedy” algorithms of approximate nearest neighbor search. We show experimental results for the face recognition problem on the FERET dataset. We demonstrate that the proposed approach lets us reduce decision making time by several times not only compared to exhaustive search but also compared to known approximate nearest neighbors techniques.

A stochastic problem of facility location formulated as a discrete bilevel problem of stochastic programming with quantile criterion was proposed. Consideration was given there to a pair of competitive players successively locating facilities with the aim of maximizing their profits. For the case of discrete distribution of the random consumer demands, it was proposed to reduce the original problem to the deterministic problem of bilevel programming. A method to calculate the value of the objective function under fixed leader strategy and procedures to construct the upper and lower bounds of the optimal value of the objective function were proposed.

We propose a mathematical formalism to define a system hierarchy and choose a way to reconfigure it based on multi-valued logic. We consider an application of this formalism to control over a group surveying the danger zone after a natural disaster.

We solve the problem of constructing extended finite state machines with execution scenarios and temporal formulas. We propose a new algorithm pstMuACO that combines a scenario filtering procedure, an exact algorithm efsmSAT for constructing finite state machines from execution scenarios based on a reduction to the Boolean satisfiability problem, and a parallel ant colony algorithm pMuACO. Experiments show that constructing several initial solutions for the ant colony algorithm with reduced sets of scenarios significantly reduces the total time needed to find optimal solutions. The proposed algorithm can be used for automated construction of reliable control systems.

An approach was developed to estimate the values of diagnosability of digital systems with the novel structure of the minimal quasicomplete 7 × 7 graph. The proposed estimates of the values of diagnosability of the digital systems under consideration were established as the result of diagnosis of fault situations in a system of 7 users and 7 switches. Consideration was given to two variants of organization of the components of the analyzed digital system for which different estimates of diagnosability were established.

We present two generalizations of the concept of equilibrium in secure strategies. In equilibrium contained by counter-threats (ECCT), no player can increase its payoff by a unilateral deviation without creating a threat to lose more than it wins. This condition must be satisfied for any pseudo-equilibrium in the generalized sense and, therefore, any such equilibrium must belong to the set of ECCT. The second generalization is the complex equilibrium in secure strategies. The proposed concept allows identifying a hierarchical structure of mutual threats between players and will be useful for the analysis of problems with asymmetric behavior of players. Search algorithms for the proposed equilibria and their examples in matrix games are provided.

We suggest a new method for designing direct switching connections between a large number of digital message sources and receivers. Conflicts at receiver input have fast resolution. Elimination of connection refusals is hardware-efficient. And finally, we demonstrate that the scheme of direct switching connections can be implemented by virtue of optoelectronic devices.