動態均衡的無政府狀態價格

Abstract

在這篇論文中，我們研究了一個隨時間變化的網路流（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.