電子情報通信学会総合大会講演要旨
D-1-7
ブロックごとに分かれた利用時間の希望割り当て問題
○稲永隆大・真鍋義文(工学院大)
大学の教室の貸出などの、ブロックごとに分かれた利用時間を、希望者に割り当てる問題を考察する。従来の研究では時間はインターバルでモデル化され、任意の長さに分割可能という仮定のもとで、戦略的操作不可能性かつパレート効率性を満足するメカニズムを、ケーキ分割アルゴリズムを利用して考案された。しかし、大学の教室の貸出などの利用時間がブロックで規定されている場合において上記の性質をもつ割り当てが可能であるかは不明であった。本稿では戦略的操作不可能性かつ(1) パレート最適性を満足するがenvy-free を満足しない、または(2)envy-free を満足するがパレート最適性は満足しない、のどちらかであれば達成可能なプロトコルを構成できることを述べる。