Abstract:

Linear programming (LP) duality has played a fundamental role in the analysis of cooperative games. In this lecture, we will present new applications of LP duality and stochastic LP duality in studying cooperative games arising from inventory centralization. In particular, we show that duality theory can be used to prove the non-emptiness of cores for such inventory games and to find an element in the core.

The first example is the economic lot-sizing game, in which multiple retailers form a coalition by placing joint orders to a single supplier in order to reduce ordering cost, which is assumed to be a concave function of the order quantity. We are concerned with the issue of how to allocate the cost/benefit so that it is advantageous for every retailer to join the coalition. The standard formulation of the corresponding optimization problem is a concave minimization problem and hence LP duality does not directly apply. We suggest an integer programming formulation for this optimization problem and show that its LP relaxation admits zero integrality gap, which makes it possible to analyze the game using LP duality. We show that there exists an optimal dual solution that gives rise to an allocation in the core, which can be found in polynomial time. An interesting feature of our approach is that, in contrast to the duality approach for other known cooperative games, it is not necessarily true that every optimal dual solution gives rise to a core allocation.

Another example is a single-period inventory centralization game with stochastic demand where multiple retailers form a coalition by holding centralized inventory in order to take advantage of the effect of risk pooling. Again, we are concerned with the issue of how to allocate the cost/benefit. When the ordering cost is linear, the optimization problem corresponding to the inventory game is formulated as a stochastic program. We observe that the strong duality of stochastic LP not only directly leads to a series of recent results concerning the non-emptiness of the cores of such games, but also suggests a way to find an element in the core. We further construct a nontrivial infinite dimensional linear programming dual for the well-known newsvendor problem with concave ordering cost and prove a strong duality result for this non-convex minimization problem. This new duality result immediately implies that the corresponding game has a non-empty core. Finally, we prove that it is NP-hard to determine whether a given allocation is in the core for the newsvendor game even in a very simple setting.

This is a joint work with Jiawei Zhang at New York University.