Stability and the immediate acceptance rule when school priorities are weak

In a model of school choice, we allow school priorities to be weak and study the preference revelation game induced by the immediate acceptance (IA) rule (also known as the Boston rule), or the IA game. When school priorities can be weak and matches probabilistic, three stability notions—ex post stability, ex ante stability, and strong ex ante stability—and two ordinal equilibrium notions—sd equilibrium and strong sd equilibrium—become available (“sd” stands for stochastic dominance). We show that for no combination of stability and equilibrium notions does the set of stable matches coincide with the set of equilibrium matches of the IA game. This stands in contrast with the existing result that the two sets are equal when priorities are strict. We also show that in the presence of weak priorities, the transition from the IA rule to the deferred acceptance rule may, in fact, harm some students.     

Game theory with translucent players

A traditional assumption in game theory is that players are opaque to one another—if a player changes strategies, then this change in strategies does not affect the choice of other players’ strategies. In many situations this is an unrealistic assumption. We develop a framework for reasoning about games where the players may be translucent to one another; in particular, a player may believe that if she were to change strategies, then the other player would also change strategies. Translucent players may achieve significantly more efficient outcomes than opaque ones. Our main result is a characterization of strategies consistent with appropriate analogues of common belief of rationality. Common Counterfactual Belief of Rationality (CCBR) holds if (1) everyone is rational, (2) everyone counterfactually believes that everyone else is rational (i.e., all players i believe that everyone else would still be rational even if i were to switch strategies), (3) everyone counterfactually believes that everyone else is rational, and counterfactually believes that everyone else is rational, and so on. CCBR characterizes the set of strategies surviving iterated removal of minimax-dominated strategies, where a strategy \(\sigma \) for player i is minimax dominated by \(\sigma '\) if the worst-case payoff for i using \(\sigma '\) is better than the best possible payoff using \(\sigma \).     

Stationary,completely mixed and symmetric optimal and equilibrium strategies in stochastic games

In this paper, we address various types of two-person stochastic games—both zero-sum and nonzero-sum, discounted and undiscounted. In particular, we address different aspects of stochastic games, namely: (1) When is a two-person stochastic game completely mixed? (2) Can we identify classes of undiscounted zero-sum stochastic games that have stationary optimal strategies? (3) When does a two-person stochastic game possess symmetric optimal/equilibrium strategies? Firstly, we provide some necessary and some sufficient conditions under which certain classes of discounted and undiscounted stochastic games are completely mixed. In particular, we show that, if a discounted zero-sum switching control stochastic game with symmetric payoff matrices has a completely mixed stationary optimal strategy, then the stochastic game is completely mixed if and only if the matrix games restricted to states are all completely mixed. Secondly, we identify certain classes of undiscounted zero-sum stochastic games that have stationary optima under specific conditions for individual payoff matrices and transition probabilities. Thirdly, we provide sufficient conditions for discounted as well as certain classes of undiscounted stochastic games to have symmetric optimal/equilibrium strategies—namely, transitions are symmetric and the payoff matrices of one player are the transpose of those of the other. We also provide a sufficient condition for the stochastic game to have a symmetric pure strategy equilibrium. We also provide examples to show the sharpness of our results.     

Games with randomly disturbed payoffs: A new rationale for mixed-strategy equilibrium points

Equilibrium points in mixed strategies seem to be unstable, because any player can deviate without penalty from his equilibrium strategy even if he expects all other players to stick to theirs. This paper proposes a model under which most mixed-strategy equilibrium points have full stability. It is argued that for any gameΓ the players' uncertainty about the other players' exact payoffs can be modeled as a disturbed gameΓ ^*, i.e., as a game with small random fluctuations in the payoffs. Any equilibrium point inΓ, whether it is in pure or in mixed strategies, can “almost always” be obtained as a limit of a pure-strategy equilibrium point in the corresponding disturbed gameΓ ^* when all disturbances go to zero. Accordingly, mixed-strategy equilibrium points are stable — even though the players may make no deliberate effort to use their pure strategies with the probability weights prescribed by their mixed equilibrium strategies — because the random fluctuations in their payoffs willmake them use their pure strategies approximately with the prescribed probabilities.     

General Theorem on a Finite Support of Mixed Strategy in the Theory of Zero-Sum Games

