基於賽局理論的人機協力演算法策略分析與評估

Abstract

儘管近幾十年來，電腦科學有相當長足的發展，還是有一些問題沒辦法用電腦有效的解決。像是圖形辨識(image recognition)或是常識推理(common sense reasoning)，這些對於人類來說相當容易的問題，目前為止卻沒有一個很好的方法可以用電腦自動的解決。這篇論文嘗試利用遊戲來向玩家收集資訊，並且進一步利用這些資訊來解決電腦難以處理的問題。 為了達成這個目的，我們設計了一個多人網路線上遊戲 PhotoSlap 來幫助我們將相同人的照片群聚(cluster)起來。利用 PhotoSlap 所產生出來的資訊，我們可以進一步達成照片標註(photo annotation)。過去也有一些研究利用遊戲來收集照片註解，這篇論文主要的不同點在於：利用賽局理論對遊戲設計進行了分析，並且證明了這樣的遊戲設計會符合subgame perfect equilibrium，也就是說只要是理性想得高分的玩家，便會貢獻出正確的資訊。最後我們請了四組焦點團體(focus group)來進行實驗，實驗結果驗證了遊戲設計的合理性，以及所獲得資料的正確性。

Despite impressive advancement in computer technology, there are still limitations on the capabilities of computers. Tasks like image recognition or common sense reasoning are trival for humans, but present challenges on even the fastest computer today. This thesis aims to explore the power of human Computation and shows how human brain powers can be utilized to solve problems that are hard for computers. A multi-player online game, PhotoSlap, is designed to achieve the task of semantic clustering and therefore accomplishes photo annotation. This research extends human computation research in incentive analysis with a game theoretic approach. In particular, PhotoSlap can be shown to reach emph{subgame perfect equilibrium} with the target strategy when players are rational and not collusive. Experiments involving four focus groups have been conducted, and the preliminary results demonstrated the game design to be reasonable and therefore produce useful information.