Embedding processes in combinatorial game theory

Berlekamp asked the question “What is the habitat of ∗2?” (See Guy, 1996 [6].) It is possible to generalize the question and ask “For a game G, what is the largest n such that ∗n is a position of G?” This leads to the concept of the nim dimension. In Santos and Silva (2008) [8] a fractal process was proposed for analyzing the previous questions. For the same purpose, in Santos and Silva (2008) [9], an algebraic process was proposed. In this paper we implement a third idea related to embedding processes. With Alan Parr’s traffic lights, we exemplify the idea of estimating the “difficulty” of the game and proving that its nim dimension is infinite.     

Atomic weights and the combinatorial game of bipass

We define an all-small ruleset, bipass, within the framework of normal play combinatorial games. A game is played on finite strips of black and white stones. Stones of different colors are swapped provided they do not bypass one of their own kind. We find a simple surjective function from the strips to integer atomic weights (Berlekamp, Conway and Guy 1982) that measures the number of units in all-small games. This result provides explicit winning strategies for many games, and in cases where it does not, it gives narrow bounds for the canonical form game values. We find game values for some parametrized families of games, including an infinite number of strips of value ?, and we prove that the game value ?2 does not appear as a disjunctive sum of bipass. Lastly, we define the notion of atomic weight tameness, and prove that optimal misére play bipass resembles optimal normal play.     

A simple,dynamic extension of temporal motivation theory

ABSTRACT

Temporal motivation theory (TMT) has been criticized for its static representation and neglect of the environment. In this paper, I develop goal sampling theory (GST) to appease these criticisms and extend our understanding of goal choices beyond momentary preferences and into dynamic updating and sampling behavior across time. GST draws from temporal motivational theory, sampling models of impression formation, and organizational theory on how the environment constrains behavior and situates aspects of each into a formal model of goal sampling. Doing so addresses the limitations of our prior thinking, introduces new concepts and predictions, and provides a mathematical framework that lends itself to computational modeling.     

A symbolic finite-state approach for automated proving of theorems in combinatorial game theory

We develop a finite-state automata approach, implemented in a Maple package Toads and Frogs available from our websites, for conjecturing, and then rigorously proving, values for large families of positions in Richard Guy's combinatorial game ‘Toads and Frogs’. In particular, we prove a conjecture of Jeff Erickson.     

Avoiding non-optimal management decisions by applying a three-person inspection game

An inspection game models a conflict situation between an inspector and an inspectee. The mathematical analysis aims to generate optimal behavior of the inspectee under the assumption that an undesirable action of the inspectee could otherwise be carried out strategically. In this paper the controller’s (inspector’s) particular job is to audit a manager’s (inspectee’s) decision and to submit a report to the company’s top managers for examination. Thus, a conflict as regards the choice of behavioral actions of the manager, the controller and the top management impends. Based on Fandel and Trockel (2011a) this modified inspection game is discussed here for the first time as a three-person game in the context of a manager’s faulty decision that will unnecessarily add to the company’s costs and that the top management understandably wishes to minimize. We will first examine the conditions under which a Nash equilibrium occurs in this three-person game in which poor management, poor monitoring and poor revision coincide. We will then examine the effects that the penalties and bonuses exert on the Nash equilibrium solution. We will find that penalties and bonuses can neutralize each other in their effects on the improved decision making by the manager and the controller.     

Submodularity of some classes of the combinatorial optimization games

Submodularity (or concavity) is considered as an important property in the field of cooperative game theory. In this article, we characterize submodular minimum coloring games and submodular minimum vertex cover games. These characterizations immediately show that it can be decided in polynomial time that the minimum coloring game or the minimum vertex cover game on a given graph is submodular or not. Related to these results, the Shapley values are also investigated.Supported by the Berlin-Zürich Joint Graduate Program Combinatorics, Geometry, and Computation (CGC), financed by ETH Zürich and the German Science Foundation (DFG).     

博弈论在通信对抗态势预测中的应用

本文首先提出了基于博弈论预测电磁态势演变的基本构想,设置了通信对抗的场景并构建了相应的数学模型.其次,分析了通信对抗电磁态势生成流程,最后结合一定的作战背景进行了仿真实验,基于双方博弈的原则预测了通信对抗态势的演变.仿真结果与理论分析相符,该研究成果已在多个作战仿真系统中得到了成功应用.     

The union of minimal hitting sets: Parameterized combinatorial bounds and counting