A theorem related to the theory of zero-sum games is proved. Rather general assumptions on the payoff function are found that are sufficient for an optimal strategy of one of the players to be chosen in the class of mixed strategies concentrated in at most m + 1 points if the opponent chooses a pure strategy in a finite-dimensional convex compact set and m is its dimension. This theorem generalizes results of several authors, starting from Bohnenblust, Karlin, and Shapley (1950).     

On the Role of Mixed Strategies in Elementary Decision Analysis and Related Decision-Support-System Treatments

We first demonstrate that mixed strategies are relevant in decision analysis for a maximin decision-maker quite apart from any game-theory considerations. This rectifies the apparent misconception that results from MS/OR textbooks which discuss mixed strategies only in the game-theory setting. Next we show an example of an implementable mixed strategy, by which we mean a mixed decision strategy which does not require randomization for its implementation. This application is to portfolio construction.     

Variational inequality formulation for the games with random payoffs

We consider an n-player non-cooperative game with random payoffs and continuous strategy set for each player. The random payoffs of each player are defined using a finite dimensional random vector. We formulate this problem as a chance-constrained game by defining the payoff function of each player using a chance constraint. We first consider the case where the continuous strategy set of each player does not depend on the strategies of other players. If a random vector defining the payoffs of each player follows a multivariate elliptically symmetric distribution, we show that there exists a Nash equilibrium. We characterize the set of Nash equilibria using the solution set of a variational inequality (VI) problem. Next, we consider the case where the continuous strategy set of each player is defined by a shared constraint set. In this case, we show that there exists a generalized Nash equilibrium for elliptically symmetric distributed payoffs. Under certain conditions, we characterize the set of a generalized Nash equilibria using the solution set of a VI problem. As an application, the random payoff games arising from electricity market are studied under chance-constrained game framework.     

Symmetric equilibrium with random entry

This paper considers Cournot-Nash equilibrium with free entry among identical firms which possess large minimum efficient scale. We consider equilibrium in which all firms receive equal treatment by allowing firms to play mixed strategies. In particular, firms randomize over the decision to enter or not. It is shown that symmetric Cournot-Nash equilibrium in mixed strategies exists when there is a finite number of potential entrants. We then consider a sequence of such mixed strategy equilibria as the number of potential entrants gets large. It is shown that such a sequence always has a convergent subsequence whose limit is a symmetric equilibrium in mixed strategies when the number of potential entrants is infinite. An example is given which shows that increased competition, in the form of a larger pool of potential entrants, is socially harmful in that expected social surplus is decreasing in the number of potential entrants.     

A Strong Anti-Folk Theorem

We study the properties of finitely complex, symmetric, globally stable, and semi-perfect equilibria. We show that: (1) If a strategy satisfies these properties then players play a Nash equilibrium of the stage game in every period; (2) The set of finitely complex, symmetric, globally stable, semi-perfect equilibrium payoffs in the repeated game equals the set of Nash equilibria payoffs in the stage game; and (3) A strategy vector satisfies these properties in a Pareto optimal way if and only if players play some Pareto optimal Nash equilibrium of the stage game in every stage. Our second main result is a strong anti-Folk Theorem, since, in contrast to what is described by the Folk Theorem, the set of equilibrium payoffs does not expand when the game is repeated.This paper is a revised version of Chapter 3 of my Ph.D. thesis, which has circulated under the title “An Interpretation of Nash Equilibrium Based on the Notion of Social Institutions”.     

Stability of the Equilibrium to the Boltzmann Equation with Large Potential Force

The Boltzmann equation with external potential force exists a unique equilibrium—local Maxwellian. The author constructs the nonlinear stability of the equilibrium when the initial datum is a small perturbation of the local Maxwellian in the whole space R~3. Compared with the previous result [Ukai, S., Yang, T. and Zhao, H.-J.,Global solutions to the Boltzmann equation with external forces, Anal. Appl.(Singap.), 3,2005, 157–193], no smallness condition on the Sobolev norm H~1 of the potential is needed in our arguments. The proof is based on the entropy-energy inequality and the L~2-L~∞ estimates.     

An <Emphasis Type="Italic">m</Emphasis><Superscript>th</Superscript> Generation Model for Weak Ranking of Players in a Tournament

The problem of ranking players in a tournament has been studied by a number of authors. The methods developed for ranking players fall under two general headings—direct methods and rating methods. The present paper extends the tournament ranking problem in two directions. First, the usual definition of a tournament is broadened to include ties or draws. Thus, our model determines the best weak ranking of the players. Second, the ranking method presented takes account of player strength in that wins over strong players are valued higher than wins over weak players. To account for player strength, we evaluate both direct or first-order wins of players over opponents (i defeats j) and indirect or higher-order wins (i defeats k, who defeats j). A model which derives a composite score for each player, combining both direct and indirect wins, is used to obtain an overall ranking of the competitors.     

