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.     

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.     

On repeated games with general information function

For a class of repeated two-person zero-sum games with incomplete information it was proved byAumann andMaschler that limν _n exists,ν _n being the value of the game withn repetitions. If the players know at each stage the moves done by both players at all previous stages,Aumann andMaschler could prove that the error termδ _n=¦ν _n — limν _n ¦ satisfiesδ _n≤c/√n for somec>0. It was then shown byZamir that this bound is the lowest possible. In this paper it is shown that if previous moves are not always announced,δ _n may be of higher order of magnitude e.g.δ _n≥c/n ^1/3 for somec>0. New upper bounds forδ _n are given for two classes of games.     

Generalized impartial games

A complete mathematical theory of NIM type games have been developed byBouton [1902],Sprague [1935/36] andGrundy [1939]. The NIM type games are a special class of combinatorial games, called the impartial games. “Impartial” means that, at any stage, the set of legal moves is independent of whose turn it is to move. The outcome of an impartial game is that the first player either wins or loses. The results ofBouton, Sprague andGrundy are now generalized to a wider class of games which allow tie-positions. This wider class of games are defined on digraphs. It is proved that the games defined on a given digraph are all impartial games (without tie-positions) iff the birthday function (also called the terminal distance function) exists on this digraph.     

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

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

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.     

The weighted Grammar constraint

We introduce the WeightedGrammar constraint and propose propagation algorithms based on the CYK parser and the Earley parser. We show that the traces of these algorithms can be encoded as a weighted negation normal form (WNNF), a generalization of NNF that allows nodes to carry weights. Based on this connection, we prove the correctness and complexity of these algorithms. Specifically, these algorithms enforce domain consistency on the WeightedGrammar constraint in time O(n ³). Further, we propose that the WNNF constraint can be decomposed into a set of primitive arithmetic constraint without hindering propagation.     

RENS

This article introduces rens, the relaxation enforced neighborhood search, a large neighborhood search algorithm for mixed integer nonlinear programs (MINLPs). It uses a sub-MINLP to explore the set of feasible roundings of an optimal solution $\bar{x}$ of a linear or nonlinear relaxation. The sub-MINLP is constructed by fixing integer variables $x_j$ with $\bar{x} _{j} \in \mathbb {Z}$ and bounding the remaining integer variables to $x_{j} \in \{ \lfloor \bar{x} _{j} \rfloor , \lceil \bar{x} _{j} \rceil \}$ . We describe two different applications of rens: as a standalone algorithm to compute an optimal rounding of the given starting solution and as a primal heuristic inside a complete MINLP solver. We use the former to compare different kinds of relaxations and the impact of cutting planes on the so-called roundability of the corresponding optimal solutions. We further utilize rens to analyze the performance of three rounding heuristics implemented in the branch-cut-and-price framework scip. Finally, we study the impact of rens when it is applied as a primal heuristic inside scip. All experiments were performed on three publicly available test sets of mixed integer linear programs (MIPs), mixed integer quadratically constrained programs (MIQCPs), and MINLP s, using solely software which is available in source code. It turns out that for these problem classes 60 to 70 % of the instances have roundable relaxation optima and that the success rate of rens does not depend on the percentage of fractional variables. Last but not least, rens applied as primal heuristic complements nicely with existing primal heuristics in scip.     

On positive definite measures

In this paper we study the Fourier transform of unbounded measures on a locally compact groupG. After a short introductory section containing background material, especially results established byL. Argabright andJ. Gil De Lamadrid we turn to the main subjects of the paper: first we characterize \(\Re \left( G \right), \mathfrak{J}\left( G \right)\) andB(G) cones in \(\mathfrak{W}\left( G \right)\) . After that we establish the subspace \(\mathfrak{W}_\Delta \left( G \right)\) of \(\mathfrak{W}\left( G \right)\) which contains \(\mathfrak{W}_p \left( G \right)\) , the linear span of all positive definite measures.     

Kantorovič operators of second order

The Kantorovi? operators of second order are introduced byQ _n f= =(B _n+2 F)″ whereF is the double indefinite integraloff andB _n+2 the (n+2)-th Bernstein operator. The operatorsQ _n will reveal a close affinity to the so-called modified Bernstein operatorsC _n introduced bySchnabl [10] on a quite different way. The article contains investigations concerning the asymptotic behavior ofQ _n ^kn f (asn → ∞), where (k _n) is a sequence of natural numbers.     

ψ-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ψ ₂.     

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.     

A note on the nucleolus

It was shown byKohlberg [1972] that the nucleolus can be obtained by solving a linear program of extremely large size (2 ⁿ ! constraints). We show here how this program can be reduced to a more tractable size (4 ⁿ constraints).     

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.     

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.     

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.     

Semantics of OpenMath and MathML3

Even though OpenMath has been around for more than 10?years, there is still confusion about the ??semantics of OpenMath??. As the recent MathML3 recommendation semantically bases Content MathML on OpenMath Objects, this question becomes more pressing. One source of confusions about OpenMath semantics is that it is given on two levels: a very weak algebraic semantics for expression trees, which is extended by considering mathematical properties in content dictionaries that interpret the meaning of (constant) symbols. While this two-leveled way to interpret objects is well-understood in logic, it has not been spelt out rigorously for OpenMath. We present two denotational semantics for OpenMath: a construction-oriented semantics that achieves full coverage of all legal OpenMath expressions at the cost of great conceptual complexity, and a symbol-oriented one for a subset of OpenMath expressions. This subset is given by a variant of the OpenMath 2 role system, which??we claim??does not exclude any representations of meaningful mathematical objects.     

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

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.