[4D2-GS-11] AIと社会

[4D2-GS-11-04] 誘因両立性・個人合理性・予算制約を満たす多項式時間ライドシェアリングメカニズム

〇岩瀬 竜也¹、Sebastian Stein²、Enrico Gerding² (1. トヨタモーターヨーロッパ、2. サウサンプトン大学)

キーワード：メカニズムデザイン、ゲーム理論、ライドシェアリング、交通

ライドシェアリングは渋滞や大気汚染の軽減し、交通を効率化する手段として期待されている。ライドシェアリングを実現するためには、特定の利用者に遠回りを促すインセンティブを与え、車の割り当てを最適化するようなメカニズムが必要となる。しかしながらVCGや貪欲法などの標準的なメカニズムを単純に適用するだけでは、誘因両立性、個人合理性、予算制約、多項式時間計算量の4つの性質を同時に満たすことができない。この課題に対し本研究では、4つの性質をすべて満たし、かつ最適解に比べ社会コストを平均8.6%以内に収める新しいライドシェアリングメカニズムを提案した。