A general characterization of the mean field limit for stochastic differential games

The mean field limit of large-population symmetric stochastic differential games is derived in a general setting, with and without common noise, on a finite time horizon. Minimal assumptions are imposed on equilibrium strategies, which may be asymmetric and based on full information. It is shown that approximate Nash equilibria in the n-player games admit certain weak limits as n tends to infinity, and every limit is a weak solution of the mean field game (MFG). Conversely, every weak MFG solution can be obtained as the limit of a sequence of approximate Nash equilibria in the n-player games. Thus, the MFG precisely characterizes the possible limiting equilibrium behavior of the n-player games. Even in the setting without common noise, the empirical state distributions may admit stochastic limits which cannot be described by the usual notion of MFG solution.     

<Emphasis Type="Italic">km</Emphasis>th price sealed-bid auctions with general independent values and equilibrium linear mark-ups

A generalised bidding model is developed to calculate a bidder’s expected profit and auctioners expected revenue/payment for both a General Independent Value and Independent Private Value (IPV) kmth price sealed-bid auction (where the mth bidder wins at the kth bid payment) using a linear (affine) mark-up function. The Common Value (CV) assumption, and highbid and lowbid symmetric and asymmetric First Price Auctions and Second Price Auctions are included as special cases. The optimal n bidder symmetric analytical results are then provided for the uniform IPV and CV models in equilibrium. Final comments concern implications, the assumptions involved and prospects for further research.     

Dynamic linear programming games with risk-averse players

Motivated by situations in which independent agents wish to cooperate in some uncertain endeavor over time, we study dynamic linear programming games, which generalize classical linear production games to multi-period settings under uncertainty. We specifically consider that players may have risk-averse attitudes towards uncertainty, and model this risk aversion using coherent conditional risk measures. For this setting, we study the strong sequential core, a natural extension of the core to dynamic settings. We characterize the strong sequential core as the set of allocations that satisfy a particular finite set of inequalities that depend on an auxiliary optimization model, and then leverage this characterization to establish sufficient conditions for emptiness and non-emptiness. Qualitatively, whereas the strong sequential core is always non-empty when players are risk-neutral, our results indicate that cooperation in the presence of risk aversion is much more difficult. We illustrate this with an application to cooperative newsvendor games, where we find that cooperation is possible when it least benefits players, and may be impossible when it offers more benefit.     

Möbius disjointness for models of an ergodic system and beyond

Given a topological dynamical system (X, T) and an arithmetic function u: ? → ?, we study the strong MOMO property (relatively to u) which is a strong version of u-disjointness with all observable sequences in (X, T). It is proved that, given an ergodic measure-preserving system (Z, \(\mathcal{D}\), к, R),the strong MOMO propertly (relately to u) of a uniquely ergodic midel (X, T)of R yields all other uniquely ergodic midel of R to be u-disjiont. It follows that all uniquely ergodic models of: ergodic unipotent diffeomorphisms on nilmanifolds, discrete spectrum automorphisms, systems given by some substitutions of constant length (including the classical Thue—Viorse and Rudin—Shapiro substitutions), systems determined by Kakutani sequences are Möbius (and Liouville) disjoint. The validity of Sarnak5s conjecture implies the strong MOMO property relatively to μ in all zero entropy systems; in particular, it makes μ-disjointness uniform. The absence of the strong MOMO property in positive entropy systems is discussed and it is proved that, under the Chowla conjecture, a topological system has the strong MOMO property relatively to the Liouville function if and only if its topological entropy is zero.     

Certain Subsets on Which Every Bounded Convex Function Is Continuous

To guarantee every real-valued convex function bounded above on a set is continuous, how ＂thick＂ should the set be？ For a symmetric set A in a Banach space E,the answer of this paper is： Every real-valued convex function bounded above on A is continuous on E if and only if the following two conditions hold： i） spanA has finite co-dimentions and ii） coA has nonempty relative interior. This paper also shows that a subset A C E satisfying every real-valued convex function bounded above on A is continuous on E if （and only if） every real-valued linear functional bounded above on A is continuous on E, which is also equivalent to that every real-valued convex function bounded on A is continuous on E.     

Coordination games on graphs

