Wythoff partizan subtraction

We introduce a class of normal-play partizan games, called Complementary Subtraction. These games are instances of Partizan Subtraction where we take any set A of positive integers to be Left’s subtraction set and let its complement be Right’s subtraction set. In wythoff partizan subtraction we take the set A and its complement B from wythoff nim, as the two subtraction sets. As a function of the heap size, the maximum size of the canonical forms grows quickly. However, the value of the heap is either a number or, in reduced canonical form, a switch. We find the switches by using properties of the Fibonacci word and standard Fibonacci representations of integers. Moreover, these switches are invariant under shifts by certain Fibonacci numbers. The values that are numbers, however, are distinct, and we can find their binary representation in polynomial time using a representation of integers as sums of Fibonacci numbers, known as the ternary (or “the even”) Fibonacci representation.     

Selective sums of loopy partizan graph games

A loopy partizan graph game is a two-person game of perfect information which is played on a labelled digraph. The disjunctive sum, the continued conjunctive sum, and the selective sum are formulations for playing several l.p.g.g.'s simultaneously, so as to form a single compound game. In this paper, we present an analysis of the selective sum by utilizing certain elements of the theories for the disjunctive sum and the continued conjunctive sum.     

PSPACE-hardness of some combinatorial games

PSPACE-hardness of four families of win-lose-draw games' played on a digraph with blocking, capture, or annihilation rules is proved. Special cases of three of the families are shown to be PSPACE-complete: Further, the PSPACE-completeness of six families of win-lose games in which two players mark or remove nodes of digraphs according to given rules is proved. The first two families contain partizan games, the last eight impartial games. All the games have been defined previously in the literature or are slight variations of such games.     

Partizan octal games: Partizan subtraction games

A subtraction gameS=(s ₁, ...,s _k)is a two-player game played with a pile of tokens where each player at his turn removes a number ofm of tokens providedmεS. The player first unable to move loses, his opponent wins. This impartial game becomes partizan if, instead of one setS, two finite setsS _L andS _R are given: Left removes tokens as specified byS _L, right according toS _R. We say thatS _L dominatesS _R if for all sufficiently large piles Left wins both as first and as second player. We exhibit a curious property of dominance and provide two subclasses of games in which a dominance relation prevails. We further prove that all partizan subtraction games areperiodic, and investigatepure periodicity.     

Discrete Concavity and Zeros of Polynomials

Murota et al. have recently developed a theory of discrete convex analysis as a framework to solve combinatorial optimization problems using ideas from continuous optimization. This theory concerns M-convex functions on jump systems. We introduce here a family of M-concave functions arising naturally from polynomials (over the field of Puiseux series) with prescribed non-vanishing properties. We also provide a short proof of Speyer's “hive theorem” which he used to give a new proof of Horn's conjecture on eigenvalues of sums of Hermitian matrices. Due to limited space a more coherent treatment and proofs will appear elsewhere.     

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.     

Reduction of Silverman-like games to games on bounded sets

A two person zero sum game is regarded as Silverman-like if the strategy sets are sets of real numbers bounded below, the payoff function is bounded, the maximum payoff is achieved whenever the second player's numbery exceeds the first player's numberx by “too much”, and the minimum is achieved wheneverx exceedsy by “too much”. Explicit upper bounds are obtained for pure strategies to be included in an optimal mixed strategy in such games. In particular, if the strategy sets are discrete, the games may be reduced to games on specified finite sets.     

Values and cores of fuzzy games with infinitely many players

The problem of the existence ofvalues (FA-valued, linear, positive, symmetric and efficient operators) on symmetric spaces of “fuzzy games” (that is, ideal set functions of bounded variation) arises naturally from [8], [18], [23] and [2], [3], [4] where it is implicitely approached for technical purposes. In our present work, this problem is approached in itself for the main reason that it is essentially related with the problem of the existence of significant countable additive measures lying in the cores of the “market games”. In fact, it is shown here that there exists a continuous value on the closed subspacebv′ICA ofIBV spanned by thebv′ functions of “fuzzy probability measures” ([9]), this values is “diagonal” onpICA, the closed subspace ofbv′ICA spanned by the natural powers of the fuzzy measures and this is used to prove the main result stating that the cooperative markets contained inpICA have unique fuzzy measures in their cores which are exactly the corresponding diagonal values. This result is of interest because it is providing a tool of determiningCA measures lying in the cores of large classes of games which are not necessarily “non-atomic” and, specially, because it is opening a way toward a new approach of the “Value Equivalence Principle” for differentiable markets with a continuum of traders which are not “perfectly competitive”.     

