著者

横尾 真 ビンセントコニッツァー トゥオマスサンドホルム 大田 直樹 岩崎 敦

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.47, no.5, pp.1451-1462, 2006-05-15

---

提携を結ぶということは,自動化された利己的な主体(エージェント)の持つ重要な性質である.エージェント間の提携が成立した場合,我々は提携を結んだエージェントの集合が得た利得をどのように分配するかを考える必要がある.協力ゲーム理論はこの利得の分配法について研究してきており,(シャープレイ値やコア,最小コアや仁といった)様々な解概念が提案されてきた.本論文ではこれら既存の解概念が,インターネットのような匿名の開環境の下でエージェントが行える操作に対し,脆弱であることを示す.匿名の開環境ではエージェントは架空名義の利用,共謀,能力の隠蔽といった操作が可能となる.我々はこれらの操作に頑健な新しい解概念である匿名操作不可能コアを提案し,この解概念を特徴づけるいくつかの公理的な条件を示す.また匿名操作不可能コアの条件を緩和した解概念として匿名操作最小コアを提案し,この解概念がつねに非空であることを示す.Coalition formation is a key aspect of automated negotiation among self-interested agents. In order for coalition to be stable, a key question that must be answered is how the gains from cooperation are to be distributed. Various solution concepts (such as the Shapley value, core, least core, and nucleolus) have been proposed. In this paper, we demonstrate how these concepts are vulnerable to various kinds of manipulations in open anonymous environments such as the Internet. These manipulations include submitting false names (one acting as many), collusion (many acting as one), and the hiding of skills. To address these threats, we introduce a new solution concept called the anonymity-proof core, which is robust to these manipulations. We show that the anonymity-proof core is characterized by certain simple axiomatic conditions. Furthermore, we show that by relaxing these conditions, we obtain a concept called the least anonymity-proof core, which is guaranteed to be non-empty.