Tổng quan luận án

Luận án tiến sĩ kỹ thuật công nghiệp và nghiên cứu vận trù (Industrial and Operations Engineering) của tác giả Shih-Fen Cheng, bảo vệ năm 2006 tại Đại học Michigan (The University of Michigan), tập trung vào việc nghiên cứu và phát triển các phương pháp lý thuyết trò chơi nhằm tối ưu hóa các hệ thống nhân tạo phức tạp (complex artificial systems). Theo định nghĩa của tác giả, một hệ thống nhân tạo phức tạp sở hữu ba đặc tính cố hữu: (1) hệ thống chỉ có thể được mô hình hóa dưới dạng mô phỏng; (2) quy mô bài toán quá lớn khiến việc giải chính xác bằng mô hình giải tích trở nên bất khả thi trong thực tế; (3) các thông tin cần thiết phục vụ việc giải quyết vấn đề bị phân tán về bản chất. Khoảng trống nghiên cứu được xác định từ thực tế là các phương pháp tối ưu hóa cổ điển và các thuật toán tìm nghiệm chính xác bị tắc nghẽn bởi sự bùng nổ tổ hợp của không gian quyết định, đồng thời thiếu khả năng điều phối hiệu quả sự tương tác phức tạp giữa các bài toán con khi phân rã hệ thống.

Luận án phân chia phạm vi nghiên cứu thành hai nhóm bài toán chính với các mục tiêu và câu hỏi nghiên cứu cụ thể:

  1. Đối với nhóm bài toán tập trung (Centralized problems):
    • Làm thế nào để phân rã bài toán tối ưu hóa và quy trình tổng quát để giải bài toán trong bối cảnh hệ thống phức tạp là gì?
    • Các đặc tính của nghiệm thu được thông qua cách tiếp cận lý thuyết trò chơi có tính chất gì?
    • Độ phức tạp tính toán khi tìm nghiệm trong các bài toán đã phân rã ra sao và tương quan thế nào so với các thuật toán tìm nghiệm tối ưu toàn cục khác?
  2. Đối với nhóm bài toán phân tán (Distributed problems):
    • Thị trường phân bổ tài nguyên hiệu quả như thế nào khi so sánh với các cơ chế thay thế và phân bổ tập trung toàn cục?
    • Làm thế nào để nhận diện và định lượng các nguồn gốc gây tổn thất hiệu quả trong cơ chế 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 chặn sai số phù hợp) nhằm tìm kiếm cân bằng Nash trong một trò chơi quy mô lớn?

Đối tượng nghiên cứu là các hệ thống vận hành và phân bổ tài nguyên quy mô lớn, bao gồm dây chuyền sản xuất công nghiệp, mạng lưới điều khiển tín hiệu giao thông đô thị và hệ thống phân bổ tác vụ động. Phạm vi không gian và thực nghiệm bao gồm: dây chuyền lắp ráp ô tô tại nhà máy Lansing Grand River của tập đoàn General Motors; mạng lưới giao thông thực tế của thành phố Troy, tiểu bang Michigan (gồm 529 liên kết, 200 nút giao và 72 tâm phân vùng); môi trường giao dịch thị trường mô phỏng trên nền tảng AB3D thông qua Ngôn ngữ định nghĩa trò chơi (Game Definition Language - GDL). Dữ liệu nghiên cứu phản ánh các tham số vận hành công nghiệp và hạ tầng giao thông ở giai đoạn những năm 2004–2006.

Tổng quan tài liệu và vị trí của luận án

