信用交渉における公開木戦略の計算量
山本 有輝 (0551132)
ネットワーク上で不特定多数のユーザに対してサービスを提供するような応用が増えている．しかし，従来のIDとパスワードによる認証などでは，未知のユーザに対する適切な権限割り当てが困難である．そこで，ユーザが持つ信任状に基づいて権限割り当てを行う技術である信用管理の必要性が生じてきた．信用交渉とは，サービス提供者とサービス要求者の両者が信任状の交換を繰り返して徐々に信用を確立する，信用管理のアプローチのひとつである．信用交渉における戦略とは，それまでに交換した信任状と自身のポリシーに対して，次に相手に公開する信任状を返すような写像である．Yuらは，DTファミリーという戦略の集合を提案し，それが戦略集合として望ましい性質を満たすことを示した．DTSは，DTファミリーの中で，相手に公開する情報が最も少ない，すなわち最も慎重な戦略である．DTSは単純な実装では指数的な計算量がかかるが，効率のよい実装が存在するかどうかや，計算量の下界は，これまで知られていなかった．本研究では，Yuらの枠組の再定式化を行い，DTSの計算量の上界および下界について考察した．その結果，Yuらの定義に従った場合にはDTSはNP困難であること，また，交渉を成功に導くことに貢献しない出力を除外するよう条件を変えた場合には多項式可解であることがわかった．発表では，信用交渉およびDTSについて説明した後，問題の設定を変えた場合にDTSの計算量がどのように変化するかを説明する．