Mollifiers for games in normal form and the Harsanyi-Selten valuation function

The concepts of disruption and mollifiers ofCharnes/Rousseau/Seiford [1978] for games in characteristic function form are here extended to games in normal form. We show for a large class of games that theHarsanyi-Selten [1959] modification ofvon Neumann /Morgenstern's [1953] construction of a characteristic function for games in normal form, to take better account of “disruption” or “threat” possibilities, yields a constant mollifier. In general, it can be non-superadditive when the von Neumann-Morgenstern function is superadditive, and it also fails to take account of coalitional sizes. Our extended “homomollifier” concept does, and always yields a superadditive constant sum characteristic function.     

Exceptions and counterexamples: Understanding Abel's comment on Cauchy's Theorem

It may seem odd that Abel, a protagonist of Cauchy's new rigor, spoke of “exceptions” when he criticized Cauchy's theorem on the continuity of sums of continuous functions. However, when interpreted contextually, exceptions appear as both valid and viable entities in the early 19th century. First, Abel's use of the term “exception” and the role of the exception in his binomial paper is documented and analyzed. Second, it is suggested how Abel may have acquainted himself with the exception and his use of it in a process denoted critical revision is discussed. Finally, an interpretation of Abel's exception is given that identifies it as a representative example of a more general transition in the understanding of mathematical objects that took place during the period. With this interpretation, exceptions find their place in a fundamental transition during the early 19th century from a formal approach to analysis toward a more conceptual one.     

Stability of solutions for Ky Fan's section theorem with some applications

In this paper, we prove that “most of” problems in Ky Fan's section theorem (in the sense of Baire category) are essential and that for any problem in Ky Fan's section theorem, there exists at least one essential component of its solution set. As applications, we deduce both the existence of essential components of the set of Ky Fan's points based on Ky Fan's minimax inequality theorem and the existence of essential components of the set of Nash equilibrium points for general n-person non-cooperative games with non-concave payoffs.     

Pareto efficiency,simple game stability,and social structure in finitely repeated games

Simple game (sensu Brown and Vincent, 1987) evolutionary theory, when coupled with social structure measured as non‐random encounter of strategy “clones”, often permits equilibrium refinement leading to Pareto superior outcomes (e.g., Axelrod, 1981; Myerson et al., 1991), a foundational goal of economic game theory (Myerson, 1991: 370–375). This conclusion, derived from analyses of one‐shot and infinitely repeated games, fails for finitely repeated games. While mutant cluster invasion enhances Pareto efficiency of equilibria in the former, it can depress Pareto efficiency in the latter. Cooperative equilibria of finitely repeated games (under economic analysis) can be susceptible to cluster‐invasion by even more Pareto efficient strategies which are not themselves evolutionarily stable. Evolutionary (simple) game theory's ability to eliminate Pareto inferior Nash equilibrium strategies induces vulnerabilities foreign to economic analysis. Simple game analysis of finitely repeated games suggests that social structure, modeled as perennial invasion by mutant‐clusters, can induce cyclic invasion, saturation, and loss of cooperation.     

Decompositions of modules lacking zero sums

A module over a semiring lacks zero sums (LZS) if it has the property that v +w = 0 implies v = 0 and w = 0. While modules over a ring never lack zero sums, this property always holds for modules over an idempotent semiring and related semirings, so arises for example in tropical mathematics.A direct sum decomposition theory is developed for direct summands (and complements) of LZS modules: The direct complement is unique, and the decomposition is unique up to refinement. Thus, every finitely generated “strongly projective” module is a finite direct sum of summands of R (assuming the mild assumption that 1 is a finite sum of orthogonal primitive idempotents of R). This leads to an analog of the socle of “upper bound” modules. Some of the results are presented more generally for weak complements and semi-complements. We conclude by examining the obstruction to the “upper bound” property in this context.     

Impartial poker nim

The combinatorial game of nim is well-studied, along with many impartial and partizan modifications. We develop a new impartial modification using the idea of bogus nim heaps and preventing loops. We completely characterize the \(\mathcal {P}\)-positions for the two-heap version, and solve the problem for a larger number of heaps dependent on counting integer partitions of a fixed size.     

