Proof of permutationally convexity of MCSF games

Granot and Huberman (1982) showed that minimum cost spanning tree (MCST) games are permutationally convex (PC). Recently, Rosenthal (1987) gave an extension of MCST games to minimum cost spanning forest (MCSF) games and showed these games have nonempty cores. In this note we show any MCSF game is a PC game.     

Minimum cost spanning tree games

We consider the problem of cost allocation among users of a minimum cost spanning tree network. It is formulated as a cooperative game in characteristic function form, referred to as a minimum cost spanning tree (m.c.s.t.) game. We show that the core of a m.c.s.t. game is never empty. In fact, a point in the core can be read directly from any minimum cost spanning tree graph associated with the problem. For m.c.s.t. games with efficient coalition structures we define and construct m.c.s.t. games on the components of the structure. We show that the core and the nucleolus of the original game are the cartesian products of the cores and the nucleoli, respectively, of the induced games on the components of the efficient coalition structure.This paper is a revision of [4].     

Dominating set games

In this paper, we study cooperative cost games arising from domination problems on graphs. We introduce three games to model the cost allocation problem and we derive a necessary and sufficient condition for the balancedness of all three games.     

On the core of cost-revenue games: Minimum cost spanning tree games with revenues

In this paper, we analyze cost sharing problems arising from a general service by explicitly taking into account the generated revenues. To this cost-revenue sharing problem, we associate a cooperative game with transferable utility, called cost-revenue game. By considering cooperation among the agents using the general service, the value of a coalition is defined as the maximum net revenues that the coalition may obtain by means of cooperation. As a result, a coalition may profit from not allowing all its members to get the service that generates the revenues. We focus on the study of the core of cost-revenue games. Under the assumption that cooperation among the members of the grand coalition grants the use of the service under consideration to all its members, it is shown that a cost-revenue game has a nonempty core for any vector of revenues if, and only if, the dual game of the cost game has a large core. Using this result, we investigate minimum cost spanning tree games with revenues. We show that if every connection cost can take only two values (low or high cost), then, the corresponding minimum cost spanning tree game with revenues has a nonempty core. Furthermore, we provide an example of a minimum cost spanning tree game with revenues with an empty core where every connection cost can take only one of three values (low, medium, or high cost).     

Optimal cost sharing for capacitated facility location games

We consider cost sharing for a class of facility location games, where the strategy space of each player consists of the bases of a player-specific matroid defined on the set of resources. We assume that resources have nondecreasing load-dependent costs and player-specific delays. Our model includes the important special case of capacitated facility location problems, where players have to jointly pay for opened facilities. The goal is to design cost sharing protocols so as to minimize the resulting price of anarchy and price of stability. We investigate two classes of protocols: basic protocols guarantee the existence of at least one pure Nash equilibrium and separable protocols additionally require that the resulting cost shares only depend on the set of players on a resource. We find optimal basic and separable protocols that guarantee the price of stability/price of anarchy to grow logarithmically/linearly in the number of players. These results extend our previous results (cf. von Falkenhausen & Harks, 2013), where optimal basic and separable protocols were given for the case of symmetric matroid games without delays.     

Evolutionary games

This paper deals with a mathematical game. As the name implies, the game concept is formulated with biological evolution in mind. An evolutionary game differs from the usual game concepts in that the players cannot choose their strategies. Rather, the strategies used by the players are handed down from generation to generation. It is the survival characteristics of a strategy that determine the outcome of the evolutionary game. Players interact and receive payoffs according to the strategies they are using. These interactions, in turn, determine the fitness of players using a given strategy. The survival characteristics of strategy are determined directly from the fitness functions. Necessary conditions for determining an evolutionarily stable strategy are developed here for a continuous game. Results are illustrated with an example.Dedicated to G. LeitmannThis work was supported by NSF Grant No. INT-82-10803 and The University of Western Australia (Visiting Fellowship, Department of Mathematics, 1983).     

Economic lot-sizing games

In this paper we introduce a new class of OR games: economic lot-sizing (ELS) games. There are a number of retailers that have a known demand for a fixed number of periods. To satisfy demand the retailers order products at the same manufacturer. By placing joint orders instead of individual orders, costs can be reduced and a cooperative game arises. In this paper we show that ELS games are balanced. Furthermore, we show that two special classes of ELS games are concave.     

