Measuring and rewarding flexibility in collaborative distribution,including two-partner coalitions

Horizontal collaboration among shippers is gaining traction as a way to increase logistic efficiency. The total distribution cost of a logistic coalition is generally between 9% and 30% lower than the sum of costs of each partner distributing separately. However, the coalition gain is highly dependent on the flexibility that each partner allows in its delivery terms. Flexible delivery dates, flexible order sizes, order splitting rules, etc., allow the coalition to exploit more opportunities for optimization and create better and cheaper distribution plans.     

The core of an economy with a common pool resource: A partition function form approach

In this paper we consider a model of an economy with a common pool resource. Under decreasing returns to scale, it is well-known that no Nash equilibrium attains Pareto efficiency. We examine whether it is possible to achieve Pareto efficiency and avoid the tragedy of the commons through cooperation among players. For that purpose, we use the notion of a game in partition function form. Whether or not the core exists depends crucially on the expectations of each coalition regarding the coalition formation of the outsiders. If each coalition has pessimistic expectations, then the core always exists, while if it has optimistic expectations, the core may be empty. Received: January 1998/Final version: November 1998     

Forms of representation for simple games: Sizes,conversions and equivalences

Simple games are cooperative games in which the benefit that a coalition may have is always binary, i.e., a coalition may either win or loose. This paper surveys different forms of representation of simple games, and those for some of their subfamilies like regular games and weighted games. We analyze the forms of representations that have been proposed in the literature based on different data structures for sets of sets. We provide bounds on the computational resources needed to transform a game from one form of representation to another one. This includes the study of the problem of enumerating the fundamental families of coalitions of a simple game. In particular we prove that several changes of representation that require exponential time can be solved with polynomial-delay and highlight some open problems.     

Strategy-proof coalition formation

We analyze coalition formation problems in which a group of agents is partitioned into coalitions and agents’ preferences only depend on the coalition to which they belong. We study rules that associate to each profile of preferences a partition of the society. We focus on strategy-proof rules on restricted domains of preferences, as the domains of additively representable or separable preferences. In such domains, the only strategy-proof and individually rational rules that satisfy either a weak version of efficiency or non-bossiness and flexibility are single-lapping rules. Single-lapping rules are characterized by severe restrictions on the set of feasible coalitions that are consistent with hierarchical organizations. These restrictions are necessary and sufficient for the existence of a unique core-stable partition. In fact, single-lapping rules always select the associated unique core-stable partition. Thus, our results highlight the relation between the non-cooperative concept of strategy-proofness and the cooperative concept of uniqueness of core-stable partitions.     

Efficient firm groups: Allocative efficiency in cooperative games

The concept of efficiency in groups postulates that a coalition of firms has to record a smaller distance toward the aggregate technology frontier compared with the sum of individual distances. Efficiency analysis (either allocative or technical) is defined with respect to cooperative firm game in order to provide operational distance functions, the so-called pseudo-distance functions. These pseudo-distances belong to the core interior of the allocative firm game, in other terms, any given firm coalition may always improve its allocative efficiency. We prove that such a result is impossible for technical efficiency, i.e., the technical efficiency cannot increase for all possible coalitions.     

Noncooperative formation of coalitions in hedonic games

We study a bargaining procedure of coalition formation in the class of hedonic games, where players’ preferences depend solely on the coalition they belong to. We provide an example of nonexistence of a pure strategy stationary perfect equilibrium, and a necessary and sufficient condition for existence. We show that when the game is totally stable (the game and all its restrictions have a nonempty core), there always exists a no-delay equilibrium generating core outcomes. Other equilibria exhibiting delay or resulting in unstable outcomes can also exist. If the core of the hedonic game and its restrictions always consist of a single point, we show that the bargaining game admits a unique stationary perfect equilibrium, resulting in the immediate formation of the core coalition structure.     

基于前景理论的众包物流配送方行为决策演化博弈分析——基于发货方视角

考虑个体有限理性特征,基于前景理论构建众包物流参与者感知收益博弈矩阵。从发货方视角,推理出众包物流配送方发挥较高努力水平的条件。通过引入保价制度,建立保价条件下配送方的行为决策模型,并运用数值仿真技术验证模型的有效性。结果发现:(1)配送方的努力成本、不努力的收入、处罚力度等指标直接影响其努力水平;(2)配送方努力工作的成本前景值要小于受到处罚与不努力收入前景值之和,同时要小于努力工作时所得的收益;(3)保价金额变动在一定条件下会影响配送方的努力水平,但是并不能达到完全控制的目的,甚至造成负面影响。因此在保价基础上,发货方可以通过增加监测力度或者加大处罚力度,有效保证配送方的努力水平。     