Tổng quan tài liệu của luận án hệ thống hóa các nền tảng toán học và kỹ thuật tối ưu hóa từ kinh tế học và khoa học máy tính:

  • Lý thuyết trò chơi cổ điển: von Neumann và Morgenstern (1947) đặt nền tảng mô hình hóa tương tác giữa các tác nhân duy lý; Nash (1950) chứng minh sự tồn tại của điểm cân bằng trong trò chơi dạng chiến lược hữu hạn. Fudenberg và Tirole (1991) cung cấp khung phân tích chuẩn tắc về cân bằng Nash và các trò chơi đối xứng.
  • Học máy trong lý thuyết trò chơi: Thuật toán chơi giả định (Fictitious Play - FP) khởi nguồn từ Brown (1951); Monderer và Shapley (1996) chứng minh tính hội tụ của FP trong trò chơi có cùng lợi ích (games of identical interests). Lambert, Epelman và Smith (2005) đề xuất biến thể chơi giả định lấy mẫu (Sampled Fictitious Play - SFP) nhằm vượt qua rào cản tính toán phản ứng tối ưu trên phân phối niềm tin liên tục.
  • Tính toán cân bằng và phần mềm: McKelvey và McLennan (1996) phát triển bộ công cụ tính toán GAMBIT nhằm giải cân bằng Nash.
  • Phát triển thuật toán metaheuristic: Glover (1986) khởi xướng khái niệm metaheuristic với phương pháp tìm kiếm Tabu (tabu search); Dréo và cộng sự tổng hợp các thuật toán phỏng sinh học và tôi luyện thép (simulated annealing).
  • Lập kế hoạch trong sản xuất: Cheung và cộng sự (2004) nghiên cứu gián đoạn sản xuất trong công nghiệp hóa chất.
  • Phương pháp phân tích kinh tế thực nghiệm: MacKie-Mason và Wellman (2006) thiết lập phương pháp luận phân tích trò chơi thực nghiệm (empirical game-theoretic analysis).

Khoảng trống mà luận án lựa chọn giải quyết nằm ở điểm giao thoa giữa tối ưu hóa mô phỏng và lý thuyết trò chơi: (1) thiếu vắng một công cụ định lượng hỗ trợ nhà quản lý quyết định có nên mô hình hóa tính ngẫu nhiên hay không trước khi tăng độ phức tạp của mô hình; (2) thuật toán SFP chưa từng được song song hóa để áp dụng cho các hàm mục tiêu hộp đen (black-box) từ phần mềm mô phỏng giao thông chi tiết; (3) thuật toán SFP nguyên bản chưa có cơ chế xử lý các ràng buộc phức tạp (non-trivial constraints) trong các bài toán quy hoạch động quy mô lớn; (4) thiếu các kỹ thuật cắt tỉa chiến lược hiệu quả có giới hạn sai số lý thuyết phục vụ việc tìm kiếm cân bằng Nash trong các trò chơi thị trường mô phỏng phức tạp.

Cơ sở lý thuyết và phương pháp nghiên cứu

Luận án sử dụng các hệ thống lý thuyết và công cụ phân tích sau:

  • Khung lý thuyết trò chơi dạng chiến lược (Strategic form games): Định nghĩa bởi bộ $\Gamma = [N, {S_i}, {u_i(s)}]$, với $N$ là tập người chơi, $S_i$ là tập chiến lược khả thi của người chơi $i$, và $u_i(s)$ là hàm hữu dụng. Luận án phân tích sâu hai lớp trò chơi đặc biệt: trò chơi có cùng lợi ích (games of identical interests: $u_1(s) = u_2(s) = \dots = u_n(s)$) và trò chơi đối xứng (symmetric games). Trạng thái nghiệm là cân bằng Nash và cân bằng $\epsilon$-Nash ($\epsilon$-NE).
  • Thuật toán chơi giả định lấy mẫu (Sampled Fictitious Play - SFP): Phân rã bài toán tối ưu hóa tổng quát thành các bài toán con tương ứng với các người chơi. Các biến thể kích thước mẫu $k=1$ được áp dụng để người chơi cập nhật chiến lược bằng cách chọn phản ứng tối ưu (best reply) đối với một chiến lược ngẫu nhiên rút ra từ lịch sử chơi của đối thủ.
  • Quá trình quyết định Markov (Markov Decision Process - MDP) và Ánh xạ không gian khả thi (Feasible Space Mapping): Phân rã MDP tổng thể thành các mô-đun chức năng tương tác và thiết lập quy tắc chiếu các quyết định không khả thi về biên không gian cho phép.
  • Phương pháp $\delta$-thống trị lặp (Iterated $\delta$-Dominance): Khung giảm không gian chiến lược kết hợp chương trình quy hoạch tuyến tính LP-A($S, T$) để xác định ngưỡng sai số $\delta$ nhỏ nhất khi loại bỏ tập chiến lược bị thống trị.

