Game-Theoretic Approaches for Complex Systems Optimization by Shih-Fen Cheng A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Industrial and Operations Engineering) in The University of Michigan 2006 Doctoral Committee:. Smith, Co-Chair Professor Michael P. Wellman, Co-Chair Associate Professor Satinder Singh Baveja Associate Professor Marina A. Epelman UMI Number: 3237932 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted.
Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3237932 Copyright 2007 by ProQuest Information and Learning Company.
All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 © Shih-Fen Cheng 2006 All Rights Reserved To my parents, my parents-in-law, and my wife, for their unconditional love and support.
ii ACKNOWLEDGMENTS This thesis includes joint work with Robert Smith, Michael Wellman, Marina Epel- man, Daniel Reaume, Archis Ghate, Daniel Reeves, Kevin Lochner, Blake Nicholson, and Stephen Baumert.2, I provide a brief summary on the connection be- tween chapters in this thesis and joint work with these co-authors. Kevin O’Malley was one of the primary developers that laid the foundation for AB3D, which is the platform for market game simulations in Part II. I would like to thank my thesis committee — Robert Smith, Michael Wellman, Ma- rina Epelman, and Satinder Singh Baveja — for their careful reading and insightful com- ments. Their feedbacks are invaluable in improving the thesis.
This thesis could not be completed without the guidance from my advisors, Michael Wellman, Robert Smith, and Marina Epelman (although she is not officially listed). Each of them has very different advising style, however, their passion for research, teaching, and advising is unmatched. Their positive altitudes toward my work have helped shaping my research career, and they provided ideal images on what a passionate research should be like. Their also showed great considerations for my career development, especially during the final stage of my Ph.
Iam grateful to the members of both Decision Machine Group and Dynamic Systems Optimization Laboratory: Daniel Reeves, Kevin Lochner, Archis Ghate, Blake Nichol- son, Chris Kiekintveld, Yagil Engel, Irina Dolinskaya, and Stephen Baumert. Their feed- backs on my work and my various presentation are greatly appreciated. I especially would like to thanks Dan and Kevin for their numerous proof-reading of my writings and iil also their social support. Without them my life as a graduate student would certainly be less delightful.
I also would like to thank my coworkers and friends at AATPC and Mustardseed, for their continuous support and prayer. And finally, I would like to thank my family, especially my wife, Cindra, for her continuous patience and effort in pushing me through the Ph. program, for taking care of our son, Ian, and for voluntarily being the first audience on almost all my research talks. iv TABLE OF CONTENTS DEDICATION.
kg k k k kna ii ACKNOWLEDGMENTS .6 ee ee iii LIST OF TABLES. Q Q Qua 1X LIST OF FIGURES. Q Q Q Q Q va X LIST OF APPENDICES. Q ee ko xi ABSTRACT.
Qua xii CHAPTER 1 Introduction. cv ch ng cv k kg k kg 1 1. cv gà gà và 3 2 Preliminaries: Basics of Game TheOory. co 5 3 When to Include Stochasticity: A Case Study of End-State Planning Problem in Production Lines.
uc cv gà kg gà va 8 3.2 A Graph Model of the End-State Planning Problem .1 A Graph Model for Representing Production Lines. The Formal Definition of the End-State Planning Problem 11 3.3 Deterministic Dynamic Programming Formulation.1 Deriving End States from the Shutdown Schedule .2 Computing Shutdown Time from the Shutdown Schedule 14 3.3 Dynamic Programming Model .4 Special Cases: Strip-All and Exact Job-Count Goals .2 ExactJob-Count Goals .2 The Optimal Policy and Alternatives. The Potential Benefits of a Stochastic Model. es 29 PARTI Sampled Fictitious Play Algorithm for Large-Scale Dis- crete Optimization Problems 31 4 An Introduction to the Sampled Fictitious Play Algorithm.
c Q Quà ky va 36 5 Optimizing Large Scale Simulations by Parallel Computing. cv ee va 39 5.2 Traffic Signal Control Problem Formulation. CoSIGN: SFP Algorithm for the Traffic Signal Control Problem 43 5.1 Formulating Coordinated Traffic Signal Control Prob- lemasaGame.342 Simulation by INTEGRATION-UM. SFP with Simulation-Based Best Reply Computation .4 Case Study: Troy, Michigan, Network .1 Competing Timing Plans and Algorithms .2 Benefits of Signal Coordination and Predictive Informa- HON 53 5.3 Parallelized Implementation of CoSIGN .4 Relative Performance of Parallelized CoSIGN vs.
Coor- dinate Descent. 0- 2000004 62 6 Approximate Large-Scale Dynamic Programming: A Special Case. eee ee ee 68 6.2 The Joint Optimization Problem .2 The Markov Decision Process. Complexity of the Markov Decision Model .3 Game-Theoretic Model for the Joint Optimization Problem .2 Best Reply Problem for the Capital Investment Module .3 Best Reply Problem for the Production Scheduling Module 85 6.4 Best Reply Problem for the Revenue Management Module 85 6.5 Best Reply Problem for the Sales Planning Module .6 The Complexity Bound for Solving the Decomposed MDP 86 6.4 Vehicle Manufacturing: A Numerical Case Study .2 Experimental Results and Analyss.3 Obtaining Managerial Insights via Optimizations.
93 7 Sampled Fictitious Play: Conclusions and Future Work. Summary of Contributions. Q g Q ng kg sa 96 PART IY Market-Based Approach For Decentralized Resource Allocation Problem 99 8 Market-Based Approach: An Introduction. cv ee và ee 100 8.1 Market-Based Resource Allocation.
Game-Theoretic Analysis. ee ee 103 9 Market-Based Approach: An Empirical Methodology .1 Iterative Mechanism Selection: An Overview .3 Designing Agent Strategies.4 Finding Nash Equilibrium in EmpiricalGames.5 Conclusion and Related Works. 113 10 Strategy Reduction by Iterated J-Dominance. ee 2 và ee 115 10.2 Iterated ô-Dominance and Equilibrium Approximation.3 Implementation of Iterated ô-Dominance.1 Finding Minimal 6 That Dominates Subset of Strategies .2 A Greedy Heuristic for Forming Domination Path.
Computing Tighter Error Bounds.4 6-Dominance for SymmetricGames .2 Comparison of GREEDY-1 and GREEDY-2. ee 131 11 Task Allocation for Dynamic Information Processing Environments: A Motivational Example .2 Task Allocation Scenario .1 Dynamic Task Allocation Problem. ee ee ee 142 vi 11.2 Marginal-Value Bidding Strategy. Dynamic Task Allocation ScenarioinGDL.
cv ee a 150 12 Market-Based Approach: Conclusions and Future Work .1 Summary of Contributions. ee ee 153 APPENDICES. 2nà và va 154 BIBLIOGRAPHY. vo 169 vill LIST OE TABLES Table 3.1 Performance of three competing algorithms.1 Performances of the MDP solver and the SFP solver.1 Summary of various error bounds at each strategy level.0 eee ee ee es 150 1X LIST OF FIGURES Figure 3.1 A serial production line.
The jobs enter the production line at line element Ñ, and exit at line elementl.2 Schematic graph for the engine compartment zone.3 Schematic graph for the underbody zone.4 Maximal achievable value and value obtained in optimal policy.5 Shutdown time foreach lineelement.1 Sampled Fictitious Play (sample size l).1 Simulation-based best reply function.2 The snapshot of Troy’s areamap.3 The Troy network topology model, composed of 529 links, 200 nodes and 72 zone centroids that can serve as origins or destinations.4 Coordinate Descent (CD) algorthm.5 The evolution of best values as a function of iteration count for the normal- flow caS@, ee 5.6 The evolution of best values as a function of iteration count for the light- flowcase, 2.7 The evolution of best values as a function of iteration count for the heavy- flow case, 6aðẼãðẼðIl-.8 Average travel time as a function of vehicles’ departing time, for the light- flow case, 2.9 Average travel time as a function of vehicles’ departing time, for the normal-flow case. Q Q Q HH nu ng kg k k va 5.10 Average travel time as a function of vehicles’ departing time, for the heavy-flow case.11 Running time of CoSIGN versus degree of parallelization K.12 Average travel time of solution found by CD when given the same wall- clock time as the parallel execution of CoSIGN with K processors, vs.: for the normal-flow €aS€.13 Average travel time of solution found by CD when given the same wall- clock time as the parallel execution of CoSIGN with K processors, vs.: for the heavy-flow case.1 The Markov decision model used. S,,,,, is the decision being made at state (m,n,2). F(m, n,7) is the set of feasible decisions at state (m,n, ?) and will be defined later.
The demand function, đ„, and the available frac- tion of the capacity, øa, will be realized after the decision is made. These two realized random variable will then complete the state transition. As Pn and d,, realized, the reward, RỂ h"" is also generated and accumulated.2 Interacting diagram indicating how decision modules affect each other. Important problem data: (a) Production line building cost, paid by period, as a function of capacity.
(b) Demand as a function of price. (c) Variable cost asafunctionofcapacity.4 Best values plotted against iterations, forthe SFP solver, .5 Average inventory levels versus mean reliability levels.1 General market gaming platform, depicted at functional level.1 LP-A(S, T): formulation for finding 6 that dominates T, a set of strategies.2 Simple greedy heuristic, one strategy (the one with least 6) is pruned in each iteration until © is alusedup.3 Generalized greedy heuristic, which is similar to Algorithm 10.2, but prunes k strategies in each iteration, .4 Evolutions of number of remaining strategies versus accumulated 6.5 Error bounds at each strategy level.1 A high-level illustration on task allocation problem in a decentralized setting. Agents on the left-hand side are assigned certain tasks indepen- dently, and required resources must be obtained through the correspond- ingexchanges.2 Two-phase markets. SAAs are used for the “preparation phase” where each agent drafts its initial plan.
After the “planning phase” begins, all SAAs are converted to CDA. The planning is “online”, therefore agents will receive dynamic task information, market updates, and have to sub- mit task commitments as time pf0gT@SS@S.3 AB3D specification of a resource auction. The third and fourth rules (when clauses) trigger the change from ascending auction to CDA after- ¡1 s1.4 Simple shading procedure for the marginal value strategy.1 This is the main game file that defines important game parameters men- tioned in Section 11.2 This figure lists the GDL used in defining agent’s preference.3 This figure lists the GDL used in defining dynamically arriving tasks. Note that the section that defines task’s parameter is identical to the frag- ment in Figure B.2, therefore it is neglected here.
Xi LIST OF APPENDICES APPENDIX A Adaptive Signal Re-timing. B Game Definition Language for Market Games £ 8 R8 8 xi ABSTRACT Game-Theoretic Approaches for Complex Systems Optimization by Shih-Fen Cheng Co-Chairs: Robert L. Smith and Michael P. Wellman A complex system is an artificial system that cannot be modeled analytically or opti- mized in an effective manner, usually because it possesses the following properties: (1) the system can only be modeled as a simulation, (2) the size of the problem is untenable, so that even if the system could be modeled analytically, it would be impractical to solve it exactly, (3) necessary information required for problem solving is distributed in na- ture.
This thesis presents methods for modeling and optimizing systems with the above challenging properties. We first discuss the important modeling decision of whether to include stochasticity. By employing a real-world case study, we show that a standard numerical procedure can indeed help us make this decision. Next, we use the challenging problem of finding coordinated signal timing plans to motivate the need of a new paradigm for simulation optimization.