For an unbalanced cooperative game, its grand coalition can be stabilized by some instruments, such as subsidization and penalization, that impose new cost terms to certain coalitions. In this paper, we study an alternative instrument, referred to as cost adjustment, that does not need to impose any new coalition-specific cost terms. Specifically, our approach is to adjust existing cost coefficients of the game under which (i) the game becomes balanced so that the grand coalition becomes stable, (ii) a desired way of cooperation is optimal for the grand coalition to adopt, and (iii) the total cost to be shared by the grand coalition is within a prescribed range. Focusing on a broad class of cooperative games, known as integer minimization games, we formulate the problem on how to optimize the cost adjustment as a constrained inverse optimization problem. We prove [Formula: see text]-hardness and derive easy-to-check feasibility conditions for the problem. Based on two linear programming reformulations, we develop two solution algorithms. One is a cutting-plane algorithm, which runs in polynomial time when the corresponding separation problem is polynomial time solvable. The other needs to explicitly derive all the inequalities of a linear program, which runs in polynomial time when the linear program contains only a polynomial number of inequalities. We apply our models and solution algorithms to two typical unbalanced games, including a weighted matching game and an uncapacitated facility location game, showing that their optimal cost adjustments can be obtained in polynomial time. History: Accepted by Area Editor Andrea Lodi for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72022018 and 72091210]; the Research Grants Council of the Hong Kong SAR, China [Grant 16210020]; Hong Kong Polytechnic University [Grant P0032007]; and the Youth Innovation Promotion Association, Chinese Academy of Sciences [Grant 2021454]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0268 .

For a cost-sharing cooperative game with an empty core, we study the problem of calculating a near-optimal cost allocation that satisfies coalitional stability constraints and maximizes the total cost allocated to all players. One application of such a problem is finding the minimum level of subsidy required to stabilize the grand coalition. To obtain solutions, we propose a new generic framework based on Lagrangian relaxation, which has several advantages over existing work that exclusively relies on linear programming (LP) relaxation techniques. Our approach can generate better cost allocations than LP-based algorithms, and is also applicable to a broader range of problems. To illustrate the efficiency and performance of the Lagrangian relaxation framework, we investigate two different facility location games. The results demonstrate that our new approach can find better cost allocations than the LP-based algorithm, or provide alternative optimal cost allocations for cases that the LP-based algorithm can also solve to optimality.

In this paper, we address a new scheduling model for a firm with an option of outsourcing. A job can be processed by either in-house production or outsourcing. All outsourced jobs have to be transported back to the firm in batches, and the transportation costs have to be taken into account. We model the situation as a scheduling problem with transportation considerations. We discuss four commonly used objective functions, and solve them by dynamic programming algorithms. Note to Practitioners-An efficient supply chain management needs the coordination of production and transportation. Such problems exist in many different scenarios. This research considers a particular problem for a firm that has an option of using a subcontractor to fulfill part of its orders. The production schedule has to be coordinated with logistics issues for the transportation from the subcontractor to the firm. The purposes of this paper are twofold. First, we build models and provide optimal solutions for the specific cases discussed in this paper. Second, we hope to raise the issue of coordinated logistics scheduling, and motivate future research on more complicated models.

We propose a novel multicast protection scheme based on a dual-homing architecture where each destination host is connected to two edge routers. Under such an architecture, the two paths from the source of the multicast session to the two edge routers provide certain protection for the data traffic from the source to the destination host. Two problems are associated with the proposed dual-homing multicast protection scheme. One is to calculate the individual survivability for a destination host that is connected to two edge routers. The other is to assign two edge routers for each destination host such that the total survivability is maximized for the multicast session subject to the port number constraint of edge routers. We propose an optimal algorithm to solve the first problem and a heuristic algorithm to solve the second problem. Through simulations, we show that the proposed heuristic algorithm achieves a performance close to the calculated lower bound.

A fault-tolerant scheme, called dual homing, is generally used in IP-based access networks to increase the survivability of the network. However, dual homing itself cannot provide survivability with respect to possible failures in the wavelength division multiplexed (WDM) core network. To provide survivability in the core network, protection and restoration techniques must be used. In the past, dual homing architecture and protection are studied separately. This paper observes that the dual homing architecture introduces new issues for protection and restoration design, especially when providing survivability against two independent failures, one in the access network and the other in the core network. This paper provides an integrated solution and studies the protection design problem in the WDM core network, given a dual-homing infrastructure in the access network. Several algorithmic solutions are proposed, and performance of the solutions is compared.