Game-Theoretic Approaches for Complex Systems Optimization

• Tác giả: Shih-Fen Cheng
• Người hướng dẫn: Robert L. Smith
• Trường học: The University of Michigan
• Chuyên ngành: Industrial and Operations Engineering
• Đề tài: Tối Ưu Hệ Thống Phức Tạp Bằng Cách Tiếp Cận Lý Thuyết Trò Chơi
• Loại tài liệu: dissertation
• Năm xuất bản: 2006
• Địa điểm: Ann Arbor

• DEDICATION
• ACKNOWLEDGMENTS
• LIST OF TABLES
• LIST OF FIGURES
• LIST OF APPENDICES
• ABSTRACT
• 1. CHAPTER 1: Introduction
• 1.1. Scope of the Research
• 1.2. Organization
• 2. CHAPTER 2: Preliminaries: Basics of Game Theory
• 3. CHAPTER 3: When to Include Stochasticity: A Case Study of End-State Planning Problem in Production Lines
• 3.1. A Graph Model of the End-State Planning Problem
• 3.2. Deterministic Dynamic Programming Formulation
• 3.2.1. Deriving End States from the Shutdown Schedule
• 3.2.2. Computing Shutdown Time from the Shutdown Schedule
• 3.3. Dynamic Programming Model
• 3.3.1. Special Cases: Strip-All and Exact Job-Count Goals
• 3.3.2. Exact Job-Count Goals
• 3.3.3. The Optimal Policy and Alternatives
• 3.3.4. The Potential Benefits of a Stochastic Model
• PART I. Sampled Fictitious Play Algorithm for Large-Scale Discrete Optimization Problems
• 4. An Introduction to the Sampled Fictitious Play Algorithm
• 5. Optimizing Large Scale Simulations by Parallel Computing
• 5.1. Formulating Coordinated Traffic Signal Control Problems as Game
• 5.2. Traffic Signal Control Problem Formulation
• 5.3. Parallelized Implementation of CoSIGN
• 5.4. Relative Performance of Parallelized CoSIGN vs. Coordinate Descent
• 6. Approximate Large-Scale Dynamic Programming: A Special Case
• 6.1. The Joint Optimization Problem
• 6.2. The Markov Decision Process
• 6.3. Game-Theoretic Model for the Joint Optimization Problem
• 6.4. Best Reply Problem for the Capital Investment Module
• 6.5. Best Reply Problem for the Production Scheduling Module
• 6.6. Best Reply Problem for the Revenue Management Module
• 6.7. Best Reply Problem for the Sales Planning Module
• 6.8. The Complexity Bound for Solving the Decomposed MDP
• 6.9. Vehicle Manufacturing: A Numerical Case Study
• 6.10. Experimental Results and Analysis
• 6.11. Obtaining Managerial Insights via Optimizations
• 7. Sampled Fictitious Play: Conclusions and Future Work
• PART II. Market-Based Approach For Decentralized Resource Allocation Problem
• 8. Market-Based Approach: An Introduction
• 8.1. Market-Based Resource Allocation. Game-Theoretic Analysis
• 9. Market-Based Approach: An Empirical Methodology
• 9.1. Iterative Mechanism Selection: An Overview
• 9.2. Designing Agent Strategies
• 9.3. Finding Nash Equilibrium in Empirical Games
• 9.4. Conclusion and Related Works
• 10. Strategy Reduction by Iterated J-Dominance
• 10.1. Iterated ô-Dominance and Equilibrium Approximation
• 10.2. Implementation of Iterated ô-Dominance
• 10.3. Finding Minimal 6 That Dominates Subset of Strategies
• 10.4. A Greedy Heuristic for Forming Domination Path
• 10.5. Computing Tighter Error Bounds
• 10.6. 6-Dominance for Symmetric Games
• 10.7. Comparison of GREEDY-1 and GREEDY-2
• 11. Task Allocation for Dynamic Information Processing Environments: A Motivational Example
• 11.1. Task Allocation Scenario
• 11.2. Marginal-Value Bidding Strategy
• 11.3. Dynamic Task Allocation Scenario in GDL
• 12. Market-Based Approach: Conclusions and Future Work
• 12.1. Summary of Contributions
• APPENDICES
• BIBLIOGRAPHY

I. Tổng Quan Về Tối Ưu Hệ Thống Phức Tạp Bằng Lý Thuyết Trò Chơi