Phương pháp nghiên cứu thực nghiệm:

  • Mô phỏng số và tối ưu hóa dựa trên mô phỏng (Simulation-based optimization): Sử dụng phần mềm mô phỏng vi mô giao thông INTEGRATION-UM để đánh giá hàm mục tiêu thời gian di chuyển.
  • Kỹ thuật tính toán song song: Phân tán việc đánh giá hàm phản ứng tối ưu của SFP trên các cụm bộ vi xử lý để đáp ứng yêu cầu tối ưu hóa theo thời gian thực.
  • Nguồn tư liệu và dữ liệu: Mô hình đồ thị tuyến tính thực tế tại nhà máy ô tô GM Lansing Grand River; tệp topo mạng lưới thành phố Troy, Michigan; nền tảng mô phỏng thị trường AB3D (Agent-Based Auction Artifacts and Design) cùng Ngôn ngữ định nghĩa trò chơi (GDL).

Nội dung chính theo từng chương

Chương 1: Introduction

Chương này xác định phạm vi nghiên cứu về các hệ thống nhân tạo phức tạp, chỉ ra giới hạn của các nỗ lực đơn giản hóa mô hình giải tích khi tính trung thực của mô hình bị vi phạm. Tác giả luận chứng rằng phân rã bài toán dựa trên lý thuyết trò chơi là công cụ trung tâm để giải quyết cả bài toán tập trung (thông qua trò chơi có cùng lợi ích) và bài toán phân tán (thông qua cơ chế thị trường).

Chương 2: Preliminaries: Basics of Game Theory

Chương trình bày các định nghĩa toán học nền tảng: trò chơi dạng chiến lược hữu hạn $\Gamma = [N, {S_i}, {u_i(s)}]$, chiến lược hỗn hợp $\Delta_i$, mở rộng hữu dụng kỳ vọng $u_i(f)$, định nghĩa cân bằng Nash (Định nghĩa 2.1) và cân bằng $\epsilon$-Nash (Định nghĩa 2.2). Tác giả định nghĩa đường niềm tin (belief path), tính hội tụ về cân bằng, khái niệm trò chơi có cùng lợi ích (Định nghĩa 2.3) và trò chơi đối xứng (Định nghĩa 2.4).

Chương 3: When to Include Stochasticity: A Case Study of End-State Planning Problem in Production Lines

Chương xây dựng mô hình lập kế hoạch trạng thái kết thúc (end-state planning) cho dây chuyền sản xuất nối tiếp tại nhà máy General Motors Lansing Grand River. Hệ thống gồm $N=66$ phần tử tuyến tính (chia thành vùng khoang động cơ - EC và vùng gầm xe - UB), xử lý $J=200$ thân xe với thời gian ca làm việc mong muốn $T_d = 4.200$ giây và ngưỡng dừng tối đa $T_{\max} = 4.800$ giây. Chi phí sản xuất thiếu là 10 đơn vị/phút, chi phí làm thêm giờ là 5 đơn vị/phút. Tổng cộng có 93 mục tiêu trạng thái kết thúc với các mức điểm: thấp (thưởng 1, phạt 1), trung bình (thưởng 5, phạt 3), cao (thưởng 20, phạt 7).

Thuật toán quy hoạch động (DP) xác định giải bài toán trong 90 giây trên máy tính Pentium-4 3,4 GHz chạy Linux. Dây chuyền dừng tại 4.189 giây (sớm 11 giây), hoàn thành 69/93 mục tiêu với giá trị ròng 189 điểm. Khi so sánh với quy tắc kinh nghiệm hiện trường (dừng sát thời điểm $T_d$), quy tắc kinh nghiệm dừng đúng 4.200 giây nhưng số mục tiêu đạt được giảm xuống 65 và giá trị ròng giảm còn 156 điểm.

Để đánh giá nhu cầu ngẫu nhiên hóa, tác giả mô phỏng tham số hỏng hóc bằng phân phối mũ với số chu kỳ trung bình giữa hai sự cố (MCBF) và thời gian sửa chữa trung bình (MTTR). Qua 30 mẫu thử nghiệm ngẫu nhiên độc lập, giá trị kỳ vọng của mô hình thông tin hoàn hảo bằng giá trị kỳ vọng của mô hình tiền định ($EV_{pi} = EV_d$). Theo bất đẳng thức $EV_s - EV_d \le EV_{pi} - EV_d$, chênh lệch bằng 0, chứng minh rằng việc đưa tính ngẫu nhiên vào mô hình không mang lại lợi ích gia tăng trong trường hợp này.

