Presentation Information
[2Yin-A-15]Approximating Maximum Cumulative Cost in Online Facility Location Games
〇Eisuke Ota1, Taiki Todo1 (1. kyushu university)
Keywords:
multi agent,facility location,mechanism design
The facility location game is a mathematical model of static multi-agent decision-making where all possible alternatives are distributed over a single line or an interval. However, in the practical scenarios, such a decision is to be made dynamically, and agents' preferences may vary over time. In this paper we consider a new situation where each agent would like to minimize the cumulative cost over time, and focus on approximating the maximum cumulative cost among all the agents. We first propose an online algorithm and show that it is online optimal for the case of two periods and three agents. We than propose a strategy-proof online algorithm and analyze its worst-case performance.