Luận án này tập trung vào tối ưu hóa hệ thống phức tạp, những hệ thống khó mô hình hóa và tối ưu hóa hiệu quả. Đặc điểm của chúng bao gồm: chỉ có thể mô hình hóa bằng mô phỏng hệ thống, kích thước bài toán lớn, và thông tin phân tán. Đôi khi, việc đơn giản hóa mô hình có thể giúp tìm ra nghiệm tối ưu toàn cục. Tuy nhiên, trong nhiều trường hợp, việc đơn giản hóa quá mức sẽ làm mất tính thực tế của mô hình. Lý thuyết trò chơi là một công cụ hữu ích để phân tích các bài toán phân bổ nguồn lực đã được phân tách. Mục tiêu là xây dựng một khuôn khổ chung để giải quyết các bài toán tối ưu hóa trong các hệ thống nhân tạo phức tạp, đồng thời nghiên cứu hiệu quả của các giải pháp thu được.

1.1. Phạm Vi Nghiên Cứu và Ứng Dụng Lý Thuyết Trò Chơi

Nghiên cứu này tập trung vào việc phân tích và tối ưu hóa các hệ thống phức tạp thông qua lý thuyết trò chơi. Các câu hỏi chính được đặt ra bao gồm: Làm thế nào để phân tách bài toán tối ưu hóa? Quy trình chung để giải quyết bài toán tối ưu hóa trong bối cảnh hệ thống phức tạp là gì? Các tính chất của nghiệm thu được theo phương pháp lý thuyết trò chơi là gì? Độ phức tạp của việc tìm kiếm nghiệm trong các bài toán đã phân tách so với các thuật toán tìm nghiệm tối ưu toàn cục khác như thế nào? Nghiên cứu sử dụng mô phỏng hệ thống và mô hình Markov quy mô lớn để trả lời các câu hỏi này.

1.2. Tổ Chức Luận Án và Các Phương Pháp Tiếp Cận

Luận án được tổ chức thành hai phần chính. Phần I trình bày các phương pháp tiếp cận để giải quyết các bài toán tối ưu hóa rời rạc phức tạp, sử dụng công cụ Sampled Fictitious Play (SFP). Phần II tập trung vào các phương pháp tiếp cận dựa trên thị trường để giải quyết các bài toán phân bổ nguồn lực phi tập trung. Luận án cũng bao gồm một nghiên cứu điển hình về quyết định mô hình hóa, xem xét liệu có nên đưa yếu tố ngẫu nhiên vào mô hình hay không. Các chương tiếp theo sẽ đi sâu vào các khía cạnh khác nhau của lý thuyết trò chơi và ứng dụng của nó trong tối ưu hóa hệ thống.

II. Thách Thức Trong Mô Hình Hóa và Tối Ưu Hệ Thống Phức Tạp

Việc mô hình hóa và tối ưu hóa hệ thống phức tạp đặt ra nhiều thách thức. Một trong những thách thức lớn nhất là quyết định có nên đưa yếu tố ngẫu nhiên vào mô hình hay không. Mặc dù yếu tố ngẫu nhiên có thể làm cho mô hình trở nên thực tế hơn, nhưng nó cũng có thể làm tăng đáng kể độ phức tạp tính toán. Một thách thức khác là kích thước của bài toán. Ngay cả khi có thể mô hình hóa hệ thống một cách phân tích, việc giải quyết bài toán một cách chính xác có thể là bất khả thi do kích thước quá lớn. Cuối cùng, thông tin cần thiết để giải quyết bài toán có thể bị phân tán, gây khó khăn cho việc thu thập và xử lý.

2.1. Quyết Định Mô Hình Hóa Yếu Tố Ngẫu Nhiên và Độ Phức Tạp

Việc đưa yếu tố ngẫu nhiên vào mô hình có thể mang lại lợi ích, nhưng cũng đi kèm với chi phí. Nghiên cứu của Cheng et al. (2006) cho thấy rằng việc sử dụng một quy trình số tiêu chuẩn có thể giúp đưa ra quyết định này một cách thực nghiệm. Cần cân nhắc kỹ lưỡng giữa độ chính xác của mô hình và chi phí tính toán. Trong một số trường hợp, việc bỏ qua yếu tố ngẫu nhiên có thể dẫn đến một mô hình đơn giản hơn mà vẫn đủ chính xác để đưa ra các quyết định tốt.

2.2. Kích Thước Bài Toán và Giới Hạn Tính Toán

Ngay cả khi có thể mô hình hóa hệ thống một cách phân tích, việc giải quyết bài toán một cách chính xác có thể là bất khả thi do kích thước quá lớn. Điều này đặc biệt đúng đối với các hệ thống phức tạp có nhiều thành phần tương tác với nhau. Trong những trường hợp này, cần sử dụng các thuật toán xấp xỉ hoặc các phương pháp phân tách để giải quyết bài toán.

