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

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.     

A new value for games without transferable utilities

We define axiomatically a unique concept of value for games without transferable utilities, which is a generalization ofNash's bargaining model. Unlike other concepts, it does not coincide with theShapley value in the case of transferable utilities.     

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

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.     

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.     

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.     

Correlated equilibria in some classes of two-person games

A correlated equilibrium in a two-person game is “good” if for everyNash equilibrium there is a player who prefers the correlated equilibrium to theNash equilibrium. If a game is “best-response equivalent” to a two-person zero-sum game, then it has no good correlated equilibria. But games which are “almost strictly competitive” or “order equivalent” to a two-person zero-sum game may have good correlated equilibria.     

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.     

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.     

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.     

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

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.     

Darstellung der klassischen hyperbolischen Raumgeometrie durch relativistische Motoren

The theory ofLorentz transformations developped in [5]–[15] admits a simple construction of elements (23)–(50) in the classical hyperbolic metric space by means of complex 2×2 matrices. In the infinitesimal 3-dimensional Euclidean neighbourhood of a point on the unit sphere in theMinkowski space-time these matrices reduce to the classical motors (54) (Cf.Brand [3]).     

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.     

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.     

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.     

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.