提携の実現可能性を考慮した最小コスト全域木問題について

摘要

本研究では，最小コスト全域木問題（以下，最小木問題と略記する）についての考察する．最小木問題では，地理的に離れた場所に位置するエージェントの集合が，ソースと呼ばれる共通の供給源から資源を得たいとする状況を考えている．エージェントはできる限りコストを抑え，ソースに直接，または他のエージェントを通して間接的に接続する．つまり，最小コスト全域木（以下最小木と略記する）が考えられる．最小木問題では，最小木を構築する接続方法の問題と，そのコストをエージェント間でどのように合理的な分配するかという分配方法の問題が生じる．接続問題の解決策として，最小木を構築するアルゴリズムが提案されている．分配問題の解決策であるコストの分配ルールに関して過去に様々な研究がなされてきた．また，最小木問題は，エージェント間のコストが非対称となる最小コスト全域有向木問題（以下，最小有向木問題と略記する）に拡張されている．