競爭選址的推廣模型

Abstract

選址(facility location) 是長期以來被研究的問題，探討如何找到最佳的設施(facility) 位置以滿足各種目標，例如最大化覆蓋面積、最大化市占率、最小化運輸成本…。在此篇論文中，我們關注於服務提供者們彼此的競爭，以設施位置競逐消費者的需求。競爭選址問題常用賽局建模，服務提供者們為玩家，並以設施位置作為他們的策略。 根據顧客行為，可以歸為三類:Voronoi 模型、覆蓋(cover-based) 模型、Huff-based 模型。我們主要的結果是建立廣義競爭選址(Generalized Competitve Facility Location) 以涵蓋以上三種模型。此外我們證明了 GCFL 的自主行為代價 2，也就是說，即使是最糟的情況，在玩家 (服務提供者) 們自私行為下所得到的總體收入，至少會是玩家們合作時的一半。

Facility location is a well-studied problem that concerns locations of facilities to optimize cerntain objective function such as maximizing covering area, maximizing market share, minimizing the transportation costs to serve the customers. We focus on competitive version of facility location problems, where sevice-providers selecting their facility locations in order to compete for customers’ demand. These problems are often modeled as games in previous researches, where sevice-providers are the players with facility locations being their stratefies. Most of the competitive facility location games can be categorized into the Voronoi model, the cover-based model, and the Huffbased model. The behaviors of customers under each model are different. Our main result is to build a general model - Generalized Competitve Facility Location (GCFL) to cover all three types of prior models so that research findings on GCFL can be applied to them naturally. We also prove that the efficiency degradation incurred by self-interest behaviors of players, the Price of Anarchy (PoA) of GCFL is upper bounded by 2. In other words, in the worst case scenario, the sum of payoffs of self-interested players is at least one-half of optimal payoffs of cooperative players.