Values of mixed games

Aumann andShapley [1973] have investigated values of games in which all players are individually insignificant, i.e. form a non-atomic continuum, or “ocean”. In this paper we treat games in which, in addition to such an ocean, there are also some “atoms”, i.e. players who are individually significant. We define spaces of such games that are analogous to those investigated byAumann andShapley, and prove the existence of values on some of them. Unlike in the non-atomic case, we find that in general there are infinitely many values, corresponding to various ways in which the atoms can be imbedded in the ocean. The results generalize those ofMilnor andShapley [1961]. Precise statements will be found in Section 2.     

On sums of graph games with last player losing

The purpose of this paper is to find the general class of graph games with last player losing which may be solved by an analogue ofBouton's [1901] solution. Moreover, it can be shown that this class contains all subtraction games, as well asLasker's [1931] nim and several other games. Games such asKayles andDawson's [1935] game with last player losing are not treated by the method of this paper and are still unsolved.     

A transplantation theorem for Fourier-Bessel coefficients

We prove a transplantation theorem for Fourier-Bessel coefficients. Theorems of such type were proved byAskey andWainger [1] andAskey [2] for ultraspherical and Jacobi coefficients, respectively. Our theorem can be also seen as a dual result to a transplantation theorem for Fourier-Bessel series which was proved byGilbert [3].     

ψ-Stability of a cooperative game without side payments

In the present paper we defineψ-stability for theAumann-Peleg theory of cooperative games without side payments, and we prove some theorems which are analogous to the core theorem byAumann andBurger. These theorems provide foundations of the theory ofψ-stability for cooperative games without side payments in addition to being of interest for their own sake. We also consider the composition of two admissible functionsψ ₁ andψ ₂.     

Factorization of Lipschitz functions and absolute convergence of Vilenkin-Fourier series

LetG be a Vilenkin group (i.e., an infinite, compact, metrizable, zero-dimensional Abelian group). Our main result is a factorization theorem for functions in the Lipschitz spaces \(\mathfrak{L}\mathfrak{i}\mathfrak{p}\) (α,p; G). As colloraries of this theorem, we obtain (i) an extension of a factorization theorem ofY. Uno; (ii) a convolution formula which says that \(\mathfrak{L}\mathfrak{i}\mathfrak{p} (\alpha , r; G) = \mathfrak{L}\mathfrak{i}\mathfrak{p} (\beta , l; G)*\mathfrak{L}\mathfrak{i}\mathfrak{p} (\alpha - \beta , r; G)\) for 0<β<α<∞ and 1≤r≤∞; and (iii) an analogue, valid for allG, of a classical theorem ofHardy andLittlewood. We also present several results on absolute convergence of Fourier series defined onG, extending a theorem ofC. W. Onneweer and four results ofN. Ja. Vilenkin andA. I. Rubinshtein. The fourVilenkin-Rubinshtein results are analogues of classical theorems due, respectively, toO. Szász, S. B. Bernshtein, A. Zygmund, andG. G. Lorentz.     

LIM is not slim

In this paper LIM, a recently proposed impartial combinatorial ruleset, is analyzed. A formula to describe the $\mathcal G $ -values of LIM positions is given, by way of analyzing an equivalent combinatorial ruleset LIM’, closely related to the classical nim. Also, an enumeration of $\mathcal P $ -positions of LIM with $n$ stones, and its relation to the Ulam-Warburton cellular automaton, is presented.     

On the relation between finitely and infinitely repeated games with incomplete information

For a class of repeated two-person zero-sum games with incomplete information it was proved byAumann andMaschler that \(\mathop {\lim }\limits_{n \to \infty } v_n\) exists,Ν _n being the value of the game withn repetitions. As for the speed of convergenceAumann andMaschler showed that the error termδ _n=¦Ν _n?limΝ _n¦ is bounded from above byc/√n for some positive constantc. Both results have been generalized byMertens andZamir. It is shown in this paper that the above mentioned theorem about the speed of convergence is sharp in the sense that there are games in whichδ _n≥c′/√n for some positive constantc′. However there are games for which δ_n is of a lower order of magnitude, for instancec′(logn)/n≤δ _n≤c (logn)/n orc′/n≤δ _n≤c/n. Sufficient conditions are given here for games to belong to one of these categories as well as examples of games from each category.     

Nonstandard utilities and the foundation of game theory