A simulated annealing based hyperheuristic for determining shipper sizes for storage and transportation

The current drive to reduce packaging waste has led many companies to consider the use of multi-trip containers or shippers in which to transport their products in order to reduce packaging waste. The efficiency of such systems obviously depends on selecting shipper dimensions in such a way as to ensure high volumetric utilisation. As is the case with many practical problems the efficiency/solution quality can be improved if problem specific information is used to enhance the operation of a meta-heuristic solution approach. The problem can be modelled as a p-median problem but is too large to be solved in reasonable time without further modification. Four such modifications, all based on properties of the physical problem, are introduced and incorporated into a hyperheuristic driven simulated annealing solution approach.     

Supplier-initiated outsourcing: A methodology to exploit synergy in transportation

Over the last decades, transportation has been evolving from a necessary, though low priority function to an important part of business that can enable companies to attain a competitive edge over their competitors. To cut down transportation costs, shippers often outsource their transportation activities to a logistics service provider of their choice. This paper proposes a new procedure that puts the initiative with the service provider instead: supplier-initiated outsourcing. This procedure is based on both operations research and game theoretical insights. To stress the contrast between the traditional push approach of outsourcing, and the here proposed pull approach where the service provider is the initiator of the shift of logistics activities from the shipper to the logistics service provider, we will refer to this phenomenon as insinking. Insinking has the advantage that the logistics service provider can proactively select a group of shippers with a strong synergy potential. Moreover, these synergies can be allocated to the participating shippers in a fair and sustainable way by means of a so-called Shapley Monotonic Path of customized tariffs. Insinking is illustrated by means of a practical example based on data from the Dutch grocery transportation sector.     

Stable profit sharing in a patent licensing game: general bargaining outcomes

By considering coalition structures formed by an external licensor of a patented technology and oligopolistic firms, we investigate licensing agreements that can be reached as bargaining outcomes under those coalition structures. The following results hold in a generalized patent licensing game. The core for a coalition structure is always empty, unless the grand coalition forms. We give a necessary and sufficient condition for the nonemptiness of the core (for the grand coalition). If the number of licensees that maximizes licensees’ total surplus is greater than the number of existing non-licensees, each symmetric bargaining set for a coalition structure is a singleton, and the optimal number of licensees that maximizes the licensor’s revenue is uniquely determined. The authors wish to thank the chief editor, anonymous referees, and participants in the 10th DC (Japan), the 3rd ICMA, and the 17th Stony Brook conference for helpful comments and suggestions. Thanks are extended to Ryo Kawasaki for editing English. They are partially supported by the MEXT Grant-in-Aid for 21 Century COE Program, Grant-in-Aid 18730517 (Watanabe), and Grant-in-Aid 16310107 (Muto).     

Contractually stable networks

We consider situations where players are part of a network and belong to coalitions in a given coalition structure. We propose the concept of contractual stability to predict the networks that are going to emerge at equilibrium when the consent of coalition partners is needed for adding or deleting links. Two different decision rules for consent are analyzed: simple majority and unanimity. We characterize the coalition structures that make the strongly efficient network contractually stable under the unanimity decision rule and the coalition structures that sustain some critical network as contractually stable under the simple majority decision rule and under any decision rule requiring the consent of any proportion of coalition partners. Requiring the consent of coalition members may help to reconcile stability and efficiency in some classical models of network formation.     

A savings-based model for two-shipper cooperative routing

We introduce a methodology for operational planning of cooperation between two independent shippers who manage their own fleets of vehicles in a given geographic area. We assume that shippers are willing to establish partial cooperation by sharing only a subset of customers. Our approach is based on the iterative attempt of identifying subsets of shareable customers which can be fruitfully exchanged between shippers. We resort to classic concepts of vehicle routing literature such as savings and insertion costs, providing both a heuristic and an exact approach.     

Equilibria in load balancing games

A Nash equilibrium （NE） in a multi-agent game is a strategy profile that is resilient to unilateral deviations. A strong Nash equilibrium （SE） is one that is stable against coordinated deviations of any coalition. We show that, in the load balancing games, NEs approximate SEs in the sense that the benefit of each member of any coalition from coordinated deviations is well limited. Furthermore, we show that an easily recognizable special subset of NEs exhibit even better approximation of SEs.     

Common pool resources with support

