圖論中的最大獨立集合(maximal independent set)問題是從一個無向圖G 中的節點 集合V挑選部分的節點集合S，需滿足在S 當 中不存在任何兩節點相鄰且S 不為其它任一 獨立集合的子集合。本篇論文透過賽局理論 (game theory)尋求較佳的最大獨立集合問題 解。我們接著將賽局設計轉換為在分散式系統 中運作的自我穩定演算法。自我穩定 (self-stabilization)的性質可以保證不論系統初 始狀態為何，必定會在有限的時間內到達穩定 的合法狀態，即最大獨立集合。為了使我們提 出的方法能在MANET 中有效的實作，需另外 再對演算法進行修改以克服環境上的差異。模 擬實驗結果顯示我們提出的演算法有較好的 效能表現，比先前的方法有較多的最大獨立集 合節點數以及較短的收斂時間。

Given an undirected graph G = (V, E), S Í V is an independent set if no nodes in S are adjacent to one another. An independent set S is maximal if no proper subset of S is an independent set. Maximal independent set problem is to find such a set S. This paper proposes a solution to this problem based on game theory. We turn the solution into a self-stabilizing algorithm running in distributed systems. The self-stability property ensures that system will enter legitimate system states in limited time regardless of initial configurations. We then convert the algorithm into a protocol that runs under MANET environment. Simulation results indicate that the proposed protocol performs better than previous work in terms of independent set size and convergence time.