Complements,mollifiers and the propensity to disrupt

Gately [1974] andLittlechild/Vaidya [1976] defined and studied ratio measures of “disruption propensity” of coalitions in ann-person game. We define and study new incremental measures giving rise to a wide variety of “disruption solution” concepts free of various ratio defects and affording advantages of analysis and acceptability in terms of solution specifications. Various “mollifier” and “homomollifier” solution concepts are characterized which appear to be of promising utility.     

Competitive outcomes in the cores of market games

The competitive outcomes of an economic system are known, under quite general conditions, always to lie in the core of the associated cooperative game. It is shown here that every “market game” (i.e., one that arises from an exchange economy with money) can be represented by a “direct market” whose competitive outcomes completely fill up the core. It is also shown that it can be represented by a market having any given core outcome as itsunique competitive outcome, or, more generally, having any given compact convex subset of the core as its full set of competitive outcomes.     

A theorem on the number of Nash equilibria in a bimatrix game

We show that ify is an odd integer between 1 and 2ⁿ ? 1, there is ann × n bimatrix game with exactlyy Nash equilibria (NE). We conjecture that this 2ⁿ ? 1 is a tight upper bound on the number of NEs in a “nondegenerate”n × n game.     

On multi-choice TU games arising from replica of economies

In this paper we derive a multi-choice TU game from r-replica of exchange economy with continuous, concave and monetary utility functions, and prove that the cores of the games converge to a subset of the set of Edgeworth equilibria of exchange economy as r approaches to infinity. We prove that the dominance core of each balanced multi-choice TU game, where each player has identical activity level r, coincides with the dominance core of its corresponding r-replica of exchange economy. We also give an extension of the concept of the cover of the game proposed by Shapley and Shubik (J Econ Theory 1: 9-25, 1969) to multi-choice TU games and derive some sufficient conditions for the nonemptyness of the core of multi-choice TU game by using the relationship among replica economies, multi-choice TU games and their covers.     

On the nucleolus of NTU-games defined by multiple objective linear programs

In this article we derive a class of cooperative games with non-transferable utility from multiple objective linear programs. This is done in order to introduce the nucleolus, a solution concept from cooperative game theory, as a solution to multiple objective linear problems.We show that the nucleolus of such a game is a singleton, which is characterized by inclusion in the least core and the reduced game property. Furthermore the nucleolus satisfies efficiency, anonymity and strategic equivalence.We also present a polynomially bounded algorithm for computation of the nucleolus. Letn be the number of objective functions. The nucleolus is obtained by solving at most2n linear programs. Initially the ideal point is computed by solvingn linear programs. Then a sequence of at mostn linear programs is solved, and the nucleolus is obtained as the unique solution of the last program.Financial support from Nordic Academy for Advanced Study (NorFA) is gratefully acknowledged. Part of this work was done during autumn 1993 at Institute of Finance and Management Science, Norwegian School of Economics and Business Administration.     

The propensity to disrupt and the disruption nucleolus of a characteristic function game

Gately [1974] recently introduced the concept of an individual player's “propensity to disrupt” a payoff vector in a three-person characteristic function game. As a generalisation of this concept we propose the “disruption nucleolus” of ann-person game. The properties and computational possibilities of this concept are analogous to those of the nucleolus itself. Two numerical examples are given.     

On the core: complement-reduced game and max-reduced game

This paper presents two characterizations of the core on the domain of all NTU games. One is based on consistency with respect to “complement-reduced game” and converse consistency with respect to “max-reduced game”. The other is based on consistency with respect to “max-reduced game” and weak converse consistency with respect to “complement-reduced game”. Besides, we introduce an alternative definition of individual rationality, we name conditional individual rationality, which is compatible with non-emptiness. We discuss axiomatic characterizations involving conditional individual rationality for the core.     

Reduced games,consistency, and the core

This paper establishes an axiomatization of the core by means of an internal consistency property with respect to a new reduced game introduced by Moulin (1985). Given a payoff vector chosen by a solution for some game, and given a subgroup of agents, we define thereduced game as that in which each coalition in the subgroup could attain payoffs to its members only if they are compatible with the initial payoffs toall the members outside of the subgroup. The solution isconsistent if it selects the same payoff distribution for the reduced game as initially. We show that consistency together with individual rationality characterizes the core of both transferable and non-transferable utility games.     