Chỉ số đánh giá Chính sách tối ưu từ DP Quy tắc kinh nghiệm hiện trường
Thời điểm dừng dây chuyền ($T_s$) 4.189 giây 4.200 giây
Số mục tiêu hoàn thành (trên 93 mục tiêu) 69 mục tiêu 65 mục tiêu
Tổng giá trị điểm ròng thu được 189 điểm 156 điểm
Thời gian chạy thuật toán 90 giây —

Chương 4: An Introduction to the Sampled Fictitious Play Algorithm

Chương trình bày cấu trúc của thuật toán SFP đối với bài toán tối ưu hóa tổ hợp quy mô lớn. Tác giả chuyển đổi bài toán tối ưu hóa có hàm mục tiêu dùng chung thành một trò chơi có cùng lợi ích giữa các biến quyết định. Thay vì tính toán phản ứng tối ưu trên toàn bộ ma trận thanh toán hoặc phân phối niềm tin đầy đủ, thuật toán SFP tại mỗi bước lặp rút ngẫu nhiên mẫu kích thước $k=1$ từ lịch sử chơi để tìm phản ứng tốt nhất, đảm bảo tính hội tụ về cân bằng Nash tương đương với cực tiểu cục bộ theo tọa độ.

Chương 5: Optimizing Large Scale Simulations by Parallel Computing

Chương phát triển thuật toán CoSIGN dựa trên SFP song song để giải bài toán điều phối tín hiệu giao thông đô thị trên mạng lưới thành phố Troy, Michigan (529 liên kết, 200 nút giao, 72 tâm phân vùng) mô phỏng bằng INTEGRATION-UM. SFP phân tán việc chạy mô phỏng đánh giá phản ứng tốt nhất của từng nút giao thông tới $K$ bộ vi xử lý. Khi so sánh với thuật toán Hạ tọa độ (Coordinate Descent - CD), CoSIGN đạt được giá trị thời gian di chuyển trung bình thấp hơn rõ rệt trong các kịch bản lưu lượng nhẹ, bình thường và nặng khi cho cùng một khoảng thời gian đồng hồ thực (wall-clock time).

Chương 6: Approximate Large-Scale Dynamic Programming: A Special Case

Chương giải quyết bài toán tối ưu hóa liên kết (Joint Optimization Problem) trong sản xuất công nghiệp xe hơi bằng cách mô hình hóa thành một MDP quy mô lớn gồm 4 mô-đun: Đầu tư vốn (Capital Investment), Lập lịch sản xuất (Production Scheduling), Quản trị doanh thu (Revenue Management), và Kế hoạch bán hàng (Sales Planning). Luận án đề xuất kỹ thuật "Ánh xạ không gian khả thi" (Feasible Space Mapping) nhằm xử lý các ràng buộc liên kết không tầm thường giữa các mô-đun khi áp dụng SFP. Thực nghiệm số cho thấy bộ giải SFP tìm được nghiệm có chất lượng tương đương bộ giải MDP toàn cục nhưng với tốc độ thực thi nhanh hơn nhiều bậc độ lớn.

Chương 7: Sampled Fictitious Play: Conclusions and Future Work

Chương tổng kết các đóng góp của Phần I, khẳng định tính khả thi của SFP trong tối ưu hóa mô phỏng hộp đen và xấp xỉ quy hoạch động quy mô lớn nhờ khả năng song song hóa tự nhiên. Hướng nghiên cứu mở rộng bao gồm việc thiết lập các điều kiện biên chặt hơn cho ánh xạ không gian khả thi trong các cấu trúc ràng buộc phi tuyến tính phức tạp.

Chương 8: Market-Based Approach: An Introduction

Chương mở đầu Phần II bằng việc phân tích bài toán phân bổ tài nguyên phân tán (Decentralized Resource Allocation). Tác giả làm rõ các thách thức khi thông tin về chi phí, sở thích và năng lực bị phân tán tại các tác nhân độc lập, từ đó thiết lập luận cứ cho việc sử dụng cơ chế thị trường như một giao thức điều phối tài nguyên có khả năng tự tổ chức.