Monotonic solutions of cooperative games

The principle of monotonicity for cooperative games states that if a game changes so that some player's contribution to all coalitions increases or stays the same then the player's allocation should not decrease. There is a unique symmetric and efficient solution concept that is monotonic in this most general sense — the Shapley value. Monotonicity thus provides a simple characterization of the value without resorting to the usual “additivity” and “dummy” assumptions, and lends support to the use of the value in applications where the underlying “game” is changing, e.g. in cost allocation problems.     

Calculus and Analysis in Early 19th-Century Britain: The Work of William Wallace

Scottish-born William Wallace (1768–1843) was an early exponent of the differential calculus in Britain and translator of French mathematical works. Encyclopaedias published during the early 19th century provided a valuable educational resource, to which Wallace and his colleague, James Ivory, contributed. Wallace's encyclopaedia articles on “Fluxions” and his other analytical writings are examined here, as are his relations with James Ivory, John Herschel, and others. Wallace's long 1815 article on “Fluxions” in the Edinburgh Encyclopaedia was the first complete account of calculus, using differential notation, to be published in English. There, he attempted an original and rigorous “doctrine of limits,” which deserved more attention than it received. In 1832, while professor of mathematics in Edinburgh, he applied analysis to support the reform of taxation proposed in the Reform Bill. It is suggested that the later neglect of Wallace's achievements is attributable to a mix of personal, institutional, political, and national rivalries. Copyright 1999 Academic Press.William Wallace né en Écosse (1768–1843) fut un interprète précoce du calcul différentiel en Grande Bretagne et traduisit des ouvrages mathématiques de langue française. Les encyclopédies publiées au début du XIXe siècle fournirent une précieuse ressource pédagogique à laquelle contribuèrent Wallace et son collègue James Ivory. Les articles encyclopédiques de Wallace sur les “Fluxions” et d'autres écrits analytiques font l'objet du présent article; et aussi ses relations avec James Ivory, John Herschel et d'autres mathématiciens. Le long article de Wallace sur les “Fluxions” paru dans l'Edinburgh Encyclopaedia de 1815 fut le premier exposé complet du calcul, utilisant la notation différentielle, à être publié en anglais. Dans cet article, il mit en oeuvre une “doctrine des limites” originale et rigoureuse, qui méritait plus d'attention qu'elle ne reçut. En 1832, alors qu'il était professeur de mathématiques à Edimbourg, il utilisa l'analyse pour soutenir la réforme fiscale proposée dans le Projet de loi de Réforme. Cet article suggère que l'oubli postérieur de l'oeuvre accomplie par Wallace doit être attribué à un mélange de rivalités personnelles, institutionnelles, politiques et nationales.     

The modified nucleolus: Properties and axiomatizations

A new solution concept for cooperative transferable utility games is introduced, which is strongly related to the nucleolus and therefore called modified nucleolus. It takes into account both the “power”, i.e. the worth, and the “blocking power” of a coalition, i.e. the amount which the coalition cannot be prevented from by the complement coalition. It can be shown that the modified nucleolus is reasonable, individually rational for weakly superadditive games, coincides with the prenucleolus for constant-sum games, and is contained in the core for convex games. Finally this paper proposes two axiomatizations of this solution concept on the set of games on an infinite universe of players which are similar to Sobolev's characterization of the prenucleolus.     

Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon

In this paper we propose a new class of games, the “strategically zero-sum games,” which are characterized by a special payoff structure. We show that for a large body of correlation schemes which includes the correlated strategies “à la Aumann”, strategically zero-sum games are exactly these games for which no completely mixed Nash equilibrium can be improved upon.     

Experimental results on ultimatum games with incomplete information

This paper is about experiments on two versions of ultimatum games with incomplete information, called the offer game and the demand game. We apply the strategy method, that is, each subject had to design a complete strategy in advance instead of reacting spontaneously to a situation which occurs in the game. Game theory predicts very similar outcomes for the offer and the demand games. Our experiments, however, show significant differences in behavior between both games. Using the strategy method, allows us to explore the motivations leading to those differences. Since each subject played the same version of the game eight rounds against changing anonymous opponents we can also study subjects' learning behavior. We propose a theory of boundedly rational behavior, called the “anticipation philosophy”, which is well supported by the experimental data.