In a recent paperFishburn [1972] discussed some consequences which the use of non-Archimedean utilities has on finite two-person zero-sum games. We shall show that the state of affairs with non-Archimedean utilities is not so different from the results undervon Neumann-Morgenstern utilities asFishburn asserts, if we represent the utilities in an appropriate non-Archimedean ordered field (nonstandard model of the real numbers) and admit that the components of the optimal strategies also may assume values in this ordered field. Moreover it is proved that for every utility space (in the sense ofHausner [1954] a nonstandard utility function exists.     

Zero-sum sequential games with incomplete information

Repeated zero-sum two-person games of incomplete information on one side are considered. If the one-shot game is played sequentially, the informed player moving first, it is proved that the value of then-shot game is constant inn and is equal to the concavification of the game in which the informed player disregards his extra information. This is a strengthening ofAumann andMaschler's results for simultaneous games. Optimal strategies for both players are constructed explicitly.     

Values of games without side payments

A value forn-person games without side payments is given which coincides with theShapley value for games with side payments, and with theNash value for two-person games.     

Completeness and fixed-points

In this note the converses of recent fixed-point theorems due toKannan andChatterjea are obtained. An example is constructed to show that a metric space having the fixed-point property for homeomorphisms need not be metrically topologically complete. An example ofConnell is formulated in a more general perspective.     

HERBRAND’s Fundamental Theorem in the Eyes of JEAN VAN HEIJENOORT

Using Heijenoort??s unpublished generalized rules of quantification, we discuss the proof of Herbrand??s Fundamental Theorem in the form of Heijenoort??s correction of Herbrand??s ??False Lemma?? and present a didactic example. Although we are mainly concerned with the inner structure of Herbrand??s Fundamental Theorem and the questions of its quality and its depth, we also discuss the outer questions of its historical context and why Bernays called it ??the central theorem of predicate logic?? and considered the form of its expression to be ??concise and felicitous??.     

Computational experience with advanced implementation of decomposition algorithms for linear programming

This paper reports computational experience with the codesDecompsx andLift which are built on IBM's MPSX/370 LP software for large-scale structured programs.Decompsx is an implementation of the Dantzig-Wolfe decomposition algorithm for block-angular LP's.Lift is an implementation of a nested decomposition algorithm for staircase and block-triangular LP's. A diverse collection of test problems drawn from real applications is used to test these codes, including multinational energy models and global economic models.     

Constrainedn-person games

The usual properties of a characteristic function game were derived byvon Neumann andMorgenstern from the properties of a game in normal form. In this paper we give a linear programming principle for the calculation of the characteristic function. The principle is a direct application ofCharnes' linear programming method for the calculation of the optimal strategies and the value of a two-person zero-sum game. The linear programming principle gives another method for proving the standard properties of a characteristic function when it is derived from a game in normal form. Using an idea originated byCharnes for two person games, we develop the concept of a constrainedn-person game as a simple, practical extension of ann-person game. However the characteristic function for a constrainedn-person game may not satisfy properties, such as superadditivity, usually associated with a characteristic function.     

A sequentially compact non-compact quasi-pseudometric space

We give an example of a sequentially compact non-compact quasipseudometric space, thus finding a negative answer to the problem posed byI. L. Reilly, P. V. Subrahmanyam andM. K. Vamanamurthy in [1].     

On optimal backward perturbation bounds for the linear least squares problem

Consider the linear least squares problem min _x ‖b?Ax‖₂ whereA is anm×n (m<n) matrix, andb is anm-dimensional vector. Lety be ann-dimensional vector, and let ηls(y) be the optimal backward perturbation bound defined by $$\eta _{LS} (y) = \inf \{ ||F||_F :y is a solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} .$$ . An explicit expression of ηls(y) (y≠0) has been given in [8]. However, if we define the optimal backward perturbation bounds ηmls(y) by $$\eta _{MLS} (y) = \inf \{ ||F||_F :y is the minimum 2 - norm solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} ,$$ , it may well be asked: How to derive an explicit expression of ηmls(y)? This note gives an answer. The main result is: Ifb≠0 andy≠0, then ηmls(y)=ηls (y).     

ParNes: a rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals

In this article, we propose an algorithm, nesta-lasso, for the lasso problem, i.e., an underdetermined linear least-squares problem with a 1-norm constraint on the solution. We prove under the assumption of the restricted isometry property (rip) and a sparsity condition on the solution, that nesta-lasso is guaranteed to be almost always locally linearly convergent. As in the case of the algorithm nesta, proposed by Becker, Bobin, and Candès, we rely on Nesterov’s accelerated proximal gradient method, which takes $O(\sqrt {1/\varepsilon })$ iterations to come within $\varepsilon > 0$ of the optimal value. We introduce a modification to Nesterov’s method that regularly updates the prox-center in a provably optimal manner. The aforementioned linear convergence is in part due to this modification. In the second part of this article, we attempt to solve the basis pursuit denoising (bpdn) problem (i.e., approximating the minimum 1-norm solution to an underdetermined least squares problem) by using nesta-lasso in conjunction with the Pareto root-finding method employed by van den Berg and Friedlander in their spgl1 solver. The resulting algorithm is called parnes. We provide numerical evidence to show that it is comparable to currently available solvers.     

Markov Limid processes for representing and solving renewal problems

In this paper a new tool for simultaneous optimisation of decisions on multiple time scales is presented. The tool combines the dynamic properties of Markov decision processes with the flexible and compact state space representation of LImited Memory Influence Diagrams (Limids). A temporal version of Limids, TemLimids, is defined by adding time-related functions to utility nodes. As a result, expected discounted utility, as well as expected relative utility might be used as optimisation criteria in TemLimids. Optimisation proceeds as in ordinary Limids. A sequence of such TemLimids can be used to model a Markov Limid Process, where each TemLimid represents a macro action. Algorithms are presented to find optimal plans for a sequence of such macro actions. Use of algorithms is illustrated based on an extended version of an example from pig production originally used to introduce the Limid concept.     

О скорсти сходимости рядов фурье двумерных функций ограниченной вариации

S. A. Telyakovskii [12] generalized a theorem of Bojani? [2] on the quantitative version of the Dirichlet-Jordan test, well-known in the classical Fourier analysis. Our goal is to extend Telyakovskii’s theorem from single to double Fourier series of functions in two variables that are of bounded variation in the sense of Hardy and Krause. The related theorems of Hardy [5] and Móricz [7] for such functions are corollaries of our Theorem proved in this paper.     

p-adic representations and vector bundles on Mumford curves

Christopher Deninger andAnnette Werner constructed a functor that associates representations of the algebraic fundamental group of an algebraic curve to a class of vector bundles on that curve. We compare this to a construction byFaltings for Mumford curves that associates representations of the Schottky group to semistable vector bundles of degree 0. We prove that for a certain class of vector bundles on Mumford curves the constructions induce isomorphic representations.