Расшифровка сигналов с помощью конечных автоматов: применение к играм с неполной информацией
Matrix games with incomplete information on both sides and public signal on the state of game represented by random binary code of fixed length are considered. Players are computationally bounded and are only able to play strategies to finite automata of different sizes: m for Player 1 and n for Player 2 where m ≫ n. We obtain a lower bound for m and an upper bound for n which may turn the original game with incomplete information for both players into a game with incomplete information for Player 2.
For matrix games we study how small nonzero probability must be used in optimal strategies. We show that for n×n win–lose–draw games (i.e. (−1,0,1) matrix games) nonzero probabilities smaller than n−O(n)are never needed. We also construct an explicit n×n win–lose game such that the unique optimal strategy uses a nonzero probability as small as n−Ω(n). This is done by constructing an explicit (−1,1)nonsingular n×n matrix, for which the inverse has only nonnegative entries and where some of the entries are of value nΩ(n).
The idea of ligalization of bribe giving for certain types of bribes was expressed by K. Basu in 2011 and got a name Basu proposal. In this paper we discuss effects that can be caused by the direct implementation of this proposal. Our game-theoretic model shows that while legalisation of certain bribe-giving occurances can lead to some positive consequences, it is not always a good idea to return bribe to the bribe-giver as suggested by Basu. The chance to get the paid bribe back increases the amount of bribes that end up in corrupt officials' pockets.
Supposing that Player 1’s computational power is higher than that of Player 2, we give three examples of different kinds of public signal about the state of a two-person zero-sum game with symmetric incom- plete information on both sides (both players do not know the state of the game) where Player 1 due to his computational power learns the state of the game meanwhile it is impossible for Player 2. That is, the game with incomplete information on both sides becomes a game with incomplete information on the side of Player 2. Thus we demonstrate that information about the state of a game may appear not only due to a private signal but as a result of a public signal and asymmetric computational resources of players.
This article deals with application of the Capital Asset Pricing Model and its drawbacks on the Ukrainian equity market. In this paper efficiency of the CAPM in the domestic conditions is identified; alternative models are proposed.
Separating codes have been used in many areas as diverse as automata synthesis, technical diagnosis and traitor tracing schemes. In this paper, we study a weak version of separating codes called almost separating codes. More precisely, we derive lower bounds on the rate of almost separating codes. From the main result it is seen that the lower bounds on the rate for almost separating codes are greater than the currently known lower bounds for ordinary separating codes. Moreover, we also show how almost separating codes can be used to construct a family of fingerprinting codes.
Formal Concept Analysis Research Toolbox (FCART) is an integrated environment for knowledge and data engineers with a set of research tools based on Formal Concept Analysis (FCA). In the paper we consider main FCA workflow and some applications in the field of the text pattern matching.
Let k be a field of characteristic zero, let G be a connected reductive algebraic group over k and let g be its Lie algebra. Let k(G), respectively, k(g), be the field of k- rational functions on G, respectively, g. The conjugation action of G on itself induces the adjoint action of G on g. We investigate the question whether or not the field extensions k(G)/k(G)^G and k(g)/k(g)^G are purely transcendental. We show that the answer is the same for k(G)/k(G)^G and k(g)/k(g)^G, and reduce the problem to the case where G is simple. For simple groups we show that the answer is positive if G is split of type A_n or C_n, and negative for groups of other types, except possibly G_2. A key ingredient in the proof of the negative result is a recent formula for the unramified Brauer group of a homogeneous space with connected stabilizers. As a byproduct of our investigation we give an affirmative answer to a question of Grothendieck about the existence of a rational section of the categorical quotient morphism for the conjugating action of G on itself.
Let G be a connected semisimple algebraic group over an algebraically closed field k. In 1965 Steinberg proved that if G is simply connected, then in G there exists a closed irreducible cross-section of the set of closures of regular conjugacy classes. We prove that in arbitrary G such a cross-section exists if and only if the universal covering isogeny Ĝ → G is bijective; this answers Grothendieck's question cited in the epigraph. In particular, for char k = 0, the converse to Steinberg's theorem holds. The existence of a cross-section in G implies, at least for char k = 0, that the algebra k[G]G of class functions on G is generated by rk G elements. We describe, for arbitrary G, a minimal generating set of k[G]G and that of the representation ring of G and answer two Grothendieck's questions on constructing generating sets of k[G]G. We prove the existence of a rational (i.e., local) section of the quotient morphism for arbitrary G and the existence of a rational cross-section in G (for char k = 0, this has been proved earlier); this answers the other question cited in the epigraph. We also prove that the existence of a rational section is equivalent to the existence of a rational W-equivariant map T- - - >G/T where T is a maximal torus of G and W the Weyl group.