共查询到20条相似文献,搜索用时 187 毫秒
1.
Let gzs(m, 2k) (gzs(m, 2k+1)) be the minimal integer such that for any coloring Δ of the integers from 1, . . . , gzs(m, 2k) by (the integers from 1 to gzs(m, 2k+1) by ) there exist integers
such that
1. there exists jx such that Δ(xi) ∈ for each i and ∑i=1m Δ(xi) = 0 mod m (or Δ(xi)=∞ for each i);
2. there exists jy such that Δ(yi) ∈ for each i and ∑i=1m Δ(yi) = 0 mod m (or Δ(yi)=∞ for each i); and
1. 2(xm−x1)≤ym−x1.
In this note we show gzs(m, 2)=5m−4 for m≥2, gzs(m, 3)=7m+−6 for m≥4, gzs(m, 4)=10m−9 for m≥3, and gzs(m, 5)=13m−2 for m≥2.
Supported by NSF grant DMS 0097317 相似文献
2.
For an undirected graph G, a zero-sum flow is an assignment of non-zero real numbers to the edges, such that the sum of the values of all edges incident with each vertex
is zero. It has been conjectured that if a graph G has a zero-sum flow, then it has a zero-sum 6-flow. We prove this conjecture and Bouchet’s Conjecture for bidirected graphs
are equivalent. Among other results it is shown that if G is an r-regular graph (r ≥ 3), then G has a zero-sum 7-flow. Furthermore, if r is divisible by 3, then G has a zero-sum 5-flow. We also show a graph of order n with a zero-sum flow has a zero-sum (n + 3)2-flow. Finally, the existence of k-flows for small graphs is investigated. 相似文献
3.
4.
We study a zero-sum differential game with hybrid controls in which both players are allowed to use continuous as well as
discrete controls. Discrete controls act on the system at a given set interface. The state of the system is changed discontinuously
when the trajectory hits predefined sets, an autonomous jump set A or a controlled jump set C, where one controller can choose to jump or not. At each jump, the trajectory can move to a different Euclidean space. One
player uses all the three types of controls, namely, continuous controls, autonomous jumps, and controlled jumps; the other
player uses continuous controls and autonomous jumps. We prove the continuity of the associated lower and upper value functions
V− and V+. Using the dynamic programming principle satisfied by V− and V+, we derive lower and upper quasivariational inequalities satisfied in the viscosity sense. We characterize the lower and
upper value functions as the unique viscosity solutions of the corresponding quasivariational inequalities. Lastly, we state
an Isaacs like condition for the game to have a value
This work was partially supported by Grants DRDO 508 and ISRO 050 to the Non-linear Studies Group, Indian Institute of Science.
The first author is a University Grant Commission Research Fellow and the financial support is gratefully acknowledged.
The authors thank Prof. M.K. Ghosh, Department of Mathematics, Indian Institute of Science, for introducing the problem and
thank the referee for useful suggestions. 相似文献
5.
Zero-Sum Stochastic Games with Partial Information 总被引:1,自引:0,他引:1
Ghosh M. K. McDonald D. Sinha S. 《Journal of Optimization Theory and Applications》2004,121(1):99-118
We study a zero-sum stochastic game on a Borel state space where the state of the game is not known to the players. Both players take their decisions based on an observation process. We transform this into an equivalent problem with complete information. Then, we establish the existence of a value and optimal strategies for both players. 相似文献
6.
Yair Caro 《Journal of Combinatorial Theory, Series A》1997,80(2):367-373
A counting argument is developed and divisibility properties of the binomial coefficients are combined to prove, among other results, that[formula]whereKn, resp.Kkn, is the complete, resp. completek-uniform, hypergaph andR(Kn, Zp),R(Kkn, Z2) are the corresponding zero-sum Ramsey numbers. 相似文献
7.
For a code C=C(n,M) the level
k code of C, denoted C
k
, is the set of all vectors resulting from a linear combination of precisely k distinct codewords of C. We prove that if k is any positive integer divisible by 8, and n=k, M=k2k then there is a codeword in C
k
whose weight is either 0 or at most
. In particular, if <(4–2)2/48 then there is a codeword in C
k
whose weight is n/2–(n). The method used to prove this result enables us to prove the following: Let k be an integer divisible by p, and let f(k,p) denote the minimum integer guaranteeing that in any square matrix over Z
p
, of order f(k,p), there is a square submatrix of order k such that the sum of all the elements in each row and column is 0. We prove that lim inf f(k,2)/k<3.836. For general p we obtain, using a different approach, that f(k,p)p(
k
/ ln
k
)(1+
o
k
(1)). 相似文献
8.
A. Jaśkiewicz 《Journal of Optimization Theory and Applications》2009,141(2):321-347
Zero-sum ergodic semi-Markov games with weakly continuous transition probabilities and lower semicontinuous, possibly unbounded,
payoff functions are studied. Two payoff criteria are considered: the ratio average and the time average. The main result
concerns the existence of a lower semicontinuous solution to the optimality equation and its proof is based on a fixed-point
argument. Moreover, it is shown that the ratio average as well as the time average payoff stochastic games have the same value.
In addition, one player possesses an ε-optimal stationary strategy (ε>0), whereas the other has an optimal stationary strategy.
A. Jaśkiewicz is on leave from Institute of Mathematics and Computer Science, Wrocław University of Technology.
This work is supported by MNiSW Grant 1 P03A 01030. 相似文献
9.
Subhamay Saha 《Journal of Optimization Theory and Applications》2014,160(1):344-354
We consider a discrete time partially observable zero-sum stochastic game with average payoff criterion. We study the game using an equivalent completely observable game. We show that the game has a value and also we present a pair of optimal strategies for both the players. 相似文献
10.
Beatris Escobedo-Trujillo Daniel López-Barrientos Onésimo Hernández-Lerma 《Journal of Optimization Theory and Applications》2012,153(3):662-687
This paper deals with zero-sum stochastic differential games with long-run average payoffs. Our main objective is to give
conditions for existence and characterization of bias and overtaking optimal equilibria. To this end, first we characterize
the family of optimal average payoff strategies. Then, within this family, we impose suitable conditions to determine the
subfamilies of bias and overtaking equilibria. A key step to obtain these facts is to show the existence of solutions to the
average payoff optimality equations. This is done by the usual “vanishing discount” approach. Finally, a zero-sum game associated
to a certain manufacturing process illustrates our results. 相似文献
11.
Adrian T. Smith 《The Journal of the Operational Research Society》1983,34(5):429-430
This paper examines the relative success rates of simple techniques for the solution of 3 x 3 games. It is suggested that examination of a 2 x 2 subgame which does not possess a saddle point is the most likely means of obtaining a first time solution to the original 3 x 3 game. 相似文献
12.
13.
Prof. J. F. Mertens 《International Journal of Game Theory》1971,1(1):217-227
The purpose of this article is to extend the results of J. F.Mertens and S.Zamir, The Value of Two-Person Zero-Sum Repeated Games with Lack of Information on Both Sides (Intern. Journal of Game Theory,1, 39–64, 1971) to the case where both players are not necessarily informed of each other's pure strategy choices at each stage. 相似文献
14.
Let G be an additively written abelian group, and let S be asequence in G \ {0} with length |S| 4. Suppose that S is aproduct of two subsequences, say S = BC, such that the elementg + h occurs in the sequence S whenever g.h is a subsequenceof B or of C. Then S contains a proper zero-sum subsequence,apart from some well-characterized exceptional cases. This resultis closely connected with restricted set addition in abeliangroups. Moreover, it solves a problem on the structure of minimalzero-sum sequences, which recently occurred in the theory ofnon-unique factorizations. 2000 Mathematics Subject Classification11B50, 11B75, 11P99. 相似文献
15.
16.
Abstract This article deals with discrete-time two-person zero-sum stochastic games with Borel state and action spaces. The optimality criterion to be studied is the long-run expected average payoff criterion, and the (immediate) payoff function may have neither upper nor lower bounds. We first replace the optimality equation widely used in the previous literature with two so-called optimality inequalities, and give a new set of conditions for the existence of solutions to the optimality inequalities. Then, from the optimality inequalities we ensure the existence of a pair of average optimal stationary strategies. Our new condition is slightly weaker than those in the previous literature, and as a byproduct some interesting results such as the convergence of a value iteration scheme to the value of the discounted payoff game is obtained. Finally, we first apply the main results in this article to generalized inventory systems, and then further provide an example of controlled population processes for which all of our conditions are satisfied, while some of conditions in some of previous literature fail to hold. 相似文献
17.
Prof. J. F. Mertens 《International Journal of Game Theory》1973,2(1):231-234
The purpose of this note is to extend the results of J. F.Mertens and S.Zamir, The Value of Two-Person Zero-Sum Repeated Games with Lack of Information on Both Sides (Intern. Journal of Game Theory,1, 39–64, 1971) to the case where both players are not necessarily informed of each other's pure strategy choices at each stage. 相似文献
18.
Let G = (V, E) be a finite loopless graph and let (A, +) be an abelian group with identity 0. Then an A-magic labeling of G is a function ${\phi}$ from E into A ? {0} such that for some ${a \in A, \sum_{e \in E(v)} \phi(e) = a}$ for every ${v \in V}$ , where E(v) is the set of edges incident to v. If ${\phi}$ exists such that a = 0, then G is zero-sum A-magic. Let zim(G) denote the subset of ${\mathbb{N}}$ (the positive integers) such that ${1 \in zim(G)}$ if and only if G is zero-sum ${\mathbb{Z}}$ -magic and ${k \geq 2 \in zim(G)}$ if and only if G is zero-sum ${\mathbb{Z}_k}$ -magic. We establish that if G is 3-regular, then ${zim(G) = \mathbb{N} - \{2\}}$ or ${\mathbb{N} - \{2,4\}.}$ 相似文献
19.
S. N. Smirnov 《Doklady Mathematics》2018,97(3):215-218
A theorem related to the theory of zero-sum games is proved. Rather general assumptions on the payoff function are found that are sufficient for an optimal strategy of one of the players to be chosen in the class of mixed strategies concentrated in at most m + 1 points if the opponent chooses a pure strategy in a finite-dimensional convex compact set and m is its dimension. This theorem generalizes results of several authors, starting from Bohnenblust, Karlin, and Shapley (1950). 相似文献
20.
Sylvain Sorin Guillaume Vigeral 《Journal of Optimization Theory and Applications》2013,157(2):564-576
We give new proofs of existence of the limit of the discounted values for two person zero-sum games in the three following frameworks: absorbing, recursive, incomplete information. The idea of these new proofs is to use some comparison criteria. 相似文献