Chương 9: Market-Based Approach: An Empirical Methodology

Chương hệ thống hóa quy trình phân tích lý thuyết trò chơi thực nghiệm bao gồm: lựa chọn cơ chế lặp (iterative mechanism selection), thiết kế chiến lược tác nhân, chạy mô phỏng Monte Carlo để ước lượng ma trận thanh toán thực nghiệm, và giải tìm cân bằng Nash thực nghiệm trên các mô hình mô phỏng.

Chương 10: Strategy Reduction by Iterated $\delta$-Dominance

Chương phát triển kỹ thuật cắt tỉa chiến lược bằng $\delta$-thống trị lặp nhằm giảm chiều không gian chiến lược trước khi tính toán cân bằng. Tác giả xây dựng chương trình quy hoạch tuyến tính LP-A($S, T$) để tìm giá trị $\delta$ tối thiểu mà tại đó một tập chiến lược $T$ bị thống trị bởi tập $S$. Hai thuật toán heuristic lòng tham được đề xuất: GREEDY-1 (loại từng chiến lược có $\delta$ nhỏ nhất ở mỗi bước) và GREEDY-2 (loại $k$ chiến lược đồng thời). Kỹ thuật này cung cấp các chặn sai số lý thuyết chặt chẽ cho nghiệm xấp xỉ cân bằng Nash thu được.

Chương 11: Task Allocation for Dynamic Information Processing Environments: A Motivational Example

Chương áp dụng phương pháp tiếp cận thị trường vào bài toán phân bổ tác vụ động trong môi trường xử lý thông tin. Mô hình sử dụng cấu trúc thị trường hai giai đoạn: Giai đoạn chuẩn bị sử dụng cơ chế Đấu giá tăng dần đồng thời (Simultaneous Ascending Auctions - SAA) để các tác nhân phác thảo kế hoạch ban đầu; giai đoạn lập kế hoạch chuyển đổi toàn bộ sang cơ chế Đấu giá kép liên tục (Continuous Double Auctions - CDA) khi thông tin tác vụ đến theo thời gian thực. Các tác nhân sử dụng chiến lược đặt giá theo giá trị biên (Marginal-Value Bidding). Toàn bộ kịch bản được định nghĩa bằng Ngôn ngữ định nghĩa trò chơi (GDL) và chạy trên nền tảng mô phỏng AB3D.

Chương 12: Market-Based Approach: Conclusions and Future Work

Chương tổng kết các kết quả của Phần II, xác nhận hiệu quả phân bổ của cơ chế thị trường hai giai đoạn SAA-CDA và vai trò của kỹ thuật cắt tỉa $\delta$-thống trị trong việc giảm chi phí tính toán trò chơi thực nghiệm. Tác giả kiến nghị nghiên cứu sâu hơn về các cơ chế định giá biên khi tác nhân có cấu trúc sở thích phụ thuộc phi tuyến.

Kết quả và những đóng góp mới

Luận án nêu rõ các đóng góp học thuật về lý luận và thực tiễn:

  1. Quy trình định lượng quyết định mô hình hóa ngẫu nhiên: Xây dựng phương pháp đo lường khoảng cách kỳ vọng giữa mô hình thông tin hoàn hảo và mô hình tiền định ($EV_{pi} - EV_d$) làm cận trên cho lợi ích tiềm năng của mô hình ngẫu nhiên ($EV_s - EV_d$), giúp loại bỏ việc xây dựng các mô hình ngẫu nhiên phức tạp khi không đem lại hiệu quả vượt trội.
  2. Khung tối ưu hóa mô phỏng bằng SFP song song: Chuẩn hóa thuật toán CoSIGN ứng dụng SFP vào bài toán điều khiển tín hiệu giao thông đô thị; chứng minh tính mở rộng quy mô thông qua tính toán song song trên mạng lưới thực tế (Troy, Michigan) với thời gian tính toán đáp ứng yêu cầu vận hành so với thuật toán Coordinate Descent.
  3. Phương pháp ánh xạ không gian khả thi cho quy hoạch động xấp xỉ: Giải quyết vấn đề ràng buộc phi tầm thường giữa các mô-đun trong MDP quy mô lớn, cho phép SFP tìm ra chính sách kiểm soát chất lượng cao với tốc độ nhanh hơn nhiều lần so với các thuật toán toàn cục truyền thống.
  4. Phương pháp cắt tỉa chiến lược bằng $\delta$-thống trị lặp: Thiết lập cơ sở toán học và hai thuật toán heuristic GREEDY-1, GREEDY-2 giải bài toán quy hoạch tuyến tính LP-A($S, T$), cho phép tính toán xấp xỉ cân bằng Nash có giới hạn sai số tường minh trong các trò chơi thực nghiệm quy mô lớn.
  5. Kiến trúc cơ chế thị trường hai giai đoạn: Đề xuất và kiểm chứng cơ chế kết hợp SAA và CDA ứng dụng cho bài toán phân bổ tác vụ xử lý thông tin động thông qua ngôn ngữ GDL và nền tảng AB3D.