2.3. Thông Tin Phân Tán và Bài Toán Phi Tập Trung

Trong nhiều hệ thống phức tạp, thông tin cần thiết để giải quyết bài toán bị phân tán giữa nhiều tác nhân khác nhau. Điều này gây khó khăn cho việc thu thập và xử lý thông tin, và đòi hỏi các phương pháp tiếp cận phi tập trung. Lý thuyết trò chơi cung cấp một khuôn khổ để phân tích các bài toán phân bổ nguồn lực phi tập trung, trong đó các tác nhân đưa ra quyết định dựa trên thông tin cục bộ của họ.

III. Phương Pháp Sampled Fictitious Play SFP Cho Tối Ưu Hóa

Phần I của luận án tập trung vào việc sử dụng Sampled Fictitious Play (SFP) để giải quyết các bài toán tối ưu hóa hệ thống rời rạc phức tạp. SFP là một thuật toán lặp, trong đó mỗi người chơi chọn một chiến lược tốt nhất dựa trên các chiến lược đã chọn của những người chơi khác trong các lần lặp trước. Ưu điểm chính của SFP là khả năng mở rộng và khả năng xử lý các hàm mục tiêu hộp đen với thời gian đánh giá dài. Việc song song hóa thuật toán SFP là rất quan trọng để đáp ứng nhu cầu về thời gian trong các ứng dụng nhạy cảm về thời gian.

3.1. Giới Thiệu Thuật Toán Sampled Fictitious Play SFP

Sampled Fictitious Play (SFP) là một thuật toán lặp được sử dụng để tìm kiếm các nghiệm tối ưu cục bộ trong các bài toán tối ưu hóa hệ thống. Trong mỗi lần lặp, mỗi người chơi chọn một chiến lược tốt nhất dựa trên các chiến lược đã chọn của những người chơi khác trong các lần lặp trước. Quá trình này được lặp lại cho đến khi hội tụ đến một nghiệm cân bằng.

3.2. Ứng Dụng SFP Trong Bài Toán Điều Khiển Tín Hiệu Giao Thông

Cheng et al. (2006) đã sử dụng SFP để giải quyết bài toán điều khiển tín hiệu giao thông phối hợp. Kết quả cho thấy rằng SFP có thể được sử dụng như một công cụ sẵn có để tối ưu hóa một hàm mục tiêu hộp đen với các thuộc tính không xác định và thời gian đánh giá dài. Việc song song hóa thuật toán là rất quan trọng để đáp ứng nhu cầu về thời gian trong các ứng dụng nhạy cảm về thời gian.

3.3. SFP và Bài Toán Quy Hoạch Động Markov Quy Mô Lớn

SFP cũng có thể được sử dụng để xấp xỉ một chính sách điều khiển tối ưu trong một mô hình Markov. Cheng et al. (2006) đã sử dụng SFP để mô hình hóa một bài toán tối ưu hóa chung trong các hệ thống sản xuất chung. Thách thức chính trong trường hợp này là xử lý các ràng buộc không tầm thường.

IV. Tiếp Cận Dựa Trên Thị Trường Cho Phân Bổ Nguồn Lực Phi Tập Trung

Phần II của luận án tập trung vào các phương pháp tiếp cận dựa trên thị trường để giải quyết các bài toán phân bổ nguồn lực phi tập trung. Các thị trường được sử dụng như một cơ chế để điều phối việc phân bổ nguồn lực. Nghiên cứu tập trung vào cả phân tích lý thuyết trò chơi thực nghiệm và các phương pháp tiếp cận dựa trên thị trường. Các câu hỏi chính được đặt ra bao gồm: Các thị trường phân bổ nguồn lực hiệu quả như thế nào so với các lựa chọn thay thế và phân bổ toàn cục? Làm thế nào để xác định và định lượng các nguồn có thể gây mất hiệu quả trong thị trường? Làm thế nào để thiết kế các phương pháp tiếp cận xấp xỉ (với các giới hạn lỗi thích hợp) để tìm kiếm các cân bằng Nash trong một trò chơi lớn?

4.1. Phân Tích Lý Thuyết Trò Chơi Thực Nghiệm và Cơ Chế Thị Trường

Phân tích lý thuyết trò chơi thực nghiệm tập trung vào các kỹ thuật để ước tính các trò chơi thị trường thông qua việc chạy các mô phỏng và giải quyết các cân bằng Nash. Mặt khác, các phương pháp tiếp cận dựa trên thị trường tập trung vào việc giải quyết các bài toán phân bổ nguồn lực phi tập trung với các cơ chế thị trường.

