We consider competitive facility location as a two-stage multi-agent system with two types of clients. For a given host graph with weighted clients on the vertices, first facility agents strategically select vertices for opening their facilities. Then, the clients strategically select which of the opened facilities in their neighborhood to patronize. Facilities want to attract as much client weight as possible, clients want to minimize congestion on the chosen facility. All recently studied versions of this model assume that clients can split their weight strategically. We consider clients with unsplittable weights, but allow mixed strategies. So clients may randomize over which facility to patronize. Besides modeling a natural client behavior, this subtle change yields drastic changes, e.g., for a given facility placement, qualitatively different client equilibria are possible. As our main result, we show that pure subgame perfect equilibria always exist if all client weights are identical. For this, we use a novel potential function argument, employing a hierarchical classification of the clients and sophisticated rounding in each step. In contrast, for non-identical clients, we show that deciding the existence of even approximately stable states is computationally intractable. On the positive side, we give a tight bound of 2 on the price of anarchy which implies high social welfare of equilibria, if they exist.

我们考虑竞争性设施位置问题作为一种具有两种类型客户的两阶段多智能体系统。我们以图中加权客户的主机图为基础，首先设施代理机构战略性地选择开设设施的顶点。然后，客户战略性地选择在其邻域中要光顾的已开设设施之一。我们的主要结果是，如果所有客户的权重相同，纯子博弈均衡总是存在。对于非相同的客户，我们证明即使近似稳定状态的存在也是计算上难以处理的。在积极的一面，我们给出了一个2的上界，这意味着即使它们存在，均衡的社会福利也很高。

两阶段设施选址中的平衡解与原子客户