利己的ルーティングにおけるネットワーク構造に基づいた各辺の課税額決定法

摘要

ネットワークを利用する各プレイヤーが，自身の遅延を小さくしようと利己的に経路を選ぶことを利己的ルーティングという．利己的ルーティングにおいては，各プレイヤーの経路選択によって，社会全体の平均遅延を最小にするフロー（最小遅延フロー）をはじめとする目標フローが実現されるとは限らない．そこで，目標フローを実現するためにネットワークを利用するプレイヤーを各経路（各パス）または各辺への課税により制御する手法が提案されている．しかし，各パスへ課税する手法は，すべてのプレイヤーとその選択するパスを区別する必要があり，実現が困難である．一方，各辺へ課税する手法は，各辺において通過するすべてのプレイヤーに区別なく課税することで実現することができる．しかしながら，既存の手法では制約が強く，一般のネットワークに対して任意の目標フローを実現する手法はまだ提案されていない．そこで，本稿では，一般のネットワークにおいて各辺への課税により任意の目標フローを実現する制御手法を提案し，その実現可能条件を明らかにする．