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.     

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

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.     

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.     

A combinatorial proof of associativity of Ore extensions

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

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.     

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.     

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.     

Generalizing pairs of complementary sequences and a construction of combinatorial structures

Pairs of complementary sequences such as Golay pairs have zero sum autocorrelation at all non-trivial phases. Several generalizations are known where conditions on either the autocorrelation function, or the entries of the sequences are altered. We aim to unify most of these ideas by introducing autocorrelation functions that apply to any sequences with entries in a set equipped with a ring-like structure which is closed under multiplication and contains multiplicative inverses. Depending on the elements of the chosen set, the resulting complementary pairs may be used to construct a variety of combinatorial structures such as Hadamard matrices, complex generalized weighing matrices, and signed group weighing matrices. We may also construct quasi-cyclic and quasi-constacyclic linear codes which over finite fields of order less than 5 are also Hermitian self-orthogonal. As the literature on binary and ternary Golay sequences is already quite deep, one intention of this paper is to survey and assimilate work on more general pairs of complementary sequences and related constructions of combinatorial objects, and to combine the ideas into a single theoretical framework.     

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.     

A multi-objective combinatorial model of casualty processing in major incident response

During the emergency response to mass casualty incidents decisions relating to the extrication, treatment and transporting of casualties are made in a real-time, sequential manner. In this paper we describe a novel combinatorial optimization model of this problem which acknowledges its temporal nature by employing a scheduling approach. The model is of a multi-objective nature, utilizing a lexicographic view to combine objectives in a manner which capitalizes on their natural ordering of priority. The model includes pertinent details regarding the stochastic nature of casualty health, the spatial nature of multi-site emergencies and the dynamic capacity of hospitals. A Variable Neighborhood Descent metaheuristic is employed in order to solve the model. The model is evaluated over a range of potential problems, with results confirming its effective and robust nature.     

An estimate of the pinching constant of minimal hypersurfaces with constant scalar curvature in the unit sphere

LetM ⁿ (n>3) be a closed minimal hypersurface with constant scalar curvature in the unit sphereS ⁿ⁺¹ (1) andS the square of the length of its second fundamental form. In this paper we prove thatS>n implies estimates of the formS>n+cn−d withc≥1/4. For example, forn>17 andS>n we proveS>n+1/4n which is sharper than a recent result of the authors [5] The second author's research was supported by NNSFC, FECC and CPSF.     

Interacting neural networks and the emergence of social structure

The article describes a computational model for the simulation of the emergence of social structure or social order, respectively. The model is theoretically based on the theory of social typifying by Berger and Luckmann. It consists of interacting artificial actors (agents), which are represented by two neural networks, an action net, and a perception net. By mutually adjusting of their actions, the agents are able to constitute a self‐organized social order in dependency of their personal characteristics and certain features of their environment. A fictitious example demonstrates the applicability of the model to problems of extra‐terrestrial robotics. © 2007 Wiley Periodicals, Inc. Complexity 12: 41–52, 2007