*********************************************************************

Seminar

Department of Systems Engineering and Engineering Management

The Chinese University of Hong Kong

----------------------------------------------------------------------------------------------

Title: Duality Approach to Inventory Centralization Games

Speaker: Xin Chen, Assistant Professor

Department of Industrial and Enterprise Systems Engineering

University of Illinois at Urbana-Champaign

Date : December 13th, 2006 (Wednesday)

Time : 4:30p.m. - 5:30p.m.

Venue : Room 513

MMW Engineering Building(Engineering Building Complex Phase 2)

CUHK

--------------------------------------------------------------------------------------------

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.

--------------------------------------------------------------------------------------------

Biography:

Prof.Xin Chen is an Assistant Profesor in the Department of Industrial and

Enterprise Systems Engineering, the University of Illinois at

Urbana-Champaign. He got his Ph.D. degree from the Department of

Operations Research, Massacheusetts Institute of Technology in 2003. After

that, he held a TA/Lecturer position in MIT from Fall 2002 to Fall 2003

and a Postdoctoral associate position in MIT from 2003 to 2004. He was an

Assistant Professor in the Dept of Mechanical and Industrial Engineering,

UIUC in 2004. Prof. Xin's research interests lie in the areas of

Production, Inventory and Supply Chain Management Optimization, Optimal

Stochastic Control, Computational Mathematics, Operations Research and

Operations Management. He published more than 20 papers in renowned

conferences and journals and a book, The Logic of Logistics by

Springer-Verlag in 2004.

*********************** ALL ARE WELCOME ************************

Host : Professor Chen, Youhua, Frank

Tel : (852) 2609-8310

Email : yhchen@se.cuhk.edu.hk

Enquiries: Peixiang Zhao or Jeffrey Xu Yu,

Department of Systems Engineering and Engineering Management

CUHK

Website: http://www.se.cuhk.edu.hk/~seg5810

Email: seg5810@se.cuhk.edu.hk

********************************************************************