4.2. Hiệu Quả Phân Bổ Nguồn Lực và Các Nguồn Gây Mất Hiệu Quả

Nghiên cứu này xem xét hiệu quả của các thị trường trong việc phân bổ nguồn lực, so sánh với các lựa chọn thay thế và phân bổ toàn cục. Nó cũng xác định và định lượng các nguồn có thể gây mất hiệu quả trong thị trường, chẳng hạn như thông tin không đối xứng và hành vi chiến lược.

4.3. Kỹ Thuật Cắt Tỉa Chiến Lược và Tìm Kiếm Cân Bằng Nash

Luận án cũng điều tra kỹ thuật cắt tỉa chiến lược, một phương pháp để giảm kích thước của không gian chiến lược trong các trò chơi lớn. Kỹ thuật này có thể được sử dụng để tìm kiếm các cân bằng Nash xấp xỉ với các giới hạn lỗi thích hợp.

V. Cắt Tỉa Chiến Lược Bằng Cách Lặp Lại J Dominance Trong Lý Thuyết Trò Chơi

Chương 10 điều tra kỹ thuật cắt tỉa chiến lược, một phương pháp để giảm kích thước của không gian chiến lược trong các trò chơi lớn. Kỹ thuật này có thể được sử dụng để tìm kiếm các cân bằng Nash xấp xỉ với các giới hạn lỗi thích hợp. Cắt tỉa chiến lược là một kỹ thuật quan trọng để giải quyết các bài toán tối ưu hóa hệ thống phức tạp, đặc biệt là trong các môi trường phi tập trung.

5.1. Iterated ô Dominance và Xấp Xỉ Cân Bằng

Iterated ô-Dominance là một kỹ thuật cắt tỉa chiến lược, trong đó các chiến lược bị chi phối bởi các chiến lược khác được loại bỏ lặp đi lặp lại cho đến khi không còn chiến lược nào có thể bị loại bỏ. Kỹ thuật này có thể được sử dụng để xấp xỉ các cân bằng Nash trong các trò chơi lớn.

5.2. Triển Khai Iterated ô Dominance và Các Thuật Toán Heuristic

Cheng et al. (2006) đã triển khai Iterated ô-Dominance và phát triển các thuật toán heuristic để tìm kiếm các đường dẫn chi phối. Các thuật toán này có thể được sử dụng để tính toán các giới hạn lỗi chặt chẽ hơn.

5.3. So Sánh Các Thuật Toán GREEDY và Ứng Dụng Trong Trò Chơi Đối Xứng

Nghiên cứu so sánh hiệu suất của các thuật toán GREEDY khác nhau và ứng dụng Iterated ô-Dominance cho các trò chơi đối xứng. Kết quả cho thấy rằng Iterated ô-Dominance có thể là một kỹ thuật hiệu quả để giảm kích thước của không gian chiến lược trong các trò chơi lớn.

VI. Ứng Dụng Phân Bổ Tác Vụ Trong Môi Trường Xử Lý Thông Tin Động

Chương 11 sử dụng phân bổ tác vụ cho môi trường xử lý thông tin động làm ví dụ để minh họa phương pháp luận và chứng minh hiệu quả của nó. Bài toán phân bổ tác vụ được mô hình hóa như một trò chơi thị trường, trong đó các tác nhân đấu thầu để giành quyền thực hiện các tác vụ. Kết quả cho thấy rằng các thị trường có thể phân bổ tác vụ một cách hiệu quả trong các môi trường động.

6.1. Kịch Bản Phân Bổ Tác Vụ Động và Bài Toán Tối Ưu

Bài toán phân bổ tác vụ động được mô tả và mô hình hóa. Các tác nhân được giao các tác vụ một cách độc lập và phải có được các nguồn lực cần thiết thông qua các trao đổi tương ứng.

6.2. Chiến Lược Đấu Thầu Giá Trị Biên và Cơ Chế Thị Trường

Chiến lược đấu thầu giá trị biên được giới thiệu và phân tích. Các cơ chế thị trường khác nhau được sử dụng để điều phối việc phân bổ tác vụ.

6.3. Mô Phỏng Phân Bổ Tác Vụ Động Trong GDL và Kết Quả

Kịch bản phân bổ tác vụ động được mô phỏng trong GDL (Game Definition Language). Kết quả cho thấy rằng các thị trường có thể phân bổ tác vụ một cách hiệu quả trong các môi trường động.