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.     

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.     

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.     

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.     

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.     

Unsteady mixed flows in non uniform closed water pipes: a Full Kinetic Approach

We recall the Pressurized and Free Surface model constructed for the modeling of unsteady mixed flows in closed water pipes where transition points between the free surface and pressurized flow are treated as a free boundary associated to a discontinuity of the gradient of pressure. Then we present a numerical kinetic scheme for the computations of unsteady mixed flows in closed water pipes. This kinetic method that we call FKA for “Full Kinetic Approach” is an easy and mathematically elegant way to deal with multiple transition points when the changes of state between free surface and pressurized flow occur. We use two approaches namely the “ghost waves approach” and the “Full Kinetic Approach” to treat these transition points. We show that this kinetic numerical scheme has the following properties: it is wet area conservative, under a CFL condition it preserves the wet area positive, it treats “naturally” the flooding zones and most of all it is very easy to implement it. Finally numerical experiments versus laboratory experiments are presented and the scheme produces results that are in a very good agreement. We also present a numerical comparison with analytic solutions for free surface flows in non uniform pipes: the numerical scheme has a very good behavior. A code to code comparison for pressurized flows is also conducted and leads to a very good agreement. We also perform a numerical experiment when flooding and drying flows may occur and finally make a numerical study of the order of the kinetic method.     

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

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

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.     

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.     

Welfare-maximizing correlated equilibria using Kantorovich polynomials with sparsity

We provide motivations for the correlated equilibrium solution concept from the game-theoretic and optimization perspectives. We then propose an algorithm that computes ${\varepsilon}$ -correlated equilibria with global-optimal (i.e., maximum) expected social welfare for normal form polynomial games. We derive an infinite dimensional formulation of ${\varepsilon}$ -correlated equilibria using Kantorovich polynomials, and re-express it as a polynomial positivity constraint. We exploit polynomial sparsity to achieve a leaner problem formulation involving sum-of-squares constraints. By solving a sequence of semidefinite programming relaxations of the problem, our algorithm converges to a global-optimal ${\varepsilon}$ -correlated equilibrium. The paper ends with two numerical examples involving a two-player polynomial game, and a wireless game with two mutually-interfering communication links.     

Memetic algorithms and hyperheuristics applied to a multiobjectivised two-dimensional packing problem

Packing problems are np-hard problems with several practical applications. A variant of a 2d Packing Problem (2dpp) was proposed in the gecco 2008 competition session. In this paper, Memetic Algorithms (mas) and Hyperheuristics are applied to a multiobjectivised version of the 2dpp. Multiobjectivisation is the reformulation of a mono-objective problem into a multi-objective one. The main aim of multiobjectivising the 2dpp is to avoid stagnation in local optima. First generation mas refers to hybrid algorithms that combine a population-based global search with an individual learning process. A novel first generation ma is proposed, and an original multiobjectivisation method is applied to the 2dpp. In addition, with the aim of facilitating the application of such first generation mas from the point of view of the parameter setting, and of enabling their usage in parallel environments, a parallel hyperheuristic is also applied. Particularly, the method applied here is a hybrid approach which combines a parallel island-based model and a hyperheuristic. The main objective of this work is twofold. Firstly, to analyse the advantages and drawbacks of a set of first generation mas. Secondly, to attempt to avoid those drawbacks by applying a parallel hyperheuristic. Moreover, robustness and scalability analyses of the parallel scheme are included. Finally, we should note that our methods improve on the current best-known solutions for the tested instances of the 2dpp.     

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.     

The value of two-person zero-sum repeated games with lack of information on both sides

We consider repeated two-person zero-sum games in which each player has only partial information about a chance move that takes place at the beginning of the game. Under some conditions on the information pattern it is proved that \(\mathop {\lim }\limits_{n \to \infty } v_n\) exists,v _n being the value of the game withn repetitions. Two functional equations are given for which \(\mathop {\lim }\limits_{n \to \infty } v_n\) is the only simultaneous solutions. We also find the least upper bound for the error term \(\left| {v_n - \mathop {\lim }\limits_{n \to \infty } v_n } \right|\) .     

The odd side of torsion geometry

We introduce and study a notion of ‘Sasaki with torsion structure’ (st ) as an odd-dimensional analogue of Kähler with torsion geometry (kt ). These are normal almost contact metric manifolds that admit a unique compatible connection with \( 3 \) -form torsion. Any odd-dimensional compact Lie group is shown to admit such a structure; in this case, the structure is left-invariant and has closed torsion form. We illustrate the relation between st structures and other generalisations of Sasaki geometry, and we explain how some standard constructions in Sasaki geometry can be adapted to this setting. In particular, we relate the st structure to a kt structure on the space of leaves and show that both the cylinder and the cone over an st manifold are kt , although only the cylinder behaves well with respect to closedness of the torsion form. Finally, we introduce a notion of ‘ \( G \) -moment map’. We provide criteria based on equivariant cohomology ensuring the existence of these maps and then apply them as a tool for reducing st structures.     

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

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.