We examine the role of support for coalition stability in common pool resource games such as fisheries games. Some players may not want to join a coalition that jointly manages a resource. Still, because they benefit from spillovers, they may want to support the coalition with a transfer payment to set incentives for others to join. We find that the impact of support on equilibria of this game is limited to games with three or five players. Recommendations for Resource Managers

• Coalitions may be able to effectively manage common pool resources such as fisheries but such coalitions are often not stable due to free-rider incentives.
• We explore the impact of a transfer scheme that can improve this coalition stability which would lead to larger and more effective coalitions.
• Our results show that this new transfer scheme works only for cases where the number of players is small.

     

Allocating the gains from resource pooling with the Shapley Value

To make their cost structure more efficient, firms often pool their critical resources: small divisions of a large firm may negotiate a joint contract to benefit from volume discounts; or firms may outsource their call centres to an independent provider who is able to increase utilization by reducing variability since demand is now pooled. Since pooling demand reduces total joint costs, an immediate question is how the realized savings should be shared. We model the problem as a cooperative game and use the resulting allocation schemes to distribute the savings. One popular scheme is the Shapley Value, which always exists and, we show, represents each player's incremental value to the pool. When the pooled savings depend on the sum of each player's demand, we label the game coalition symmetric and propose, for those games, an algorithm that makes pseudo-polynomial the computation of the Shapley Value.     

A Note on the Private Core and Coalitional Fairness under Asymmetric Information

We study relations among Walrasian expectations allocations, coalitional fair allocations and the private core of economies with uncertainty and asymmetric information. Our analysis covers finite exchange models, as well as models of mixed markets consisting of some large traders and an ocean of small traders. The adopted notion of coalitional fairness requires that: 1. Under a “c-fair” allocation, no coalition could benefit from achieving the net trade of some other disjoint coalition; 2. Coalition bargaining takes place without information sharing among agents. We introduce a notion of restricted Walrasian expectations allocation and examine its relations with c-fairness.     

Exploring the VCG mechanism in combinatorial auctions: The threshold revenue and the threshold-price rule

We explore interesting potential extensions of the Vickrey–Clarke–Groves (VCG) rule under the assumption of players with independent and private valuations and no budget constraints. First, we apply the VCG rule to a coalition of bidders in order to compute the second price of the coalition. Then, we introduce and formulate the problem of determining that partition of players into coalitions which maximize the auctioneer’s revenue in the case whereby such coalitions take part to a VCG auction each one as a single agent; in particular, we provide an integer linear formulation of this problem. We also generalize this issue by allowing players to simultaneously belong to distinct coalitions in the case that players’ valuation functions are separable. Finally, we propose some applications of these theoretical results. For instance, we exploit them to provide a class of new payment rules and to decide which bids should be defined as the highest losing ones in combinatorial auctions.     

Strategic cooperation in cost sharing games

We examine strategic cost sharing games with so-called arbitrary sharing based on various combinatorial optimization problems. These games have recently been popular in computer science to study cost sharing in the context of the Internet. We concentrate on the existence and computational complexity of strong equilibria (SE), in which no coalition can improve the cost of each of its members. Our main result reveals a connection to the core in coalitional cost sharing games studied in operations research. For set cover and facility location games this results in a tight characterization of the existence of SE using the integrality gap of suitable linear programming formulations. Furthermore, it allows to derive all existing results for SE in network design cost sharing games with arbitrary sharing via a unified approach. In addition, we show that in general there is no efficiency loss, i.e., the strong price of anarchy is always 1. Finally, we indicate how the LP-approach is useful for the computation of near-optimal and near-stable approximate SE.     

Coalition formation in the presence of continuing conflict

This paper studies endogenous coalition formation in a rivalry environment where continuing conflict exists. A group of heterogeneous players compete for a prize with the probability of winning for a player depending on his strength as well as the distribution of strengths among his rivals. Players can pool their strengths together to increase their probabilities of winning as a group through coalition formation. The players in the winning coalition will compete further until one individual winner is left. We show that in any equilibrium there are only two coalitions in the initial stage of the contest. In the case of three players, the equilibrium often has a coalition of the two weaker players against the strongest. The equilibrium coalition structure with four players mainly takes one of the two forms: a coalition of the three weaker players against the strongest or a coalition of the weakest and strongest players against a coalition of the remaining two. Our findings imply that the rivalry with the possibility of coalition formation in our model exhibits a pattern of two-sidedness and a balance of power. We further study the impact of binding agreements by coalition members on equilibrium coalition structures. Our analysis sheds some light on problems of temporary cooperation among individuals who are rivals by nature.