We introduce natural strategic games on graphs, which capture the idea of coordination in a local setting. We study the existence of equilibria that are resilient to coalitional deviations of unbounded and bounded size (i.e., strong equilibria and k-equilibria respectively). We show that pure Nash equilibria and 2-equilibria exist, and give an example in which no 3-equilibrium exists. Moreover, we prove that strong equilibria exist for various special cases. We also study the price of anarchy (PoA) and price of stability (PoS) for these solution concepts. We show that the PoS for strong equilibria is 1 in almost all of the special cases for which we have proven strong equilibria to exist. The PoA for pure Nash equilbria turns out to be unbounded, even when we fix the graph on which the coordination game is to be played. For the PoA for k-equilibria, we show that the price of anarchy is between \(2(n-1)/(k-1) - 1\) and \(2(n-1)/(k-1)\). The latter upper bound is tight for \(k=n\) (i.e., strong equilibria). Finally, we consider the problems of computing strong equilibria and of determining whether a joint strategy is a k-equilibrium or strong equilibrium. We prove that, given a coordination game, a joint strategy s, and a number k as input, it is co-NP complete to determine whether s is a k-equilibrium. On the positive side, we give polynomial time algorithms to compute strong equilibria for various special cases.     

Improved Strategies for Radial basis Function Methods for Global Optimization

We propose some strategies that can be shown to improve the performance of the radial basis function (RBF) method by Gutmann [J. Global optim. 19(3), 201–227 (2001a)] (Gutmann-RBF) and the RBF method by Regis and Shoemaker [J. Global optim. 31, 153–171 (2005)] (CORS–RBF) on some test problems when they are initialized by symmetric Latin hypercube designs (SLHDs). Both methods are designed for the global optimization of computationally expensive functions with multiple local optima. We demonstrate how the original implementation of Gutmann-RBF can sometimes converge slowly to the global minimum on some test problems because of its failure to do local search. We then propose Controlled Gutmann-RBF (CG-RBF), which is a modification of Gutmann-RBF where the function evaluation point in each iteration is restricted to a subregion of the domain centered around a global minimizer of the current RBF model. By varying the size of this subregion in different iterations, we ensure a better balance between local and global search. Moreover, we propose a complete restart strategy for CG-RBF and CORS-RBF whenever the algorithm fails to make any substantial progress after some threshold number of consecutive iterations. Computational experiments on the seven Dixon and Szegö [Towards Global optimization, pp. 1–13. North-Holland, Amsterdam (1978)] test problems and on nine Schoen [J. Global optim. 3, 133–137 (1993)] test problems indicate that the proposed strategies yield significantly better performance on some problems. The results also indicate that, for some fixed setting of the restart parameters, the two modified RBF algorithms, namely CG-RBF-Restart and CORS-RBF-Restart, are comparable on the test problems considered. Finally, we examine the sensitivity of CG-RBF-Restart and CORS-RBF-Restart to the restart parameters.     

The Sequential Truel

The Sequential Truel is a three-person game which generalizes the simple duel. The players' positions are fixed at the vertices of an equilateral triangle, and they fire, in sequence, until there is only one survivor or until each survivor has fired a pre-specified number of times. The rules of the particular game may or may not permit the tactic of abstention, i.e. firing into the air. Several versions of Sequential Truel (with and without abstention) are examined here. It is found that, often, there is a single equilibrium point which can be called the solution of the truel for rational players. Quite frequently, the poorest marksman of the three has the greatest payoff at this equilibrium point.     

Games with a permission structure - A survey on generalizations and applications

In the field of cooperative games with restricted cooperation, various restrictions on coalition formation are studied. The most studied restrictions are those that arise from restricted communication and hierarchies. This survey discusses several models of hierarchy restrictions and their relation with communication restrictions. In the literature, there are results on game properties, Harsanyi dividends, core stability, and various solutions that generalize existing solutions for TU-games. In this survey, we mainly focus on axiomatizations of the Shapley value in different models of games with a hierarchically structured player set, and their applications. Not only do these axiomatizations provide insight in the Shapley value for these models, but also by considering the types of axioms that characterize the Shapley value, we learn more about different network structures. A central model of games with hierarchies is that of games with a permission structure where players in a cooperative transferable utility game are part of a permission structure in the sense that there are players that need permission from other players before they are allowed to cooperate. This permission structure is represented by a directed graph. Generalizations of this model are, for example, games on antimatroids, and games with a local permission structure. Besides discussing these generalizations, we briefly discuss some applications, in particular auction games and hierarchically structured firms.