Shoshana Anily

Problem definition: We consider the parallel machine scheduling (PMS) under job-splitting game defined by a set of manufacturers where each holds uniform parallel machines and each is committed to produce some jobs submitted to her by her clients while bearing the cost of the sum of completion times of her jobs on her machines. An efficient algorithm for this scheduling problem is well known. We consider the corresponding cooperative game, where the manufacturers are players that want to join forces. We show that collaboration is profitable. Yet, the stability of the cooperation depends on the cost allocation scheme; we focus on the core of the game. Methodology/results: We prove that the PMS game is totally balanced and its core is infinitely large, by developing a sophisticated methodology of linear complexity that finds a line segment in its symmetric core. We call this segment the basic core of the game. Managerial implications: This PMS game has the potential for various applications both in traditional industry and in distributed computing systems in the hi-tech industry. The formation of a partnership among entrepreneurs, companies, or manufacturers necessitates not only a plan for joining forces toward the achievement of the ultimate goals, but also an acceptable agreement regarding the cost allocation among the partners. Core allocations guarantee the stability of the partnership as no subset of players can gain by defecting from the grand coalition. Funding: This work was supported by the Henry Crown Israeli Institute for Business Research, the Coller Foundation, and the Israel Science Foundation [Grant 1489/19].

Assume a multi‐server memoryless loss system. Each server is associated with a service rate and a value of service. Customers from a common Poisson arrival process are routed to the servers in an unobservable way, where the goal is to maximize the long‐run expected reward per customer (which is the service value times the probability that the customer is not blocked). We first solve this problem under two criteria: social optimization and Nash equilibrium. Our main result is that the price of anarchy, defined as the ratio between the expected gain under the two criteria, is bounded by . We also show, via examples, that this bound is tight for any number of servers.

We propose a method to design cost allocation contracts that help maintain the stability of strategic alliances among firms by using cooperative game theory. The partners of the alliance increase their efficiency by sharing their assets. We introduce a new sufficient condition for total balancedness of regular games, and a full characterization of their nonnegative core. A regular game is defined by a finite number of resources owned by the players. The initial cost of a player is a function of the vector of quantities of the resources that the player owns. The characteristic function value of a coalition is a symmetric real function of the vectors of its members. Within this class we focus on centralizing aggregation games, meaning that the formation of a coalition is equivalent to aggregating its players into one artificial player whose cost is an intermediate value of the costs of the aggregated players. We prove that under a certain decreasing variation condition, a centralizing aggregation game is totally balanced and its nonnegative core is fully characterized. We present a few nonconcave games in operations management that their nonnegative core is fully characterized, by showing that they satisfy the conditions presented in this article.

We consider the Inventory‐Routing Problem (IRP) where n geographically dispersed retailers must be supplied by a central facility. The retailers experience demand for the product at a deterministic rate, and incur holding costs for keeping inventory. Distribution is performed by a fleet of capacitated vehicles. The objective is to minimize the average transportation and inventory costs per unit time over the infinite horizon. We focus on the set of Fixed Partition Policies (FPP). In an FPP, the retailers are partitioned into disjoint and collectively exhaustive sets. Each set of retailers is served independently of the others and at its optimal replenishment rate. Previous research has measured the effectiveness of an FPP solution relative to a lower bound over all policies. We propose an additional measure that is relative to the optimal FPP. In this paper we construct a polynomial‐time partitioning scheme that is shown to yield an FPP whose cost is asymptotically within 1.5% + ϵ of the cost of an optimal FPP, for arbitrary ϵ > 0. In addition, in some cases, our polynomial‐time scheme yields an FPP whose cost is asymptotically within 1.5% + ϵ of the minimal policy's cost (over all feasible policies). © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004