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.     

On the structure of hereditary classes of graphs

A class of graphs is hereditary if it is closed under taking induced subgraphs. Classes associated with graph representations have “composition sequences” and we show that this concept is equivalent to a notion of “amalgamation” which generalizes disjoint union of graphs. We also discuss how general hereditary classes of graphs are built up from representation classes.     

Phenomena in Inverse Stackelberg Games,Part 1: Static Problems

Games are considered in which the role of the players is a hierarchical one. Some players behave as leaders, others as followers. Such games are named after Stackelberg. In the current paper, a special type of these games is considered, known in the literature as inverse Stackelberg games. In such games, the leader (or: leaders) announces his strategy as a mapping from the follower (or: followers) decision space into his own decision space. Arguments for studying such problems are given. The routine way of analysis, leading to a study of composed functions, is not very fruitful. Other approaches are given, mainly by studying specific examples. Phenomena in problems with more than one leader and/or follower are studied within the context of the inverse Stackelberg concept. As a side issue, expressions like “two captains on a ship” and “divide and conquer” are given a mathematical foundation.     

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.     

Non-cooperative monopolistic games and monopolistic market games

A class of non-cooperative games is discussed in which one player (“the monopolist”) by choosing his strategy restricts the other players to subsets of their strategy sets. Examples of such games in various fields are given. In particular it is shown that some very important economic situations fall within this class of games. A solution concept is defined and sufficient conditions for its existence are derived. The question of the advantages a player derives from being a monopolist is raised and conditions are derived for him to benefit from being a monopolist.     

Global games

Global games are real-valued functions defined on partitions (rather than subsets) of the set of players. They capture “public good” aspects of cooperation, i.e., situations where the payoff is naturally defined for all players (“the globe”) together, as is the case with issues of environmental clean-up, medical research, and so forth. We analyze the more general concept of lattice functions and apply it to partition functions, set functions and the interrelation between the two. We then use this analysis to define and characterize the Shapley value and the core of global games.     

A note on disjoint arborescences

Recently Kamiyama, Katoh, and Takizawa have shown a theorem on packing arc-disjoint arborescences that is a proper extension of Edmonds’ theorem on disjoint spanning branchings. We show a further extension of their theorem, which makes clear an essential rôle of a reachability condition played in the theorem. The right concept required for the further extension is “convexity” instead of “reachability”.     

The prenucleolus and the prekernel for games with communication structures

It is well-known that the prekernel on the class of TU games is uniquely determined by non-emptiness, Pareto efficiency (EFF), covariance under strategic equivalence (COV), the equal treatment property, the reduced game property (RGP), and its converse. We show that the prekernel on the class of TU games restricted to the connected coalitions with respect to communication structures may be axiomatized by suitably generalized axioms. Moreover, it is shown that the prenucleolus, the unique solution concept on the class of TU games that satisfies singlevaluedness, COV, anonymity, and RGP, may be characterized by suitably generalized versions of these axioms together with a property that is called “independence of irrelevant connections”. This property requires that any element of the solution to a game with communication structure is an element of the solution to the game that allows unrestricted cooperation in all connected components, provided that each newly connected coalition is sufficiently charged, i.e., receives a sufficiently small worth. Both characterization results may be extended to games with conference structures.     

Systems of conservation laws of mixed type

A local theory of weak solutions of first-order nonlinear systems of conservation laws is presented. In the systems considered, two of the characteristic speeds become complex for some achieved values of the dependent variable. The transonic “small disturbance” equation is an example of this class of systems. Some familiar concepts from the purely hyperbolic case are extended to such systems of mixed type, including genuine nonlinearity, classification of shocks into distinct fields and entropy inequalities. However, the associated entropy functions are not everywhere locally convex, shock and characteristic speeds are not bounded in the usual sense, and closed loops and disjoint segments are possible in the set of states which can be connected to a given state by a shock. With various assumptions, we show (1) that the state on one side of a shock plus the shock speed determine the state on the other side uniquely, as in the hyperbolic case; (2) that the “small disturbance” equation is a local model for a class of such systems; and (3) that entropy inequalities and/or the existence of viscous profiles can still be used to select the “physically relevant” weak solution of such a system.     

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.     

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.     

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

Strategy-indifferent games of best choice

The game of best choice (or “secretary problem”) is a model for making an irrevocable decision among a fixed number of candidate choices that are presented sequentially in random order, one at a time. Because the classically optimal solution is known to reject an initial sequence of candidates, a paradox emerges from the fact that candidates have an incentive to position themselves immediately after this cutoff which challenges the assumption that candidates arrive in uniformly random order.One way to resolve this is to consider games for which every (reasonable) strategy results in the same probability of success. In this work, we classify these “strategy-indifferent” games of best choice. It turns out that the probability of winning such a game is essentially the reciprocal of the expected number of left-to-right maxima in the full collection of candidate rank orderings. We present some examples of these games based on avoiding permutation patterns of size 3, which involves computing the distribution of left-to-right maxima in each of these pattern classes.     