Shortest path games

We study cooperative games that arise from the problem of finding shortest paths from a specified source to all other nodes in a network. Such networks model, among other things, efficient development of a commuter rail system for a growing metropolitan area. We motivate and define these games and provide reasonable conditions for the corresponding rail application. We show that the core of a shortest path game is nonempty and satisfies the given conditions, but that the Shapley value for these games may lie outside the core. However, we show that the shortest path game is convex for the special case of tree networks, and we provide a simple, polynomial time formula for the Shapley value in this case. In addition, we extend our tree results to the case where users of the network travel to nodes other than the source. Finally, we provide a necessary and sufficient condition for shortest paths to remain optimal in dynamic shortest path games, where nodes are added to the network sequentially over time.     

Complete stability of noncooperative games

This paper is concerned with a class of noncooperative games ofn players that are defined byn reward functions which depend continuously on the action variables of the players. This framework provides a realistic model of many interactive situations, including many common models in economics, sociology, engineering, and political science. The concept of Nash equilibrium is a suitable companion to such models.A variety of different sufficient conditions for existence, uniqueness, and stability of a Nash equilibrium point have been previously proposed. By sharpening the noncooperative aspect of the framework (which is really only implicit in the original framework), this paper attempts to isolate one set of natural conditions that are sufficient for existence, uniqueness, and stability. It is argued thatl quasicontraction is such a natural condition. The concept of complete stability is introduced to reflect the full character of noncooperation. It is then shown that, in the linear case, the condition ofl quasicontraction is both necessary and sufficient for complete stability.This research was supported by the Air Force Office of Scientific Research under Grant No. AFOSR 77-3141 and by the National Science Foundation under Grant No. GK18748.     

Equilibria of two-sided matching games with common preferences

Problems of matching have long been studied in the operations research literature (assignment problem, secretary problem, stable marriage problem). All of these consider a centralized mechanism whereby a single decision maker chooses a complete matching which optimizes some criterion. This paper analyzes a more realistic scenario in which members of the two groups (buyers–sellers, employers–workers, males–females) randomly meet each other in pairs (interviews, dates) over time and form couples if there is mutual agreement to do so. We assume members of each group have common preferences over members of the other group. Generalizing an earlier model of Alpern and Reyniers [Alpern, S., Reyniers, D.J., 2005. Strategic mating with common preferences. J. Theor. Biol. 237, 337–354], we assume that one group (called males) is r   times larger than the other, r?1$r?1$. Thus all females, but only 1/r$1/r$ of the males, end up matched. Unmatched males have negative utility -c$-c$. We analyze equilibria of this matching game, depending on the parameters r   and c$c$. In a region of (r,c)$(r\text{,}c)$ space with multiple equilibria, we compare these, and analyze their ‘efficiency’ in several respects. This analysis should prove useful for designers of matching mechanisms who have some control over the sex ratio (e.g. by capping numbers of males at a ‘singles event’or by having ‘ladies free’ nights) or the nonmating cost c (e.g. tax benefits to married couples).     

Cost allocation games with information costs

We propose a simple model which embeds cost allocation games into a richer structure to take into account that information on costs can be itself costly. The model is an outgrowth of experience on cost allocation for consortia of municipalities dealing with garbage collection.The authors thank an anonymous referee for having pointed out a mistake in the previous version of Lemma 1     

An equitable solution for multicriteria bargaining games

In this paper we study bargaining models where the agents consider several criteria to evaluate the results of the negotiation process. We propose a new solution concept for multicriteria bargaining games based on the distance to a utopian minimum level vector. This solution is a particular case of the class of the generalized leximin solutions and can be characterized as the solution of a finite sequence of minimax programming problems.     

Weighted search games

In this paper we shall deal with search games in which the strategic situation is developed on a lattice. The main characteristic of these games is that the points in each column of the lattice have a specific associated weight which directly affects the payoff function. Thus, the points in different columns represent points of different strategic value. We solve three different types of games. The first involves search, ambush and mixed situations, the second is a search and inspection game and the last is related to the accumulative games.     

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

Distributed consensus in noncooperative inventory games

