论文标题
与客户的战略设施位置，以最大程度地减少总等待时间
Strategic Facility Location with Clients that Minimize Total Waiting Time
论文作者
论文摘要
我们研究了一个不合作的双面设施位置游戏，其中设施和客户在战略上行事。这与许多其他设施的位置游戏形成鲜明对比的是，客户只需访问其最接近的设施。设施代理选择图表上的位置以打开设施以吸引尽可能多的购买力，而客户代理人选择通过战略性地分配其购买力来降低其总等待时间来获得光顾的设施。在这里，设施的等待时间取决于其收到的总购买力。我们表明，我们的客户阶段是一个可分解的交通拥堵游戏，这意味着对客户平衡的存在，独特性和有效的计算。因此，设施代理可以有效地预测客户的行为并相应地做出战略决策。尽管如此，我们证明了该游戏的所有情况下都不存在子游戏的完美平衡，并且它们的存在是NP的决定。从积极的一面来看，我们提供了一种简单有效的算法来计算3个体重的子游戏完美平衡。
We study a non-cooperative two-sided facility location game in which facilities and clients behave strategically. This is in contrast to many other facility location games in which clients simply visit their closest facility. Facility agents select a location on a graph to open a facility to attract as much purchasing power as possible, while client agents choose which facilities to patronize by strategically distributing their purchasing power in order to minimize their total waiting time. Here, the waiting time of a facility depends on its received total purchasing power. We show that our client stage is an atomic splittable congestion game, which implies existence, uniqueness and efficient computation of a client equilibrium. Therefore, facility agents can efficiently predict client behavior and make strategic decisions accordingly. Despite that, we prove that subgame perfect equilibria do not exist in all instances of this game and that their existence is NP-hard to decide. On the positive side, we provide a simple and efficient algorithm to compute 3-approximate subgame perfect equilibria.
