“Optimistic” weighted Shapley rules in minimum cost spanning tree problems

We introduce optimistic weighted Shapley rules in minimum cost spanning tree problems. We define them as the weighted Shapley values of the optimistic game v⁺ introduced in Bergantiños and Vidal-Puga [Bergantiños, G., Vidal-Puga, J.J., forthcoming. The optimistic TU game in minimum cost spanning tree problems. International Journal of Game Theory. Available from: <http://webs.uvigo.es/gbergant/papers/cstShapley.pdf>]. We prove that they are obligation rules [Tijs, S., Branzei, R., Moretti, S., Norde, H., 2006. Obligation rules for minimum cost spanning tree situations and their monotonicity properties. European Journal of Operational Research 175, 121–134].     

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

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

A branch and bound algorithm for the robust spanning tree problem with interval data

The robust spanning tree problem is a variation, motivated by telecommunications applications, of the classic minimum spanning tree problem. In the robust spanning tree problem edge costs lie in an interval instead of having a fixed value.Interval numbers model uncertainty about the exact cost values. A robust spanning tree is a spanning tree whose total cost minimizes the maximum deviation from the optimal spanning tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and is used to drive optimization.In this paper a branch and bound algorithm for the robust spanning tree problem is proposed. The method embeds the extension of some results previously presented in the literature and some new elements, such as a new lower bound and some new reduction rules, all based on the exploitation of some peculiarities of the branching strategy adopted.Computational results obtained by the algorithm are presented. The technique we propose is up to 210 faster than methods recently appeared in the literature.     

The minimum cost shortest-path tree game

A minimum cost shortest-path tree is a tree that connects the source with every node of the network by a shortest path such that the sum of the cost (as a proxy for length) of all arcs is minimum. In this paper, we adapt the algorithm of Hansen and Zheng (Discrete Appl. Math. 65:275?C284, 1996) to the case of acyclic directed graphs to find a minimum cost shortest-path tree in order to be applied to the cost allocation problem associated with a cooperative minimum cost shortest-path tree game. In addition, we analyze a non-cooperative game based on the connection problem that arises in the above situation. We prove that the cost allocation given by an ??à la?? Bird rule provides a core solution in the former game and that the strategies that induce those payoffs in the latter game are Nash equilibrium.     

A characterization of the folk rule for multi-source minimal cost spanning tree problems

In this paper we provide an axiomatic characterization of the folk rule for minimum cost spanning tree problems with multiple sources. The properties we need are: cone-wise additivity, cost monotonicity, symmetry, isolated agents, and equal treatment of source costs.     

Obligation rules for minimum cost spanning tree situations and their monotonicity properties

We consider the class of Obligation rules for minimum cost spanning tree situations. The main result of this paper is that such rules are cost monotonic and induce also population monotonic allocation schemes. Another characteristic of Obligation rules is that they assign to a minimum cost spanning tree situation a vector of cost contributions which can be obtained as product of a double stochastic matrix with the cost vector of edges in the optimal tree provided by the Kruskal algorithm. It turns out that the Potters value (P-value) is an element of this class.     

Strong stability of Nash equilibria in load balancing games

We study strong stability of Nash equilibria in load balancing games of m(m 2)identical servers,in which every job chooses one of the m servers and each job wishes to minimize its cost,given by the workload of the server it chooses.A Nash equilibrium(NE)is a strategy profile that is resilient to unilateral deviations.Finding an NE in such a game is simple.However,an NE assignment is not stable against coordinated deviations of several jobs,while a strong Nash equilibrium(SNE)is.We study how well an NE approximates an SNE.Given any job assignment in a load balancing game,the improvement ratio(IR)of a deviation of a job is defined as the ratio between the pre-and post-deviation costs.An NE is said to be aρ-approximate SNE(ρ1)if there is no coalition of jobs such that each job of the coalition will have an IR more thanρfrom coordinated deviations of the coalition.While it is already known that NEs are the same as SNEs in the 2-server load balancing game,we prove that,in the m-server load balancing game for any given m 3,any NE is a(5/4)-approximate SNE,which together with the lower bound already established in the literature yields a tight approximation bound.This closes the final gap in the literature on the study of approximation of general NEs to SNEs in load balancing games.To establish our upper bound,we make a novel use of a graph-theoretic tool.     

A generalization of obligation rules for minimum cost spanning tree problems

Tijs et al. [23] introduce the family of obligation rules for minimum cost spanning tree problems. We give a generalization of such family. We prove that our family coincides with the set of rules satisfying an additivity property and a cost monotonicity property. We also provide two new characterizations for the family of obligation rules using the previous properties. In the first one, we add a property of separability; and in the second one, we add core selection.     

A vertex oriented approach to the equal remaining obligations rule for minimum cost spanning tree situations

In this paper, we consider spanning tree situations, where players want to be connected to a source as cheap as possible. These situations involve the construction of a spanning tree with the minimum cost as well as the allocation of the cost of this minimum cost spanning tree among its users in a fair way. Feltkamp, Muto and Tijs 1994 introduced the equal remaining obligations rule to solve the cost allocation problem in these situations. Recently, it has been shown that the equal remaining obligations rule satisfies many appealing properties and can be obtained with different approaches. In this paper, we provide a new approach to obtain the equal remaining obligations rule. Specifically, we show that the equal remaining obligations rule can be obtained as the average of the cost allocations provided by a vertex oriented construct-and-charge procedure for each order of players.     

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.     

A new rule for source connection problems

In this paper we study situations where a group of agents require a service that can only be provided from a source, the so-called source connection problems. These problems contain the standard fixed tree, the classical minimum spanning tree and some other related problems such as the k-hop, the degree constrained and the generalized minimum spanning tree problems among others. Our goal is to divide the cost of a network among the agents. To this end, we introduce a rule which will be referred to as a painting rule because it can be interpreted by means of a story about painting. Some meaningful properties in this context and a characterization of the rule are provided.     

最小费用k度限制树对策

本在Glover—Klingman算法及最小费用支撑树对策的基础上，讨论了最小费用k度限制树对策问题．利用威胁、旁支付理论制订了两种规则，并利用优超、策略等价理论分别给出了在这两种规则下最小费用k度限制树对策核心中的解，从而证明了在这两种规则下其核心非空．     

Realizing fair outcomes in minimum cost spanning tree problems through non-cooperative mechanisms

In the context of minimum cost spanning tree problems, we present a bargaining mechanism for connecting all agents to the source and dividing the cost among them. The basic idea is very simple: we ask each agent the part of the cost he is willing to pay for an arc to be constructed. We prove that there exists a unique payoff allocation associated with the subgame perfect Nash equilibria of this bargaining mechanism. Moreover, this payoff allocation coincides with the rule defined in Bergantiños and Vidal-Puga [Bergantiños, G., Vidal-Puga, J.J., 2007a. A fair rule in minimum cost spanning tree problems. Journal of Economic Theory 137, 326–352].     

Merge-proofness in minimum cost spanning tree problems

In the context of cost sharing in minimum cost spanning tree problems, we introduce a property called merge-proofness. This property says that no group of agents can be better off claiming to be a single node. We show that the sharing rule that assigns to each agent his own connection cost (the Bird rule) satisfies this property. Moreover, we provide a characterization of the Bird rule using merge-proofness.     

On the core and nucleolus of directed acyclic graph games

We introduce directed acyclic graph (DAG) games, a generalization of standard tree games, to study cost sharing on networks. This structure has not been previously analyzed from a cooperative game theoretic perspective. Every monotonic and subadditive cost game—including monotonic minimum cost spanning tree games—can be modeled as a DAG-game. We provide an efficiently verifiable condition satisfied by a large class of directed acyclic graphs that is sufficient for the balancedness of the associated DAG-game. We introduce a network canonization process and prove various structural results for the core of canonized DAG-games. In particular, we characterize classes of coalitions that have a constant payoff in the core. In addition, we identify a subset of the coalitions that is sufficient to determine the core. This result also guarantees that the nucleolus can be found in polynomial time for a large class of DAG-games.     

On the computation of the nucleolus of a cooperative game

We consider classes of cooperative games. We show that we can efficiently compute an allocation in the intersection of the prekernel and the least core of the game if we can efficiently compute the minimum excess for any given allocation. In the case where the prekernel of the game contains exactly one core vector, our algorithm computes the nucleolus of the game. This generalizes both a recent result by Kuipers on the computation of the nucleolus for convex games and a classical result by Megiddo on the nucleolus of standard tree games to classes of more general minimum cost spanning tree games. Our algorithm is based on the ellipsoid method and Maschler's scheme for approximating the prekernel. Received February 2000/Final version April 2001     

Minimum cost forest games

In this paper we consider a generalization of the minimum cost spanning tree game. The generalized model allows for more than one supplier, where each supplier offers a different type of service to the customers and each customer specifies a non-empty subset of these suppliers to which he wishes to be connected. We show that the core of such a game may be empty, but that it is always non-empty if there is at least one customer who wants to be connected to all suppliers. Furthermore, the core is always non-empty if there are at most two suppliers.     

Upper and lower bounding procedures for the minimum caterpillar spanning problem

A spanning caterpillar in a graph is a tree composed by a path such that all vertices not in the path are leaves. In the Minimum Spanning Caterpillar Problem (MSCP) each edge has two costs: a path cost when it belongs to the path and a connection cost when it is incident to a leaf. The goal is to find a spanning caterpillar minimizing the sum of all path and connection costs. In this paper we formulate the as a minimum Steiner arborescence problem. This reduction is the basis for the development of an efficient branch-and-cut algorithm for the MSCP. We als developed a GRASP heuristic to generate primal bounds. Experiments carried out on instances adapted from TSPLIB 2.1 revealed that the exact algorithm is capable to solve to optimality instances with up to 300 vertices in reasonable time. They also showed that our heuristic yields very high quality solutions.     

Finding all pure strategy Nash equilibria in a planar location game

In this paper, we deal with a planar location-price game where firms first select their locations and then set delivered prices in order to maximize their profits. If firms set the equilibrium prices in the second stage, the game is reduced to a location game for which pure strategy Nash equilibria are studied assuming that the marginal delivered cost is proportional to the distance between the customer and the facility from which it is served. We present characterizations of local and global Nash equilibria. Then an algorithm is shown in order to find all possible Nash equilibrium pairs of locations. The minimization of the social cost leads to a Nash equilibrium. An example shows that there may exist multiple Nash equilibria which are not minimizers of the social cost.