The Thesis presents an optimization problem of flow in decentralized networks like data transportation, traffic, population, work flow, etc., where their latency-cost functions are congestion-dependent. In the presence of congestion dependency, the shortest path is not trivially determined, but evolves in current flow, which is more realistic feature. Then we consider this system evolves as to optimize either the total cost or elemental costs individually. Accordingly, the flow pattern can be either intentionally regulated by a global optimization or emerged by individual optimization depending on type of the systems. The latter is known for settling at Nash equilibrium in game theory context. By definition,individual optimization mostly results in worse than a global optimum. This gap has been coined "the Price of Anarchy", indicating the worst inefficiency of selfishness. Nevertheless, this price can get lowered, according to Braess's paradox, by removals of edges in a given system. Consequently, the Thesis investigates tendencies of the price of anarchy in a real system, a simplified Boston road network, and our work promises a potential implication of new methods to optimize flow in decentralized system, which is closer to reality in diverse systems.
최적화 문제는 가깝게는 우리의 생활에서 항상 경험하는 친근한 문제이며, 한 발짝 더 나아가서는 공학의 근간이 되는 중요한 주제이다. 이는 물리학에도 역시 중요시 되고 있으며, 많은 물리학적 관심 문제들이 최적화에 근간을 두고 있거나 동일한 문제로 변환될 수 있다. 이러한 유사점들은 많은 물리학자들을 매혹시켜왔다. 특히, 통계물리의 관점에서 살펴보는 최적화 문제로의 접근은 본 연구가 최종적으로 풀고자 하는 과제이다.
본 연구에서 특별히 관심을 가지고 있는 시스템인, 분산흐름망에서의 최적화문제는 그 복잡함으로 인하여 그리 간단하지 않고 흥미로운 현상들을 보인다. 통계물리 또는 공학에서의 시스템 전체적인 물리량을 최소화하려는 소극적인 자들의 운동이라고 한다면, 우리가 살펴보려는 분산된 시스템에서는 각각의 요소들이 적극적으로 자신의 물리량을 최적화 시키도록 움직인다. 우리는 이러한 시스템에서 나타나는 기이한 현상을 살펴보고자 하는 것이다. 이러한 시스템들은 우리에게 밀접한 집단이 - 흔히 우리가 경험하는, 예를 들면 사회집단 - 포함되므로, 이 시스템에서의 최적화 문제를 통찰해서 얻은 결과는 실생활에서 아주 유용할 것으로 예상된다.
본 연구에서 고찰한 시스템은 분산된 시스템이 네트워크로 이루어져 있을 때, 흐름에 관한 것이다. 이 흐름은 각각의 요소들의 운동에 사용된 에너지 양을 최소화하여 나타난 집단적 결과이다. 이때 요소들은 전체적인 시스템이 가지고 있는 에너지를 생각하지 않는다. 이런 연유에서 이 시스템을 이기적인 시스템이라 부르기도 한다. 우리가 접할 수 있는 예들로는 데이터전송망, 교통망, 집단의 흐름망, 일처리흐름망 등을 들 수 있다. 정리하면, 네트워크에서의 흐름의 패턴은 전체 시스템을 최적화하는 방향으로 조절되거나 그 시스템을 이루는 각각의 요소들의 물리량을 최적화하는 방향으로 창발될 수가 있는데, 후자의 경우가 우리가 관심을 갖는 시스템인, 분산흐름 네트워크인 셈이다. 기존의 연구가 전체 시스템을 통제할 수 있음을 가정한 최적화방법에 기반을 두는 데에 반하여, 본 논제에서 관심을 가지는 시스템인 분산된 흐름망은 그 시스템을 이루는 각각의 요소들을 최적화 이루었을 때의 나타나는 창발된 흐름 패턴에 대한 결과에 중점을 두고 있다. 이런 복잡한 시스템들은 게임이론에서 말하는 내쉬균형으로 간다고 알려져 있는데, 이때 시스템이 갖게되는 값은 앞에서 말한 전체 시스템을 최적화 시킨 결과보다는 같거나 높다. 즉, 전체 시스템이 갖을 수 있는 최대효용보다 낮은 효용을 갖는데, 이 차이를 보여주는 측정양을 "무정부의 가치(Price of Anarchy)"라고 한다. 이는 게임이론에서의 "협동정도" (Coordination ratio) 와 통하는 개념이다.
이러한 기본적인 도구들을 바탕으로 본 연구는 도로 교통망에서의 전산시늉내기로의 결과를 보여주고, 분석하기 위해 노력하고 있다. 흥미로운 결과로는, 이러한 분산적 시스템에서의 최적화는 직관적인 예상과는 전혀 다른 결과를 얻을 수 있다라는 것이다. 즉 링크를 하나 만들어 길을 많이 만들었지만 교통체증은 오히려 심화 될 수 도 있다라는 것이다. 이는 분산망에서의 기존의 방법이 오히려 효용성을 악화시키는 결과를 낳을 수 있음을 의미한다. 이로서 본 연구는 분산망인 시스템을 최적화 시키는 방법에 대한 방향을 제시한다.