Homogeneous games as anti step functions

In this paper the class of homogeneousn-person games “without dummies and steps” is characterized by two algebraic axioms. Each of these games induces a natural vector of lengthn, called incidence vector of the game, and vice versa. A geometrical interpretation of incidence vectors allows to construct all of these games and to enumerate them recursively with respect to the number of persons. In addition an algorithm is defined, which maps each directed game to a minimal representation of a homogeneous game. Moreover both games coincide, if the initial game is homogeneous.     

The algorithm designer versus nature: A game-theoretic approach to information-based complexity

A new setting for analyzing problems in information-based complexity is formulated and discussed. By using concepts from two-person zero-sum game theory, a randomized setting results from defining the nth minimal radius as an infimum over “mixed” strategies of information operators and algorithms. After presenting an example, some general results are developed on the randomized radius and its relationship to average and worst case radii.     

Local strategies and equilibria with an application to the committee decision process

In this paper, a formalization of the idea of “lookingk turns ahead” in the context of an-person non-cooperative game, in which the rules specify a sequence of turns, is considered. At thei-th move, there is a game ofk turns an equilibrium of which gives a behavioral strategy for thei-the move. In general, this strategy is not an equilibrium but is attractive as an explanation of the behavior of experienced players playing a complicated game. As an application of this idea, a committee voting game is analyzed.     

Gray codes in graphs of subsets

Let G(n,k) be a graph whose vertices are the k-element subsets of an n-set represented as n-tuples of “O's” and “1's” with k “1's”. Two such subsets are adjacent if one can be obtained from the other by switching a “O” and a “1” which are in adjacent positions, where the first and nth positions are also considered adjacent. The problem of finding hamiltonian cycles in G(n,k) is discussed. This may be considered a problem of finding “Gray codes” of the k-element subsets of an n-set. It is shown that no such cycle exists if n and k are both even or if k=2 and n?7 and that such a cycle does exist in all other cases where k?5.     

Stochastic Differential Games with Multiple Modes and Applications to Portfolio Optimization

Abstract

We study a zero-sum stochastic differential game with multiple modes. The state of the system is governed by “controlled switching” diffusion processes. Under certain conditions, we show that the value functions of this game are unique viscosity solutions of the appropriate Hamilton–Jacobi–Isaac' system of equations. We apply our results to the analysis of a portfolio optimization problem where the investor is playing against the market and wishes to maximize his terminal utility. We show that the maximum terminal utility functions are unique viscosity solutions of the corresponding Hamilton–Jacobi–Isaac' system of equations.     

Dissections of regular polygons into triangles of equal areas

This paper answers the question, “If a regular polygon withn sides is dissected intom triangles of equal areas, mustm be a multiple ofn?” Forn=3 the answer is “no,” since a triangle can be cut into any positive integral number of triangles of equal areas. Forn=4 the answer is again “no,” since a square can be cut into two triangles of equal areas. However, Monsky showed that a square cannot be dissected into an odd number of triangles of equal areas. We show that ifn is at least 5, then the answer is “yes.” Our approach incorporates the techniques of Thomas, Monsky, and Mead, in particular, the use of Sperner's lemma and non-Archimedean valuations, but also makes use of affine transformations to distort a given regular polygon into one to which those techniques apply.     

Optimal strategies for node selection games on oriented graphs: Skew matrices and symmetric games

In the node selection game Γ_D each of the two players simultaneously selects a node from the oriented graph D. If there is an arc between the selected nodes, then there is a payoff from the “dominated” player to the “dominating” player. We investigate the set of optimal strategies for the players in the node selection game Γ_D. We point out that a classical theorem from game theory relates the dimension of the polytope of optimal strategies for Γ_D to the nullity of certain skew submatrix of the payoff matrix for Γ_D. We show that if D is bipartite (with at least two nodes in each partite set), then an optimal strategy for the node selection game Γ_D is never unique. Our work also implies that if D is a tournament, then there is a unique optimal strategy for each player, a result obtained by Fisher and Ryan [Optimal strategies for a generalized “scissors, paper, and stone” game, Amer. Math. Monthly 99 (1992) 935–942] and independently by Laffond, Laslier, and Le Breton [The bipartisan set of a tournament game, Games Econom. Behav. 5 (1993) 182–201].     