A k-hitting set in a hypergraph is a set of at most k vertices that intersects all hyperedges. We study the union of all inclusion-minimal k-hitting sets in hypergraphs of rank r (where the rank is the maximum size of hyperedges). We show that this union is relevant for certain combinatorial inference problems and give worst-case bounds on its size, depending on r and k. For r=2 our result is tight, and for each r3 we have an asymptotically optimal bound and make progress regarding the constant factor. The exact worst-case size for r3 remains an open problem. We also propose an algorithm for counting all k-hitting sets in hypergraphs of rank r. Its asymptotic runtime matches the best one known for the much more special problem of finding one k-hitting set. The results are used for efficient counting of k-hitting sets that contain any particular vertex.     

A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games

We suggest the first strongly subexponential and purely combinatorial algorithm for solving the mean payoff games problem. It is based on iteratively improving the longest shortest distances to a sink in a possibly cyclic directed graph.We identify a new “controlled” version of the shortest paths problem. By selecting exactly one outgoing edge in each of the controlled vertices we want to make the shortest distances from all vertices to the unique sink as long as possible. The decision version of the problem (whether the shortest distance from a given vertex can be made bigger than a given bound?) belongs to the complexity class NP∩CONP. Mean payoff games are easily reducible to this problem. We suggest an algorithm for computing longest shortest paths. Player MAX selects a strategy (one edge from each controlled vertex) and player MIN responds by evaluating shortest paths to the sink in the remaining graph. Then MAX locally changes choices in controlled vertices looking at attractive switches that seem to increase shortest paths lengths (under the current evaluation). We show that this is a monotonic strategy improvement, and every locally optimal strategy is globally optimal. This allows us to construct a randomized algorithm of complexity , which is simultaneously pseudopolynomial (W is the maximal absolute edge weight) and subexponential in the number of vertices n. All previous algorithms for mean payoff games were either exponential or pseudopolynomial (which is purely exponential for exponentially large edge weights).     

Interaction indices for games on combinatorial structures with forbidden coalitions

The notion of interaction among a set of players has been defined on the Boolean lattice and Cartesian products of lattices. The aim of this paper is to extend this concept to combinatorial structures with forbidden coalitions. The set of feasible coalitions is supposed to fulfil some general conditions. This general representation encompasses convex geometries, antimatroids, augmenting systems and distributive lattices. Two axiomatic characterizations are obtained. They both assume that the Shapley value is already defined on the combinatorial structures. The first one is restricted to pairs of players and is based on a generalization of a recursivity axiom that uniquely specifies the interaction index from the Shapley value when all coalitions are permitted. This unique correspondence cannot be maintained when some coalitions are forbidden. From this, a weak recursivity axiom is defined. We show that this axiom together with linearity and dummy player are sufficient to specify the interaction index. The second axiomatic characterization is obtained from the linearity, dummy player and partnership axioms. An interpretation of the interaction index in the context of surplus sharing is also proposed. Finally, our interaction index is instantiated to the case of games under precedence constraints.     

Is It Better to Forget? Stimulus-Response, Prediction, and the Weight of Past Experience in a Fast-Paced Bargaining Task

Decision makers in dynamic environments such as air traffic control, firefighting, and call center operations adapt in real-time using outcome feedback. Understanding this adaptation is important for influencing and improving the decisions made. Recently, stimulus-response (S-R) learning models have been proposed as explanations for decision makers' adaptation. S-R models hypothesize that decision makers choose an action option based on their anticipation of its success. Decision makers learn by accumulating evidence over action options and combining that evidence with prior expectations. This study examines a standard S-R model and a simple variation of this model, in which past experience may receive an extremely low weight, as explanations for decision makers' adaptation in an evolving Internet-based bargaining environment. In Experiment 1, decision makers are taught to predict behavior in a bargaining task that follows rules that may be the opposite of, congruent to, or unrelated to a second task in which they must choose the deal terms they will offer. Both models provide a good account of the prediction task. However, only the second model, in which decision makers heavily discount all but the most recent past experience, provides a good account of subsequent behavior in the second task. To test whether Experiment 1 artificially related choice behavior and prediction, a second experiment examines both models' predictions concerning the effects of bargaining experience on subsequent prediction. In this study, decision models where long-term experience plays a dominating role do not appear to provide adequate explanations of decision makers' adaptation to their opponent's changing response behavior.     

A combinatorial proof of associativity of Ore extensions

