Narrow Results

In this paper, the focus is on the role of the municipality, as an enabler of a collaboration between freight forwarders and the municipality in which the consolidation of goods is considered as a means for goods flow improvement in urban freight transportation. We present a cost allocation model that is based on solution concepts from cooperative game theory, for allocating the operational costs associated with the collaboration. It is assumed that the municipality is willing to carry some cost to ensure a stable collaboration for the potential benefits received, e.g., reduced traffic congestion in the city. The model is applied to some illustrative examples, and the cost allocation results are discussed. It is shown that the role of the municipality may be decisive in achieving a stable collaboration between the freight forwarders, and further that the municipality does not necessarily need to contribute to covering the costs.

Cleaning up a polluted river requires coordinated actions among different firms along the river. The key to promoting and enriching the firms’ cooperation is to share the pollution cleanup cost among these firms fairly and reasonably. In this paper, we propose a new cost-sharing scheme, called the entire upstream agents compensation method (the EUAC method for short), for a line-structure river cleanup cost-sharing problem by considering the waste transfer rate for each river segment. On the one hand, we offer a re-allocation scenario in order to implement the EUAC method. On the other hand, to reveal the rationality and stability of this proposed method, we formulate a cooperative cost game for the line-structure river cleanup cost-sharing problem, and show that the EUAC method coincides with the Shapley value of this game and belongs to the core of this game.

This paper introduces a new notion related to the traveling salesperson problem (TSP) — the notion of the TSP ratio. The TSP ratio of a TSP instance I is the sum of the marginal values of the nodes of I divided by the length of the optimal TSP tour on I, where the marginal value of a node i ∈ I is the difference between the length of the optimal tour on I and the length of the optimal tour on I\i. We consider the problem of establishing exact upper and lower bounds on the TSP ratio. To our knowledge, this problem has not been studied previously.

We present a number of cases for which the ratio is never greater than 1. We establish a tight upper bound of 2 on the TSP ratio of any metric TSP. For the TSP on six nodes, we determine the maximum ratio of 1.5 in general, 1.2 for the case of metric TSP, and 10/9 for the geometric TSP in the L₁ metric. We also compute the TSP ratio experimentally for a large number of random TSP instances on small number of points.

The weighted value was introduced by Shapley in 1953 as an asymmetric version of his value. Since then several axiomatizations have been proposed including one by Shapley in 1981 specifically addressed to cost allocation, a context in which weights appear naturally. It was at the occasion of a comment in which he only stated the axioms. The present paper offers a proof of Shapley's statement as well as an alternative set of axioms. It is shown that the value is the unique rule that allocates additional fixed costs fairly: only the players who are concerned contribute to the fixed cost and they contribute in proportion to their weights. A particular attention is given to the case where some players are assigned a zero weight.

In this paper, we explain why the field of cost allocation problems with a coalition structure is a wide and promising unexplored research direction. In particular, we pose some open questions for airport games with a coalition structure.

In this paper we consider a Jackson network of independent service stations. To improve upon the total expected queue length, the stations may redistribute the total arrival rate of customers over all queues. We investigate this situation by means of arrival rate games. These are cooperative TU cost games in which the stations are the players and the total cost of a coalition is linear in the total expected queue length. We show that these games are totally balanced; cooperation is beneficial to all stations. Further, we provide a tailor-made cost allocation rule that belongs to the core of the game.

Briata, F. and Fragnelli, V. [2017] Free-riding in common facility sharing, in Transaction on Computation Collective Intelligence XXVII, pp. 129–138. dealt with the inefficiency and the free-riding situations that may arise from sharing the maintenance cost of a facility among its potential users and from dividing the cost of a check to assess who the users are among the agents that asked for it.They introduced two mechanisms for reducing the free-riding behaviors and considered the possibility that the check provides also information on the level at which the facility is used by each agent.

In this paper, we improve the profitability of the check, introducing a TU-cost game for determining the quota of the total cost assigned to each agent in order to satisfy as many agents as possible. Two solutions are proposed and analyzed and the balancedness of the TU-cost game is studied and characterized.

How to share the cost of an improvement in a condo? In France, as in most European civil law countries, the law does not provide any precise method for answering this question. This vagueness of the law calls for further investigation. Focusing on how to distribute costs that are collectively incurred by a group of players, cooperative game theory is a priori an appropriate framework for dealing with this topic. In this theory, the Shapley value is a widely used cost-sharing method. We analyze the interest of using this concept to solve our problem by considering the case of a three-storey condo. We show that taking into account the legal requirement that any decision concerning improvements be made by a majority of the votes affects the characteristic function of the game. We then identify a pitfall of the Shapley value: it almost never receives an affirmative vote from the co-owner association.