Sequentially two-leveled egalitarianism for TU games: Characterization and application

A new linear value for cooperative transferable utility games is introduced. The recursive definition of the new value for an n-person game involves a sequential process performed at n − 1 stages, applying the value to subgames with a certain size k,1 ? k < n, combining with the rule of two-leveled egalitarianism (additive normalization) in order to guarantee the efficiency property for the new value, sequentially two-leveled egalitarianism, shortly S₂EG value, applied to subgames of size k + 1. The new value will be characterized in various ways. The S₂EG value differs from the Shapley value since, besides efficiency, linearity, and symmetry, it verifies an additional property with respect to so-called scale-dummy player (replacing dummy player property). Consequently, the S₂EG value of a game may be determined as the solidarity value of the per-capita game (incorporating the proportional rule due to different levels of efficiency). Various potential representations of the new value are established. In the application to a land corn production economy, it yields allocations, in which the landlord’s interest coincides with striving for a maximum production level. For economies with the linear production function, not only the unique landlord but also all the workers have incentives to increase the scale of the economy.     

An N-dimensional version of Scarf's example

This paper presents a unification of the contributions of Scarf [Some examples of global instability of competitive equilibrium, Int. Econ. Rev. 1 (1960) 157–172] and Gale [A note on global instability of competitive equilibrium, Nav. Res. Logist. Q. 10 (1963) 81–87] by means of a single class of utility functions. The unification extends Scarf's three-commodity, three-consumer economy to an n-commodity, n-consumer economy. We find that the stability of the extended economy depends on whether the law of demand for exchange economies, i.e., downward sloping excess demand, holds or not. Moreover, it is seen that there is a transition from instability to stability as substitution effect increases or as the desire of each consumer for his own commodity decreases.     

n-Simple theories

The main topic of this paper is the investigation of generalized amalgamation properties for simple theories. That is, we are trying to answer the question of when a simple theory has the property of n-dimensional amalgamation, where two-dimensional amalgamation is the Independence Theorem for simple theories. We develop the notions of strong n-simplicity and n-simplicity for 1≤n≤ω, where both “1-simple” and “strongly 1-simple” are the same as “simple”. For strong n-simplicity, we present examples of simple unstable theories in each subclass and prove a characteristic property of strong n-simplicity in terms of strong n-dividing, a strengthening of the dependence relation called dividing in simple theories. We prove a strong three-dimensional amalgamation property for strongly 2-simple theories, and, under an additional assumption, a strong (n+1)-dimensional amalgamation property for strongly n-simple theories. In the last section of the paper we comment on why strong n-simplicity is called strong.     

Rectilinear line segment intersection,layered segment trees,and dynamization

The aim of the present paper is to provide an efficient solution to the following problem: “Given a family of n rectilinear line segments in two-space report all intersections in the family with a query consisting of an arbitrary rectilinear line segment.” We provide an algorithm which takes O(nlog₂n) preprocessing time, o(nlog₂n) space and O(log₂n + k) query time, where k is the number of reported intersections. This solution serves to introduce a powerful new data structure, the layered segment tree, which is of independent interest. Second it yields, by way of recent dynamization techniques, a solution to the on-line version of the above problem, that is the operations INSERT and DELETE and QUERY with a line segment are allowed. Third it also yields a new nonscanning solution to the batched version of the above problem. Finally we apply these techniques to the problem obtained by replacing “line segment” by “rectangle” in the above problem, giving an efficient solution in this case also.     

The solution of the soccer “dream league” game

On January 5, 1996, Maariv, one of the two leading daily newspapers in Israel, announced “The Dream League” game. Every participant in this game was required to “purchase” from a pool of all the soccer players in the Israeli National League, a team which according to his judgment would be chosen as the best team at the end of the season. Purchasing the players was subject to a given budget and to several other constraints. After the soccer season was over, we were requested by Maariv to find the optimal “Dream Team”.The problem of finding the optimal team is shown to be a generalized version of the well-known knapsack problem. It is formulated as an integer program and solved to optimality by the software NAG. Evidently, the optimal Dream Team is much better (in terms of the total cumulative grade) than the actual winning team chosen by the readers of Maariv. A possible heuristic procedure for solving the game in larger settings is also discussed.