Hạn chế và hướng nghiên cứu tiếp

Văn bản luận án nêu rõ các giới hạn phạm vi nghiên cứu:

  • Mô hình lập kế hoạch trạng thái kết thúc (Chương 3) chỉ áp dụng cho cấu trúc dây chuyền sản xuất tuyến tính (serial line topology); chưa tổng quát hóa cho các cấu trúc phân nhánh hoặc có đường hồi lưu phức tạp.
  • Thuật toán SFP trong Phần I phụ thuộc vào giả định trò chơi có cùng lợi ích; tính hội tụ chưa được bảo đảm trên các lớp trò chơi tổng quát có xung đột lợi ích sâu sắc giữa các tác nhân phân tán.
  • Kỹ thuật ánh xạ không gian khả thi trong xấp xỉ MDP (Chương 6) được thiết kế chuyên biệt cho cấu trúc ràng buộc của bài toán sản xuất ô tô cụ thể, chưa mở rộng thành bộ giải đa năng cho mọi dạng ràng buộc phi tuyến tính tổng quát.
  • Các hướng nghiên cứu tiếp theo bao gồm việc mở rộng việc đánh giá mẫu $k > 1$ trong SFP song song, nghiên cứu tính hội tụ của SFP trong các hệ thống mạng không đồng nhất và hoàn thiện bộ từ vựng GDL cho các luật đấu giá phức hợp.

Giá trị tham khảo

Luận án có giá trị tham khảo chuyên môn đối với các nhóm đối tượng:

  • Nghiên cứu sinh và nhà nghiên cứu vận trù học / khoa học máy tính: Tham khảo Chương 4 và Chương 10 về kỹ thuật toán học triển khai thuật toán SFP và quy hoạch tuyến tính giải bài toán $\delta$-thống trị lặp để tìm xấp xỉ cân bằng Nash.
  • Kỹ sư công nghiệp và quản lý sản xuất: Tham khảo Chương 3 để áp dụng công thức quy hoạch động giải bài toán điều độ dây chuyền dừng máy (shutdown schedule) và quy trình định lượng giá trị ngẫu nhiên trước khi xây dựng mô hình phức tạp.
  • Kỹ sư giao thông và quy hoạch đô thị: Tham khảo Chương 5 về cách thức ghép nối bộ mô phỏng giao thông INTEGRATION-UM với thuật toán tối ưu hóa song song CoSIGN để thiết lập lịch tín hiệu đèn phối hợp.
  • Chuyên gia thiết kế cơ chế thị trường và hệ thống phân tán: Tham khảo Chương 9 và Chương 11 về phương pháp luận phân tích trò chơi thực nghiệm, cấu trúc đấu giá chuyển đổi hai giai đoạn (SAA sang CDA) và quy cách đặc tả thị trường bằng GDL trên AB3D.

Câu hỏi thường gặp

1. Luận án định lượng giá trị của việc đưa tính ngẫu nhiên vào mô hình như thế nào?
Tại Chương 3, tác giả sử dụng bất đẳng thức $EV_s - EV_d \le EV_{pi} - EV_d$, trong đó $EV_{pi}$, $EV_s$, và $EV_d$ lần lượt là hiệu năng kỳ vọng của mô hình thông tin hoàn hảo, mô hình ngẫu nhiên và mô hình tiền định. Bằng việc chạy 30 kịch bản mô phỏng Monte Carlo với thời gian hỏng hóc và sửa chữa phân phối mũ, thực nghiệm ghi nhận $EV_{pi} = EV_d$, suy ra $EV_s - EV_d \le 0$, chứng minh rằng việc đưa tính ngẫu nhiên vào không mang lại giá trị gia tăng trong bối cảnh thực nghiệm này.