A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications

Coalitional games raise a number of important questions from the point of view of computer science, key among them being how to represent such games compactly, and how to efficiently compute solution concepts assuming such representations. Marginal contribution nets (MC‐nets), introduced by Ieong and Shoham, are one of the simplest and most influential representation schemes for coalitional games. MC‐nets are a rulebased formalism, in which rules take the form pattern → value, where “pattern ” is a Boolean condition over agents, and “value ” is a numeric value. Ieong and Shoham showed that, for a class of what we will call “basic” MC‐nets, where patterns are constrained to be a conjunction of literals, marginal contribution nets permit the easy computation of solution concepts such as the Shapley value. However, there are very natural classes of coalitional games that require an exponential number of such basic MC‐net rules. We present read‐once MC‐nets, a new class of MC‐nets that is provably more compact than basic MC‐nets, while retaining the attractive computational properties of basic MC‐nets. We show how the techniques we develop for read‐once MC‐nets can be applied to other domains, in particular, computing solution concepts in network flow games on series‐parallel networks (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Time traps in supply chains: Is optimal still good enough?

Operations Researchers support Supply Chain Management and Supply Chain Planning by developing adequate mathematical optimization models and providing suitable solution procedures. In this paper we discuss what adequate could mean. Therefore, we may ask several questions concerning “optimality” in Supply Chain Planning under causal and temporal uncertainty: What is an optimal solution? When is it optimal? For how long is it optimal? How should the design of a supply chain be changed when conditions and requirements ask for new structures? In particular, we discuss new approaches to Supply Chain Planning in order to give an optimal transformation from an initial solution over multiple periods to a desired one rather than just specifying an optimal snapshot solution. Time and uncertainty are the factors triggering the whole discussion. In particular, several flaws often found when dealing with these factors result in so-called “time traps”. We look at the impact of recent technological developments like the Internet of Things or Industry 4.0 on operational supply chain planning and control, and we show how online optimization can help to cope with real-time challenges. Moreover, we re-coin the concept of risk in the realm of Supply Chain Planning. Here the question is how to measure supply chain specific risks and how to incorporate them “adequately” into mathematical models.     

“Procedural” values for cooperative games

This paper introduces a new notion of a “procedural” value for cooperative TU games. A procedural value is determined by an underlying procedure of sharing marginal contributions to coalitions formed by players joining in random order. We consider procedures under which players can only share their marginal contributions with their predecessors in the ordering, and study the set of all resulting values. The most prominent procedural value is, of course, the Shapley value obtaining under the simplest procedure of every player just retaining his entire marginal contribution. But different sharing rules lead to other interesting values, including the “egalitarian solution” and the Nowak and Radzik “solidarity value”. All procedural values are efficient, symmetric and linear. Moreover, it is shown that these properties together with two very natural monotonicity postulates characterize the class of procedural values. Some possible modifications and generalizations are also discussed. In particular, it is shown that dropping one of monotonicity axioms is equivalent to allowing for sharing marginal contributions with both predecessors and successors in the ordering.     

Three hierarchies of simple games parameterized by “resource” parameters

This paper contributes to the program of numerical characterization and classification of simple games outlined in the classic monograph of von Neumann and Morgenstern. We suggest three possible ways to classify simple games beyond the classes of weighted and roughly weighted games. To this end we introduce three hierarchies of games and prove some relationships between their classes. We prove that our hierarchies are true (i.e., infinite) hierarchies. In particular, they are strict in the sense that more of the key “resource” (which may, for example, be the size or structure of the “tie-breaking” region where the weights of the different coalitions are considered so close that we are allowed to specify either winningness or nonwinningness of the coalition) yields the flexibility to capture strictly more games.     

Correlated equilibria in some classes of two-person games

A correlated equilibrium in a two-person game is “good” if for everyNash equilibrium there is a player who prefers the correlated equilibrium to theNash equilibrium. If a game is “best-response equivalent” to a two-person zero-sum game, then it has no good correlated equilibria. But games which are “almost strictly competitive” or “order equivalent” to a two-person zero-sum game may have good correlated equilibria.     

Advantageous strategies in differential games for a class of suboptimal control laws

This paper deals with suboptimal control policies in differential games. Sufficient conditions for advantageous strategies of either player are examined for a linear-quadratic game in which the players are constrained to use suboptimal control laws of specified form. The concept of a “bargaining matrix” is employed. Specific scalar and vector examples are included to illustrate the theory.