請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8078
標題: | 動態均衡的無政府狀態價格 On the Price of Anarchy of Dynamic Equilibria |
作者: | Jun-Wei Liang 梁峻瑋 |
指導教授: | 陳和麟(Ho-Lin Chen) |
關鍵字: | 賽局,演算法,無政府狀態價格,自主行為的代價, game theory,algorithm,price of anarchy, |
出版年 : | 2021 |
學位: | 碩士 |
摘要: | 在這篇論文中,我們研究了一個隨時間變化的網路流(network flow)模型,稱之為「流體排隊模型」。考慮到一個有向圖被注入連續的流量,致使水分子傳播到每一條邊上。對於每一條邊而言,如果流入的流率超過給定的容量,那麼超出的粒子將會形成等待的隊伍,而其他的粒子在給定的時間長度內通過這一條邊。更精確地,我們研究了在賽局觀點上的流體排隊模型,稱之為動態平衡模型,這被用來描述一些問題。例子包含了網際網路、自駕車中控系統、以及中央處理器挑選任務的過程。
我們在研究中發現了具備連續函數流量的網路的PoA上限。我們證明了平行網路和兩層兩條邊平行網路的PoA上限為$2$,串並聯網路有一個PoA上限為「網路的直徑」,所有網路在假設成立下有一個PoA上限為$2|V|-1$。這是第一篇論文研究具備連續函數流量的網路在流體排隊模型上的PoA。我們把平行網路和串並聯網路的PoA上限從無限大分別壓低到$2$和「網路的半徑」。這兩個被證明出來的上限和具備常數函數流量的網路在流體排隊模型上的情況截然不同。另一方面,類似於在早先抽稅方案上的研究,我們設計了一個簡單的抽稅方案來改善系統的無效率程度。這會許對於具備連續函數流量的網路會有極大的幫助。 In this thesis, we study a Time-Variant-Model, called the ``fluid queuing model''. Consider a directed graph injected with a continuous inflow such that water propagates to each edge. For each edge, If the inflow rate exceeds the given capacity, the exceeding particles form a waiting queue, and the other particles pass through this edge under the given delay time. We study the game theory aspect of the fluid queuing model, called the dynamic equilibrium model, which was applied to describe several problems. Examples include the Internet, the self-driving car central control system, and the procedure of CPU-core. We find upper bounds of the PoA of networks with dynamic inflow. We prove the PoA of $2$ of parallel-link networks and $(2+2)$-parallel-link networks, the PoA of ``network's diameter(called $D(C)$)'' of series-parallel networks, the PoA of $2|V|-1$ of general networks with assumption. This thesis is the first study on the PoA for networks with dynamic inflow in the fluid queuing model. That is, we reduce the upper bound of PoA of parallel-link networks or series-parallel networks from infinite to $2$ and $D(C)$ respectively. The bounds we proved are different from networks with constant inflow in the fluid queuing model. On the other hand, similar to the work of tax scheme, we design a simple tax scheme to improve the inefficiency of the system. This may help a lot on networks with dynamic inflow. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8078 |
DOI: | 10.6342/NTU202100753 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-2202202113573000.pdf | 1.46 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。