This paper deals with repeated nonsymmetric congestion games in which the players cannot observe their payoffs at each stage. Examples of applications come from sharing facilities by multiple users. We show that these games present a unique Pareto optimal Nash equilibrium that dominates all other Nash equilibria and consequently it is also the social optimum among all equilibria, as it minimizes the sum of all the players’ costs. We assume that the players adopt a best response strategy. At each stage, they construct their belief concerning others probable behavior, and then, simultaneously make a decision by optimizing their payoff based on their beliefs. Within this context, we provide a consensus protocol that allows the convergence of the players’ strategies to the Pareto optimal Nash equilibrium. The protocol allows each player to construct its belief by exchanging only some aggregate but sufficient information with a restricted number of neighbor players. Such a networked information structure has the advantages of being scalable to systems with a large number of players and of reducing each player’s data exposure to the competitors.     

A value for multichoice games

A multichoice game is a generalization of a cooperative TU game in which each player has several activity levels. We study the solution for these games proposed by Van Den Nouweland et al. (1995) [Van Den Nouweland, A., Potters, J., Tijs, S., Zarzuelo, J.M., 1995. Cores and related solution concepts for multi-choice games. ZOR-Mathematical Methods of Operations Research 41, 289–311]. We show that this solution applied to the discrete cost sharing model coincides with the Aumann-Shapley method proposed by Moulin (1995) [Moulin, H., 1995. On additive methods to share joint costs. The Japanese Economic Review 46, 303–332]. Also, we show that the Aumann-Shapley value for continuum games can be obtained as the limit of multichoice values for admissible convergence sequences of multichoice games. Finally, we characterize this solution by using the axioms of balanced contributions and efficiency.     

Infrastructure security games

Infrastructure security against possible attacks involves making decisions under uncertainty. This paper presents game theoretic models of the interaction between an adversary and a first responder in order to study the problem of security within a transportation infrastructure. The risk measure used is based on the consequence of an attack in terms of the number of people affected or the occupancy level of a critical infrastructure, e.g. stations, trains, subway cars, escalators, bridges, etc. The objective of the adversary is to inflict the maximum damage to a transportation network by selecting a set of nodes to attack, while the first responder (emergency management center) allocates resources (emergency personnel or personnel-hours) to the sites of interest in an attempt to find the hidden adversary. This paper considers both static and dynamic, in which the first responder is mobile, games. The unique equilibrium strategy pair is given in closed form for the simple static game. For the dynamic game, the equilibrium for the first responder becomes the best patrol policy within the infrastructure. This model uses partially observable Markov decision processes (POMDPs) in which the payoff functions depend on an exogenous people flow, and thus, are time varying. A numerical example illustrating the algorithm is presented to evaluate an equilibrium strategy pair.     

Pure subgame-perfect equilibria in free transition games

We consider a class of stochastic games, where each state is identified with a player. At any moment during play, one of the players is called active. The active player can terminate the game, or he can announce any player, who then becomes the active player. There is a non-negative payoff for each player upon termination of the game, which depends only on the player who decided to terminate. We give a combinatorial proof of the existence of subgame-perfect equilibria in pure strategies for the games in our class.     

Robust equilibria in location games

In the framework of spatial competition, two or more players strategically choose a location in order to attract consumers. It is assumed standardly that consumers with the same favorite location fully agree on the ranking of all possible locations. To investigate the necessity of this questionable and restrictive assumption, we model heterogeneity in consumers’ distance perceptions by individual edge lengths of a given graph. A profile of location choices is called a “robust equilibrium” if it is a Nash equilibrium in several games which differ only by the consumers’ perceptions of distances. For a finite number of players and any distribution of consumers, we provide a complete characterization of robust equilibria and derive structural conditions for their existence. Furthermore, we discuss whether the classical observations of minimal differentiation and inefficiency are robust phenomena. Thereby, we find strong support for an old conjecture that in equilibrium firms form local clusters.     

Distributed computation of Pareto solutions inn-player games

The problem of computing Pareto optimal solutions with distributed algorithms is considered inn-player games. We shall first formulate a new geometric problem for finding Pareto solutions. It involves solving joint tangents for the players' objective functions. This problem can then be solved with distributed iterative methods, and two such methods are presented. The principal results are related to the analysis of the geometric problem. We give conditions under which its solutions are Pareto optimal, characterize the solutions, and prove an existence theorem. There are two important reasons for the interest in distributed algorithms. First, they can carry computational advantages over centralized schemes. Second, they can be used in situations where the players do not know each others' objective functions.