請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/67765
標題: | 競爭選址的推廣模型 A Generalized Model for Competitve Facility Location Games |
作者: | Chung-Hui Chen 陳重輝 |
指導教授: | 陳和麟 |
關鍵字: | 競爭選址,廣義競爭選址模型,賽局理論,納許均衡,自主行為代價, Competitive Facility Location,Game Theory,Generalized Competitive Facility Location,Nash equilibrium,Price of Anarchy, |
出版年 : | 2017 |
學位: | 碩士 |
摘要: | 選址(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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/67765 |
DOI: | 10.6342/NTU201701960 |
全文授權: | 有償授權 |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-106-1.pdf 目前未授權公開取用 | 713.41 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。