2. Thuật toán CoSIGN tối ưu hóa tín hiệu giao thông dựa trên nguyên lý nào và thử nghiệm ở đâu?
CoSIGN (Chương 5) chuyển đổi bài toán điều khiển tín hiệu phối hợp thành trò chơi có cùng lợi ích giữa các nút giao thông, áp dụng thuật toán SFP với mẫu ngẫu nhiên kích thước 1 từ lịch sử để cập nhật kế hoạch tín hiệu. Hàm mục tiêu đánh giá bằng phần mềm mô phỏng vi mô INTEGRATION-UM và được tính toán song song trên $K$ bộ xử lý. Mô hình được kiểm thử trên mạng lưới thành phố Troy, Michigan gồm 529 liên kết, 200 nút giao và 72 tâm phân vùng.

3. Khái niệm "Ánh xạ không gian khả thi" (Feasible Space Mapping) trong Chương 6 giải quyết vấn đề gì?
Thuật toán SFP thông thường chỉ áp dụng thuận lợi cho các bài toán tối ưu hóa không ràng buộc hoặc ràng buộc hộp đơn giản. Trong bài toán MDP liên kết gồm 4 mô-đun sản xuất ô tô, các biến quyết định chịu ràng buộc phi tầm thường (non-trivial constraints). Kỹ thuật ánh xạ không gian khả thi được thiết lập để chiếu các quyết định không khả thi phát sinh trong quá trình phản ứng tốt nhất về miền hợp lệ, duy trì tính hội tụ của SFP mà không làm mất đi tính khả thi của hệ thống tổng thể.

4. Kỹ thuật cắt tỉa chiến lược bằng $\delta$-thống trị lặp hoạt động như thế nào?
Được trình bày tại Chương 10, phương pháp này sử dụng mô hình quy hoạch tuyến tính LP-A($S, T$) để tìm độ lệch $\delta$ nhỏ nhất mà một tập chiến lược $T$ bị thống trị bởi tập $S$. Thông qua hai thuật toán tham lam GREEDY-1 (loại từng chiến lược) và GREEDY-2 (loại cụm $k$ chiến lược), không gian chiến lược của trò chơi thực nghiệm được thu nhỏ dần trong khi vẫn bảo đảm các chặn sai số toán học cho nghiệm cân bằng Nash xấp xỉ.

5. Cơ chế thị trường hai giai đoạn trong Chương 11 được thiết kế ra sao?
Cơ chế phục vụ bài toán phân bổ tác vụ động trong môi trường xử lý thông tin gồm: (1) Giai đoạn chuẩn bị (preparation phase) sử dụng cơ chế đấu giá tăng dần đồng thời (SAA) để các tác nhân lập kế hoạch ban đầu; (2) Giai đoạn lập kế hoạch trực tuyến (planning phase) chuyển đổi toàn bộ thị trường sang cơ chế đấu giá kép liên tục (CDA) để xử lý các tác vụ phát sinh động theo thời gian thực. Tác nhân tham gia đấu giá sử dụng chiến lược định giá theo giá trị biên (Marginal-Value Bidding) và toàn bộ môi trường được mô phỏng qua ngôn ngữ GDL trên nền tảng AB3D.

Kết luận

Luận án của Shih-Fen Cheng đã phát triển khung phương pháp luận lý thuyết trò chơi nhằm giải quyết các bài toán tối ưu hóa phức tạp trong cả cấu trúc tập trung lẫn phân tán. Bằng việc kết hợp thuật toán chơi giả định lấy mẫu (SFP) song song hóa, quy hoạch động phân rã với ánh xạ không gian khả thi, và kỹ thuật cắt tỉa $\delta$-thống trị lặp trong thị trường mô phỏng thực nghiệm, công trình cung cấp các giải pháp tính toán hiệu quả cho các bài toán quy mô lớn. Các kết quả thực nghiệm trên hệ thống lắp ráp ô tô của General Motors, mạng lưới giao thông thành phố Troy và môi trường đấu giá AB3D xác nhận tính ứng dụng thực tiễn của các mô hình được đề xuất.