We use a counting argument to show that Ore extensions are associative.     

A fixed point theorem for o‐minimal structures

We prove a definable analogue to Brouwer's Fixed Point Theorem for o‐minimal structures of real closed field expansions: A continuous definable function mapping from the unit simplex into itself admits a fixed point, even though the underlying space is not necessarily topologically complete. Our proof is direct and elementary; it uses a triangulation technique for o‐minimal functions, with an application of Sperner's Lemma. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Continuos social decision procedures

Classical social decision procedures are supposed to map lists of preference orderings into binary relations which describe society ‘preferences’. But when there are infinitely many alternatives the resulting plethora of possible preference orderings make it impossible to differentiate ‘nearby’ preference relations. If the preference information used to make social decisions is imperfect, society may wish to implement a continuous social decision procedure (SDP) so that nearby preference configurations will map into nearby social preference relations. It is shown here that a continuity requirement can severely restrict the admissible behavior of a social decision procedure. Furthermore, a characterization of continuous SDPs is presented which facilitates the examination of such procedures and their relation to various voting mechanisms.     

Braiding minimal sets of vector fields

We extend a classical but fundamental theorem of knot and braid theories to describe the geometry of nonsingular minimal sets of 3-dimensional flows.

     

A class of combinatorial identities

A general theorem for providing a class of combinatorial identities where the sum is over all the partitions of a positive integer is proven. Five examples as the applications of the theorem are given.     

Newsvendor models for innovative products with one-shot decision theory

In this paper, newsvendor problems for innovative products are analyzed. Because the product is new, no relevant historical data is available for statistical demand analysis. Instead of using the probability distribution, the possibility distribution is utilized to characterize the uncertainty of the demand. We consider products whose life cycles are expected to be smaller than the procurement lead times. Determining optimal order quantities of such products is a typical one-shot decision problem for a retailer. Therefore, newsvendor models for innovative products are proposed based on the one-shot decision theory (OSDT). The main contributions of this research are as follows: the general solutions of active, passive, apprehensive and daring focus points and optimal alternatives are proposed and the existence theorem is established in the one-shot decision theory; a simple and effective approach for identifying the possibility distribution is developed; newsvendor models with four types of focus points are built; managerial insights into the behaviors of different types of retailers are gained by the theoretical analysis; the proposed models are scenario-based decision models which provide a fundamental alternative to analyze newsvendor problems for innovative products.     

A combinatorial classification of 2-regular simple modules for Nakayama algebras

Enomoto showed for finite dimensional algebras that the classification of exact structures on the category of finitely generated projective modules can be reduced to the classification of 2-regular simple modules. In this article, we give a combinatorial classification of 2-regular simple modules for Nakayama algebras and we use this classification to answer several natural questions such as when there is a unique exact structure on the category of finitely generated projective modules for Nakayama algebras. We also classify 1-regular simple modules, quasi-hereditary Nakayama algebras and Nakayama algebras of global dimension at most two. It turns out that most classes are enumerated by well-known combinatorial sequences, such as Fibonacci, Riordan and Narayana numbers. We first obtain interpretations in terms of the Auslander-Reiten quiver of the algebra using homological algebra, and then apply suitable bijections to relate these to combinatorial statistics on Dyck paths.     

A model of far-sighted electoral competition

A model is described in which candidates adopt positions in sequences of election contests against opponents randomly drawn from a large population. Symmetric steady-state equilibria of the model require rational selection of positions by all candidates against the aggregated behavior of the population, taking into account constraints which an individual's current selections impose on his future selections.     

A new binary relation to compare viability of winning coalitions and its interrelationships to desirability relation and blockability relation

This paper aims to propose a new type of binary relations, called the viability relation, defined on the set of all coalitions in a simple game for a comparison of coalition influence, and to investigate its properties, especially its interrelationships to the desirability relation and the blockability relation. The viability relation is defined to compare coalitions based on their robustness over deviation of their members for complementing the inability of the desirability relation and the blockability relation to make a distinguishable comparison among winning coalitions. It is verified in this paper that the viability relation on a simple game is always transitive and is complete if and only if the simple game is S-unanimous for a coalition S. Examples show that there are no general inclusion relations among the desirability relation, the blockability relation and the viability relation. It is also verified that the viability relation and the blockability relation are complementary to each other. Specifically, the blockability relation between two coalitions is equivalent to the inversed viability relation between the complements of the two coalitions.