혼잡 게임

혼잡 게임(CG)은 게임 이론에서 게임의 한 종류입니다.그들은 도로, 통신망, 과점 시장 및 자연 서식지에서 흔히 발생하는 상황을 나타냅니다.일련의 리소스(예: 도로 또는 통신 링크)가 있습니다. 리소스가 필요한 여러 플레이어(예: 드라이버 또는 네트워크 사용자)가 있습니다. 각 플레이어는 이러한 리소스의 하위 집합(예: 네트워크의 경로)을 선택합니다. 각 리소스의 지연은 이 리소스를 포함하는 하위 집합을 선택하는 플레이어의 수에 따라 결정됩니다.각 선수의 비용은 그가 선택한 모든 자원 중 지연의 합계입니다.당연히, 각 선수들은 자신의 지연을 최소화하기를 원하지만, 각 선수들의 선택은 다른 선수들에게 부정적인 외부성을 강요하고, 이것은 비효율적인 결과로 이어질 수 있습니다.

혼잡 게임의 연구는 1973년 ^[1]미국 경제학자 로버트 W. 로젠탈에 의해 시작되었습니다.그는 모든 혼잡 게임이 순수 전략(일명 순수 내쉬 균형, PNE)에서 내쉬 균형을 가지고 있다는 것을 증명했습니다.증명하는 동안, 그는 사실 모든 혼잡 게임이 정확한 잠재적 게임이라는 것을 증명했습니다.나중에, Monderer와 Shapley는^[2] 정확한 잠재적 기능을 가진 모든 게임은 일부 혼잡 게임과 동등하다는 반대 결과를 증명했습니다.이후의 연구는 다음과 같은 질문에 초점을 맞췄습니다.

• 평형의 존재와 잠재적인 함수의 존재가 혼잡 게임의 더 일반적인 모델로 확장됩니까?
• 융합 게임의 양적 비효율은 무엇입니까?
• 평형을 찾을 때의 계산 복잡도는 무엇입니까?

예

두 플레이어가 O $지점({displaystyle$O})에서$$ 시작하여$$T $지점{\displaystyle }$({$displaystyle$T$\})$에 도달해야 하는 트래픽 네트워크를 생각해 보십시오. 노드 O$({displaystyle$O})가 두 경로를 통해 $노드{\displaystyle }$T({$displaystyle$T})에$$ 연결되어 있다고 가정합니다.오른쪽 그림과 같이 O(디스플레이 스타일 A) - A(디스플레이 스타일 A) - T(디스플레이 스타일 T) 및 O(디스플레이 스타일 A) - B(디스플레이 스타일 B) - T(디스플레이 스타일 A)가 B(디스플레이 스타일 B)보다 조금 더 가깝습니다(즉, A(디스플레이 스타일 A)는 각 플레이어에 의해 선택될 가능성이 높습니다.

두 연결 지점에서 T${displaystyle$ T$}$까지의 도로는 쉽게 정체됩니다. 즉, 한 지점을 통과하는 플레이어가 많을수록 각 플레이어의 지연이 커지므로 두 플레이어가 동일한 연결 지점을 통과하면 추가 지연이 발생합니다.공식적으로$,$ A$({displaystyle$A$})$ T({$displaystyle$ T$})$와 B$({displaystyle$B}({$displaystyle$ B}) $T$$($$각각{\displaystyle }$)에서 x({$displaystyle$x}) 플레이어가 이동할 때 $지연{\displaystyle }$ 시간은 $({$ x$^{2$입니다.

이 게임에서 좋은 결과는 두 선수가 서로 다른 연결 지점을 "조정"하고 통과하는 것입니다.그러한 결과를 달성할 수 있습니까?

다음 매트릭스는 선수들의 선택에 따른 지연 비용을 나타냅니다.

비용 매트릭스

p2 p1	귀리	OBT
귀리	(5,5)	(2,3)
OBT	(3,2)	(6,6)

이 게임의 순수 내쉬 균형은 (OAT, OBT)과 (OBT, OAT)입니다. 플레이어 중 한 명이 일방적으로 변경하면 플레이어의 비용이 증가합니다(표의 값은 비용이므로 플레이어는 더 작은 것을 선호합니다).이 예에서 내쉬 균형은 효율적입니다. 플레이어는 다른 차선을 선택하고 비용의 합계는 최소입니다.

반대로$,$ $xdisplaystyle$x 플레이어가 이동할$$ 때 $A{\displaystyle }$$({displaystyle$ $A$${\displaystyle }$$})$ $T{\displaystyle }$$({displaystyle$ T$}$ 및$$ B$({displaystyle$ B$})$ T$({displaystyle$ T$})$의 $지연{\displaystyle }$ $시간$이 0${\displaystyle \mathrm{.}8}$ x$({displaystyle$ 0$.8x$라고 가정하면 비용 행렬은 다음과 같습니다.

비용 매트릭스

p2 p1	귀리	OBT
귀리	(2.6,2.6)	(1.8,2.8)
OBT	(2.8,1.8)	(3.6,3.6)

이제 순수한 내쉬 균형은 (OAT, OAT)입니다. OBT로 전환하는 모든 플레이어는 비용을 2.6에서 2.8로 증가시킵니다.균형은 여전히 존재하지만 효율적이지 않습니다. (OAT, OBT)와 (OBT, OAT)의 비용 합계는 4.6인 반면, 비용 합계는 5.2입니다.

기본결과

표기법

CG의 기본 정의에는 다음과 같은 구성 요소가 있습니다.

• 정체 가능한 요소(리소스 또는 요인이라고도 함)의 기본$$집합 E${displaystyle$E$$}위의 예에서 E${displaystyle$ E$}$는 도로 집합$($${$$displaystyle$$$O$\},$ $A{\displaystyle }$${$$displaystyle$A$\}$$$$T$${\displaystyle }${$Displaystyle$ T}, $O$${displaystyle$ O$}$ B$($ B) 및 B{$displaystyle$ T$}$입니다.
• $플레이어들$의 집합입니다$.$위의 $예$에서 n $=$ ${displaystyle$ n=$2$
• 각 플레이어에 대한 유한한 $전략{\displaystyle {}_{}}$ 세트 $({$$}).$ 여기서 각 $전략{\displaystyle }$ ${\displaystyle {}_{}}$∈ ${\displaystyle {Si}_{}}$({$displaystyle$P\$in S_{$i$$})는 E$({displaystyle$ E$\}$의 하위 집합입니다.
  • 위의 예에서 두 플레이어는 동일한 전략 집합을 $갖습니다{\displaystyle {}_{}}$. ${\displaystyle {S1\mathrm{}}_{}{}_{}}$ ${\displaystyle {S2\mathrm{}}_{}}$ $=${${\displaystyle \mathrm{OA},}$ ${\displaystyle \mathrm{AT}\},}$ {${\displaystyle \mathrm{OB},}$ ${\displaystyle \mathrm{BT}\}}$ $=$ {\$displaystyle S_{1$}= $S_{2$}\ \{\$OA,$$AT\},\{OB,BT$ 모든 플레이어가 동일한 전략 집합을 갖는 CG를 대칭 CG라고 합니다.일반적으로 각 플레이어의 소스 및/또는 대상이 다른 경우와 같이 여러 플레이어의 세트가 다를 수 있습니다.이러한 CG를 비대칭 CG라고 합니다.
  • 일반적으로 전략은 E${displaystyle$ E$\}$의 하위 집합이 될 수 있습니다. 위의 예와 같이 전략이 주어진 그래프의 경로로만 사용될 수 있는 CG를 네트워크 CG라고 합니다.전략이 단일 리소스만 될 수 있는 CG를 싱글톤 CG라고 합니다.
• 각 $요소{\displaystyle }$ e${E$\$displaystyle$ $e\$in$$ E$\}{\displaystyle }$ 및 ${\displaystyle {}_{}}$ ${\displaystyle {벡터\mathrm{}}_{}{P1\mathrm{}}_{}{}_{},}$ ${\displaystyle {}_{}}$ ) ${\displaystyle (P_{1}, P_{2},\ldots, P_{$n$\}\}$에 대해 ${\displaystyle {부하}_{}}$는${\displaystyle \mathrm{}}$x$=$# {$i$ : e$e}=\e{$로 정의됩니다.
• 각 $요소{\displaystyle }$ ${\displaystyle e}${$displaystyle$ e$\in$ E$}$에 대해 지연 $함수{\displaystyle {}_{}}$ ${\displaystyle {de}_{}}$ ${\displaystyle N\mathbb{}}$ ${\displaystyle ⟶}$ ${\displaystyle R\mathbb{}}$ ${\$ \$longrightarrow \mathbb {R}($지연 함수 또는 비용 함수라고도 함)가 있습니다.전략의 벡터가 주어지면 $지연{\displaystyle }$ 1${displaystyle$ e$}$는 $){displaystyle d_{e$$x_{e})$입니다. $각{\displaystyle {}_{}}$ $({$e$$}})는 양의 단조 증가하는 것으로 가정됩니다.
• $전략{\displaystyle {}_{}}$ $($$P_{$i$\})$가 주어지면 $플레이어$ i$({$$displaystyle$i$})$는 지연 ${\displaystyle \sum _{}}$ $xe)$를$$경험합니다$$. 각 플레이어는 $지연$을 최소화하려고 합니다.
• 내쉬 균형(Nash equilibrium)은 각 플레이어 i에 대해 Pi({displaystyle P_{i})를 다른 전략 Q({displaystyle Q_{i})로 교체해도 idisplaystyle i가 경험하는 지연이 줄어들지 않는 전략 벡터(P_{1}, P_{2}, \ldots, P_{n}.

내쉬 균형의 존재

모든 CG는 순수한 전략에서 내쉬 균형을 가지고 있습니다.이는 각 ^[1]결과에 값을 할당하는 잠재적 함수를 구성하여 나타낼 수 있습니다.게다가, 이 구성은 또한 반복되는 최상의 반응이 내쉬 균형을 찾는다는 것을 보여줄 것입니다.$\phi {\displaystyle \mathrm{}}$${\displaystyle \underset{}{}}$=$$∑ ${\displaystyle \underset{}{e}}$ ∈ ${\displaystyle \underset{}{\overset{}{e}}}$ ∑ k = 1 ${\displaystyle \underset{}{\overset{}{{}_{}}}}$ ${\displaystyle {ed}_{}}$ $)$ \$displaystyle \textstyle \Phi$ = \$sum$ _${e\$$in$ E$}\$$sum$_{k$=1}^{x_{e}d_{e$$k$$).$ 이 함수는 사회 복지 ∑${\displaystyle \underset{}{}{}_{}{}_{}}$(${\displaystyle {}_{}}$)$discretelediscontextstystyle \textstyle$\{$e$의 $적분이 아닙니다$.혼잡 게임에서 잠재적 기능의 중요한 특성은 한 플레이어가 전략을 전환할 경우 지연의 변화가 잠재적 기능의 변화와 같다는 것입니다.

플레이어 i({displaystyle i})가 Pi({i})에서 Qi({i})로 전환되는 경우를 생각해 보십시오. 두 가지 전략 모두에 있는 요소는 영향을 받지 않으며 플레이어가 떠나는 요소(예: ∈ Pi - Qi)는 잠재력을 d(ex)만큼 감소시킵니다플레이어가 조인하는 요소(${\displaystyle {}_{}}$:${\displaystyle }$∈ ${\displaystyle {Qi}_{}}$- ${\displaystyle {Pi}_{}}$ ${\$ e$\in$ Q_${i}-P_{i$는 잠재력을 ${\displaystyle {de}_{}\mathrm{x}{}_{}}$+ 1$)$ 증가시킵니다(x_{{$e}(x_{e}+1$이러한 전위 변화는 정확히 $플레이어{\displaystyle }$i({$displaystyle$i$\})$의 지연 변화이므로,$\Delta {\displaystyle \mathrm{}}$({$displaystyle \Phi})$는 실제로 잠재적 함수입니다.

이제 최소$({displaystyle$ \Phi$$$})$가 순수한 내시 평형이라는 것을 관찰합니다.한 플레이어를 제외한 모든 플레이어를 고정하면 해당 플레이어의 전략 개선은 ${displaystyle \Phi$ 감소에 해당하며, 이는 최소한 발생할 수 없습니다.이제 제한된 수의 구성이 있고 각 $({$가 단조롭기 때문에 평형이 존재합니다.

잠재적 함수의 존재는 유한 개선 속성(FIP)이라는 추가적인 의미를 갖습니다.만약 우리가 어떤 전략-벡터로 시작하고, 임의로 선수를 선택하고, 그 선수에게 더 나은 전략으로 그의 전략을 바꾸게 하고, 반복한다면, 개선의 순서는 유한해야 합니다(즉, 순서는 순환하지 않습니다).이는 이러한 개선이 가능성을 엄격하게 증가시키기 때문입니다.

확장 기능

아래는 기본 CG 모델에 대한 다양한 확장과 변형을 제시합니다.

비원자 정체 게임

n ${\displaystyle \to }$ $∞$ {\$displaystyle$ n$\rightarrow \infty$와 $같이{\displaystyle }$ n개의 플레이어가 있는 표준 CG의 한계입니다. 플레이어는 연속적으로 존재하며 플레이어는 "매우 작은" 것으로 간주되며 각 플레이어는 혼잡에 무시할 수 있는 영향을 미칩니다.Milchtaich,^[3] Friedman^[4] 및 Blonsky는 ^[5][6]원자가 아닌 CG를 연구했습니다.

• 우리는 E${displaystyle$ E$}$를 유한 집합의 혼잡 요소로 $유지$합니다.
• 개별 사례에서처럼$$n개의 $플레이어$를 $인식$하는 대신 각 $유형{\displaystyle }$ i${displaystyle$ $i$$}$가 해당 유형의 $트래픽{\displaystyle {}_{}}$ 속도를 나타내는 숫자 $({$와 연결된 {$displaystyle$ n$}$ 유형의 플레이어가 $.$
• 유형 i의 각 에이전트는 전략 $세트{\displaystyle {}_{}}$ $({$에서 전략을 선택합니다.
• 이전과 마찬가지로, $지연{\displaystyle {}_{}}$ 함수 ${$e$$}는 단조롭고 긍정적이지만, 이제 우리는 그것들도 연속적이라는 가정을 추가합니다.
• 우리는 유형의 플레이어가 전략 세트에 걸쳐 부분적으로 분배할 수 있도록 허용합니다.즉, 모든 $전략{\displaystyle }$ P$$$\in {\displaystyle \underset{}{}}$ ${\displaystyle {Si}_{}}$({\$displaystyle$ P$\in$ S_${i$에 ${\displaystyle {대해}_{}}$ P$({$가 $전략{\displaystyle }$P({$displaystyle$P$\})$를 사용하여 $유형{\displaystyle }$i({$displaystyle$$f_$$$${P})$의 플레이어 분율을 나타내도록 $합니다{\displaystyle {}_{}}$. 정의에 따라 P ${\displaystyle \sum _{}}$ ${\displaystyle \underset{}{{}_{}}}$ ${\displaystyle {if}_{}}$ P$=$ ${\displaystyle r_{}}${\$displaystyle$ \$textstyle \textsum$ _{i_{P$\in S_{P_i$
• 각 $요소{\displaystyle }$ ${\displaystyle e}$\$displaystyle$ e$\in$ E$\}$에 대해 부하는 e를 사용하는 플레이어의 분수 합계, $즉{\displaystyle {}_{}}$ ${\displaystyle x_{}}$ $=$ ${\displaystyle \sum _{}}$ ${\displaystyle \underset{}{P}}$ ${\displaystyle \ni }$ ${\displaystyle e_{}}$ ${\displaystyle \underset{}{}{}_{}}$P {$displaystyle x_${e}=\$sum _{P\nie}f_{$P$\}$로 정의됩니다.

원자가 아닌 CG에서 평형의 존재

이제 전략은 전략 프로파일 fP({displaystyle f_{P})의 집합입니다. 크기가 n인 전략 집합 Si({displaystyle S_{i})의 경우, 모든 유효한 프로파일 집합은 {\displaystyle [0,r_{i}]^{n}}의 압축 부분 집합입니다. 이제 잠재 함수를 Δ = Δ E x z(z)로 정의합니다 \$textstyle \Phi$=\$sum$ _${e\in$ E$}\int$ _${0}^{x_{e}}d_{e}(z)\,dz$ 이산 적분을 표준 적분으로 바꿉니다$.$

전략의 함수로서 ${displaystyle \Phi}$는 연속적입니다. ${$는 가정에 의해 연속적이고 ${{$는 전략의 연속적인 함수입니다.그런 다음 극단값 정리에 의해 ${displaystyle \Phi}$가 전역 최소값에 도달합니다.

마지막 단계는 최소 ${displaystyle \Phi}$가 실제로 내쉬 평형임을 보여주는 것입니다.$\Delta$를$$최소화하지만 내시 평형이 아닌 $({$$displaystyle f_{$P$$$})$ $집합$이 있다고 모순을 가정합니다.그런 다음 일부 $유형{\displaystyle }$i({$displaystyle$i$\})$의 경우 현재 $선택$한 P$({displaystyle$ P$\})$보다 $({$Q$\$$in$ S_${$$i})$가 $약간{\displaystyle }$ 향상됩니다. , ( < $)$ \$textstyle \sum_{e}(x})$ \textstyledisplaystyle \syle\$sum(e{e_${e_{e_$e})$입니다.이제 아이디어는 소량의 δ < f P {displaystyle \delta <f_{를 취하는 것입니다P} 전략을 사용하는 플레이어 중에서 P} 전략을 사용하는 플레이어를 전략 Q({displaystyle Q})로 이동합니다. 이제 임의의 x ∈ Q({displaystyle x_{e}\in Q)에 대해 로드를 δ만큼 늘렸으므로 φ \displaystyle \Phi(\displaystyle \delta)의 기간은 현재 ∫0 x + δ (z )입니다 ${${e$}+\$$delta }$d_${$e}($z$$)dz$ 적분을 구분할 때, 이 변경 사항은 약 $\delta {\displaystyle {}^{}}$${\displaystyle {}_{}}$$⋅$ ${\displaystyle d_{}}$($)$이며 ${\displaystyle {오류}^{}}$는 2${\$ $d_{$$2$입니다$.$P${displaystyle$ P$\}$의 가장자리를 볼 때 변화에 대한 동등한 분석이 유지됩니다.

따라서 퍼텐셜의 변화는 대략 $\delta {\displaystyle }$ ($$ ∈ ${\displaystyle \underset{}{Q}{}_{}{de}_{}}$ ( ${\displaystyle {}_{}{e}_{}}$) - ${\displaystyle \sum _{}{}_{}}$∈ ${\displaystyle {Pde}_{}}$ ( ${\displaystyle x_{}}$e )$$\$delta$ (\$sum$ _${e\in$Q}$d_{e}(x_{e$로 0보다 $작습니다.$이는 모순입니다. 당시 ${displaystyle \Phi}$가 최소화되지 않았기 때문입니다.따라서 최소 ${displaystyle \Phi}$는 내쉬 평형이어야 합니다.

분할 가능한 혼잡 게임

원자 CG에서처럼 분할 가능한 CG에는 많은 플레이어가 있으며, 각 플레이어는 전송해야 할 특정 부하를 가집니다.원자가 아닌 CG에서처럼, 각 플레이어는 자신의 부하를 다른 경로를 통해 분할할 수 있습니다. 마치 운송 회사가 대량 운송을 위한 경로 집합을 선택하는 것처럼 말입니다.원자가 아닌 CG와 대조적으로, 각 플레이어는 혼잡에 무시할 수 없는 영향을 미칩니다.

분할 가능한 CG는 1993년 ^[7][8]통신 네트워크의 맥락에서 Ariel Orda, Raphael Rom 및 Nachum Shimkin에 의해 처음 분석되었습니다.그들은 두 개의 노드와 여러 개의 병렬 링크가 있는 간단한 네트워크의 경우 내쉬 평형이 합리적인 볼록 조건에서 독특하고 몇 가지 흥미로운 단조성 특성을 가지고 있음을 보여줍니다.일반적인 네트워크 토폴로지의 경우 내쉬 균형의 고유성을 보장하기 위해 더 복잡한 조건이 필요합니다.

가중 혼잡 게임

가중치가 부여된 CG에서, 다른 플레이어들은 혼잡에 다른 영향을 미칠 수 있습니다.예를 들어, 도로망에서 트럭은 오토바이보다 훨씬 더 혼잡을 가중시킵니다.일반적으로 플레이어의 무게는 자원(자원별 가중치)에 따라 달라질 수 있다: 모든 플레이어 i와 자원 i에는 가중치 wi, edisplaystyle w_{i,e}가 있고, 자원 e에 대한 부하는 x = ∑ i : e Piwi, e{displaystyle x_{e}=\sum _{i:\in P_{i,e},e}이다플레이어(리소스에 의존하지 않는 가중치), 즉 각 플레이어 i에는 $가중치$가 $,$ ${\displaystyle {xe}_{}}$ $=$ : ${\displaystyle \underset{}{e}}$ ∈ ${\displaystyle \underset{}{{}_{}}{}_{}}$ ${\displaystyle {wi}_{}}$wi wi {{$displaystyle x_{e$}=\$sum$ _${i$$:$$e\in$ P_${i}w_{i$가 있습니다.

리소스 독립 가중치가 있는 가중 싱글톤 CG

Milchtaich는^[9] 각 전략이 단일 리소스("싱글톤 CG")이고 가중치는 리소스 독립적이며 모든 플레이어가 동일한 전략 세트를 갖는 가중 CG의 특별한 경우를 고려했습니다.다음 사항이 입증되었습니다.

• 모든 플레이어가 동일한 지연 함수를 가질 경우, 게임은 유한 개선 속성(따라서 PNE)을 가집니다.
• 두 가지 전략만 있는 경우(그리고 다른 지연 함수를 가진 임의의 많은 플레이어), 게임은 유한 개선 속성을 가집니다(따라서 PNE를 가집니다).
• 두 명의 플레이어만 있는 경우(지연 기능이 다를 수 있음), 게임은 유한 최적 응답 특성을 가집니다(따라서 PNE를 가집니다).
• 세 가지 이상의 전략과 세 가지 이상의 지연 기능을 가진 플레이어가 있는 경우 PNE가 존재하지 않을 수 있습니다.

가중 네트워크 CG

Milchtaich는 각 전략이 주어진 무방향 그래프("네트워크 CG")의 경로인 가중 CG의 특별한 경우를 고려했습니다.그는 모든 유한 게임이 감소하지 않는(반드시 마이너스는 아니지만) 비용 ^[10]함수를 가진 가중 네트워크 혼잡 게임으로 표현될 수 있다는 것을 증명했습니다.이것은 이러한 모든 게임이 PNE를 가지고 있는 것은 아니라는 것을 의미합니다.PNE가 없는 가중 CG의 구체적인 예는 Libman과 Orda,^[11][12] Goemans Mirrokni 및 Vetta에 의해 제공됩니다.이는 PNE의 ^[13]존재를 보장하는 조건이 무엇인지에 대한 의문을 제기합니다.

특히, 우리는 기본 네트워크가 G인 모든 가중 네트워크 CG가 해당 속성을 가질 경우 특정 그래프 G가 특정 속성을 보장한다고 말합니다.Milchtaich[14]는 PNE의 존재와 유한 개선 속성을 보장하는 네트워크를 저체중의 플레이어가 약하게 허용되는 전략을 갖는 추가 조건으로 특성화했다(형식적으로, wj {\displaystyle w_{i}<w_{j}는 Si ≥ S {\displaystyle S_{i} \geQ S_{j}를 의미한다).그는 다음을 증명했습니다.

• 그래프 G는 G가 병렬 네트워크(병렬로 연결된 하나 이상의 단일 에지 네트워크로 구성된 그래프) 또는 하나 또는 ^{: Thm.2} 두 개의 단일 에지 네트워크와 직렬로 연결된 병렬 네트워크와 동형일 경우 유한 개선 특성을 보장합니다.
• 그래프 G는 G가 6개의 "허용된 네트워크" 세트에서 하나 이상의 네트워크 시리즈 연결과 동형일 경우 PNE의 존재를 보장합니다. 동등한 조건은 ^{: Thm.3} G에 6개의 "금지된 네트워크" 세트의 네트워크가 포함되지 않는다는 것입니다.

모든 플레이어가 모든 전략("퍼블릭 에지")을 사용할 수 있는 특별한 경우, PNE의 존재를 보장하는 네트워크가 더 많습니다. 이러한 네트워크의 완전한 특성화는 공개 ^[14]문제로 제기됩니다.

Mlichtaich는^[15] 네트워크 토폴로지가 PNE의 효율성에 미치는 영향을 분석합니다.

• 그래프 G는 세 개의 간단한 "금지된 네트워크"가 G에 포함되지 않은 경우 모든 PNE가 파레토 효율적임을 보장합니다.
• 그래프 G는 직렬 병렬 그래프인 경우 Braess의 역설이 발생하지 않음을 보장합니다.

Milchtaich는^[16] 네트워크 토폴로지가 PNE 비용의 고유성에 미치는 영향을 분석합니다.

• 그래프 G는 G가 여러 가지 간단한 종류의 하나 이상의 네트워크 시리즈 연결인 경우 PNE 비용이 고유함을 보장합니다.
• G가 특정 단순 유형의 내장 네트워크를 포함하는 경우 그래프 G는 PNE 비용이 고유하다는 것을 보장하지 않습니다.

Holzman과 Law-Yone은^[17] 또한 모든 원자 CG가 강력한 PNE, 고유한 PNE 또는 파레토 효율적인 PNE를 갖도록 보장하는 네트워크를 특징짓습니다.

Richman과 Shimkin은^[18] 분할 가능한 모든 CG가 고유한 PNE를 갖도록 보장하는 네트워크를 특징짓습니다.

일반 가중 CG

우리는 모든 지연 함수가 C의 요소인 모든 가중 CG가 해당 속성을 가질 경우 함수의 클래스 C가 특정 속성을 보장한다고 말합니다.

• Fotakis, Kontogiannis 및^[19] Spirakis는 선형 함수의 클래스가 정확한 잠재력의 존재를 보장하므로 PNE의 존재를 증명합니다.
• 파나고풀루와 스피라키스는^[20] 지수 함수의 클래스가 가중 잠재력의 존재를 보장하며, 따라서 PNE의 존재를 증명합니다.
• Harks, Klimm 및 Mohring은^[21] 함수 클래스가 아핀 함수만 포함하는 경우에만 정확한 잠재력의 존재를 보장한다는 것을 증명합니다.이 특성화는 2인 게임, 3자원 게임, 싱글톤 게임, 대칭 전략을 사용하는 게임 또는 적분 가중치를 사용하는 게임으로 제한되는 경우에도 유효합니다.또한 함수의 클래스는 (1) 아핀 함수만 포함하거나 (${\displaystyle 2)}$ ea $형식$의 지수 함수만 포함하는 경우에만 가중 잠재력의 존재를 보장합니다. ({$e}(\$\$cdot x_{e}}+b_{e$여기서$\varphi {\displaystyle }$ {\$displaystyle \phi}$는 모든 리소스에 대해 동일합니다.이 특성화는 4인 게임, 4자원 게임, 싱글톤 게임, 대칭 전략을 사용하는 게임 또는 적분 가중치를 사용하는 게임으로 제한된 경우에도 유효합니다.2인용 게임의 경우, 함수의 클래스는 $가중치$가$$된$$의 존재를 보장합니다. $여기$서 f${displaystyle$f$}$는 단조 함수입니다($모든$ 리소스에 대해 동일합니다$).$
• Harks와 Klimm[22]은 PNE의 존재에 대해 유사한 결과를 증명한다. 그들은 함수의 클래스가 (1) 그것이 오직 아핀 함수만을 포함하거나 (2) 그것이 a e exp ( ϕ ⋅ ⁡ x ) + 형태의 지수 함수만 포함하는 경우에만 PNE의 존재를 보장한다는 것을 증명한다,여기서$\varphi {\displaystyle }$ {\$displaystyle \phi}$는 모든 리소스에 대해 동일합니다.이 특성화는 3인 게임으로 제한된 경우에도 유효합니다.2인용 게임의 경우, 함수 클래스는 PNE의 $존재$를 ${\displaystyle {보장}_{}}$합니다${\displaystyle {}_{}}$ 여기서 f${$$displaystyle$f$}$는 모노톤 함수입니다$($ 리소스에 동일$).$

기타 결과

가중 혼잡 ^[23][24][25]게임에 대한 다른 많은 논문들이 있습니다.

플레이어별 비용 함수

기본 CG 모델은 각 자원의 지연 기능이 플레이어에 따라 달라지도록 하여 확장할 수 있습니다.따라서 각 리소스와 플레이어 i에는 지연 함수 ${\displaystyle {di,}_{}}$ ${$e$\}$가 있습니다. $전략{\displaystyle {}_{}}$ ${$가 주어지면 $플레이어{\displaystyle }$ i${displaystyle$ i$}$는 지연${\displaystyle \underset{\sum }{}}$ ${\displaystyle {Pi,}_{}}$e$($ \$textstyle \sum$ _${e\in$ P_${i}}{i,e}(x_e$를 경험합니다.

싱글톤 CG의 플레이어별 비용(크라우딩 게임)

Milchtaich는^[9] 다음과 같은 특별한 경우에 플레이어별 비용으로 CG를 도입하고 연구했습니다.

• 각 플레이어는 단일 리소스를 선택합니다(이러한 게임을 싱글턴 CG라고 함).
• 모든 플레이어는 동일한 전략을 가지고 있습니다.

CG의 이 특별한 경우는 크라우딩 ^[26][27]게임이라고도 불립니다.여러 명이 동시에 갈 장소(예: 방, 숙소, 식당)를 선택하는 설정을 나타내며, 그들의 보수는 장소와 같은 장소를 선택하는 다른 플레이어의 수에 따라 결정됩니다.

혼잡한 게임에서 전략 파이 = {e}({displaystyle P_{i}=\{e\})가 주어지면 플레이어 i({displaystyle i}가 지연 d, e(xe)를 경험합니다. 플레이어가 다른 전략 f({i,e}(x_{e)로 전환하면 지연은 d, f(x + 1)가 됩니다. 따라서 PNE 전략입니다모든$$ 플레이어 i, ${\displaystyle {di,}_{}}$ ${\displaystyle e_{}{xe}_{}}$ ${\displaystyle \le }$ ${\displaystyle {di,}_{}}$ ${\displaystyle f_{}{xf}_{}}$ ${\displaystyle {}_{}}$ $)$의 경우 ifff, f(\$displaystyle d_{i,e}(x_{e})\leq d_{i,f}(x_{f}+1)}.$

일반적으로 플레이어별 지연이 있는 CG는 잠재적인 기능을 허용하지 않을 수 있습니다.예를 들어, 다음과 같은 지연 기능을 가진 세 개의 리소스 x, y, z와 두 개의 플레이어 A 및 B가 있다고 가정합니다.

• ${\displaystyle d_{A,x}(1)<d_{A,y}(0)<d_{A,y}(2)<d_{A,z}(0)<d_{A,z}(2)<d_{A,x}(2)}$
• ${\displaystyle d_{B,y}(1)<d_{B,x}(0)<d_{B,x}(2)<d_{B,z}(0)<d_{B,z}(2)<d_{B,y}(2)}$

다음은 순환 개선 경로입니다$.{\displaystyle }$ (${\displaystyle z,y}$ )${\displaystyle \to }$ (${\displaystyle y,y)}$ ${\displaystyle \to }$ (y,${\displaystyle }$z) ${\displaystyle \to }$ (${\displaystyle x,z)}$ (${\displaystyle x}$, x$\to (y, y)\to (x, x)\to$ ($x, x)\to$ ($z,$ x)\to (z, x)\$to$ (z, x,$x)\$to (z, z, z, $z)$ $\}$ 이것은 유한한 개선이 유지되지 않음을 보여줍니다.따라서 게임은 잠재적인 기능을 가질 수 없습니다(일반화된 순서적인 기능도 아닙니다).그러나:

• 두 가지 리소스만 있으면 유한 개선 속성이 ^{[9]: Thm.1} 유지됩니다.따라서 PNE가 존재합니다.
• 두 명의 플레이어만 있으면 모든 유한 최상의 응답 속성이 유지됩니다.따라서 PNE가 존재합니다.

세 명 이상의 선수가 있을 때는 최상의 대응 경로도 순환적일 수 있습니다.그러나 모든 CG에는 여전히 ^{[9]: Thm.2} PNE가 있습니다.증명은 건설적이며 최대${\displaystyle }$(${\displaystyle n\genfrac{}{}{0ex}{}{}{}}$+ ${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{}}{}}$ )${{$ 2$}$ 단계에서$$ 내쉬 균형을 찾는 알고리듬을 보여줍니다.게다가, 모든 CG는 약하게 비순환적입니다. 초기 전략-벡터의 경우, 이 벡터에서 시작하는 적어도 하나의 최상의 응답 경로의 $길이$는 최대 r${\displaystyle (n\genfrac{}{}{0ex}{}{}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{+}{}}$ $)$ {$displaystyle$r{$n + 1$ \$choose$2$\}\}$이며,^{[9]: Thm.3} 이는 평형에서 끝납니다.

모든 혼잡한 게임은 순차적으로 해결할 ^[26]수 있습니다.즉, 플레이어의 모든 순서에 대해 각 플레이어가 차례로 전략을 선택하는 순차 게임은 플레이어의 행동이 원래 동시 게임에서 PNE인 하위 게임 완벽 균형을 갖습니다.모든 크라우딩 게임에는 적어도 하나의 강력한 ^[28]PNE가 있습니다. 크라우딩 게임의 모든 강력한 PNE는 ^[26]게임의 순차 버전의 하위 게임 완벽 균형으로 달성될 수 있습니다.

일반적으로, 혼잡한 게임은 많은 다양한 PNE를 가질 수 있습니다.예를 들어, n개의 플레이어와 n개의 리소스가 있으며, 리소스의 양의 값보다 혼잡이 보상에 미치는 부정적인 영향이 훨씬 높다고 가정합니다.다른 플레이어가 점유한 리소스로 이동하는 플레이어가 없기 때문에 리소스에 대한 플레이어의 일대일 매칭은 PNE입니다.그러나 혼잡한 게임이 m회 복제되면 m이 무한대로 이동함에 따라 PNE 집합이 단일 지점으로 수렴됩니다.게다가, "대형"(원자가 아닌) 크라우딩 게임에는 일반적으로 고유한 PNE가 있습니다.이 PNE는 흥미로운 그래프 이론적 특성을 가지고 있습니다.G를 한 쪽에는 플레이어가 있고 다른 쪽에는 리소스가 있는 이분 그래프로 하자. 여기서 각 플레이어는 고유한 PNE에서 선택한 모든 리소스에 인접합니다.그러면 G에는 ^[27]주기가 없습니다.

분리 가능한 비용 함수

플레이어별 지연 함수의 특별한 경우는 지연 함수를 플레이어별 요인과 일반 요인으로 구분할 수 있다는 것입니다.두 가지 하위 사례가 있습니다.

• 곱셈으로 분리할 수 있는 $비용{\displaystyle {}_{}}$ 함수: $xe$)$=$ ${\displaystyle \mathrm{ai},}$ e$($ {$displaystyle d_{i,e}=a_{i,$e}\$cdot d(x_{$e$\}\}).$ ${\displaystyle {여기}_{}}$서 $,$ e{$displaystyle a_{i,e}$는 플레이어에 대한 리소스의 기본 비용을 나타내는 상수이며 일반 지연 함수입니다(모든 리소스에 대해 동일).
• 추가적으로 분리할 수 있는 ^[29]비용 ${\displaystyle {함수:}_{}}$ ${\displaystyle {\mathrm{di}}_{}}$ e (${\displaystyle x_{}}$ $=$ ${\displaystyle {\mathrm{ai},}_{}}$e +${\displaystyle d}$ ($x)$ {$displaystyle d_{i,e}= a_{$$i,e}+$$d(x_{$$e$$\}\}).$ $여기$서 ${\displaystyle i_{}}$,$,$는 플레이어에 대한 리소스의 고정 비용을 나타내는 상수이며 일반 지연 함수입니다(모든 리소스에 대해 동일합니다).

순수 전략만 고려할 때 제품의 로그는 합이므로 이 두 개념은 동일합니다.또한 플레이어가 리소스별 가중치를 가질 수 있는 경우 리소스별 지연 기능이 있는 설정을 범용 지연 기능이 있는 설정으로 줄일 수 있습니다.분리 가능한 비용 기능을 가진 게임은 ^[30]로드 밸런싱, M/M/1 ^[31]큐잉, 서식지 ^[32]선택에서 발생합니다.다음은 분리 가능한 ^[33]비용이 있는 가중 싱글톤 CG에 대해 알려져 있습니다.

• 기본 $비용{\displaystyle {}_{}}$ ${\displaystyle {a,}_{}}$ ${$$displaystyle$ $a_{i,e}$가 플레이어 독립적인 경우(ai$=$}=$a_{e$}), CG는 FIP를 가지므로 PNE를 가집니다.기본 비용이 리소스에 의존하지 않는 경우(ai${\displaystyle {,}_{}}$ $e$ ^[30][34]$=$ i{$,$}=$a_{i})$에도 마찬가지입니다.증명은 벡터 값 전위 함수를 기반으로 합니다.게임의 각 상태에서 잠재력은 큰 것에서 작은 것으로 정렬된 모든 플레이어의 비용을 포함하는 크기 n의 벡터입니다.플레이어가 더 적은 비용으로 자원을 이탈할 때마다 비용의 벡터는 렉시 순서대로 작아집니다.
• 가중치가 플레이어 독립적인 경우(동등하게: CG는 가중치가 없고 지연 함수는 리소스에 따라 다름), FIP가 있으므로 ^[35][29]PNE가 있습니다.비용 함수가 추가적으로 분리 가능하다면, 게임은 정확한 잠재적 기능을 가지고 있습니다.비용 함수가 부하에 따라 단조롭게 증가하지 않더라도 결과는 유지됩니다.비용 함수가 추가적으로 분리 가능하지 않으면 FIP가 유지되지 않을 수 있고 잠재적인 함수가 없을 수 있지만 PNE는 여전히 ^{[9]: Thm.2} 존재합니다.
• 가중치가 리소스에 의존하지 않는 경우 PNE는 다음과 같은 경우에 존재합니다.
  • 최대 세 명의 플레이어가 있을 때 PNE가 ^{[36]: Cor.3} 존재하지만 최상의 응답 개선 속성은 유지되지 않을 수 있습니다.대조적으로 PNE가 존재하지 ^{[33]: Thm.3} 않는 8명의 플레이어로 분리 가능한 비용과 자원 독립 가중치를 가진 CG가 있습니다.
  • 비용 함수가 선형 가변 비용 함수와 추가적으로 분리 가능할 때 CG는 가중 잠재력을 가지므로 FIP를 가지므로 ^{[36]: Thm.6} PNE를 갖습니다.
  • 비용 함수가 로그 가변 비용 함수와 추가적으로 분리 가능하고 최대 3명의 플레이어가 있을 때 CG는 최고의 반응 개선 특성을 가지고 있기 때문에 PNE를 가집니다.그러나 유한 개선 ^[37]속성을 가지고 있지 않을 수 있습니다.3명 이상의 선수들에게 PNE의 존재는 열려 있습니다.

분리 가능한 플레이어별 선호도를 가진 모든 가중 싱글톤 CG는 플레이어 독립적 ^[33][2]선호도를 가진 가중 네트워크 CG와 동형입니다.

플레이어별 비용이 포함된 네트워크 CG

Milchtaich는 각 전략이 주어진 그래프("네트워크 CG")의 경로인 플레이어별 비용이 있는 CG의 특수한 경우를 고려했습니다.그는 모든 유한 게임이 플레이어별 비용으로 (무가중) 네트워크 혼잡 게임으로 표현될 수 있으며, 비용 ^[10]함수는 감소하지 않지만 반드시 마이너스는 아니라는 것을 증명했습니다.이러한 CG에서 PNE의 존재를 보장하는 네트워크의 완전한 특성화는 공개 ^[14]문제로 제기됩니다.

순수 내쉬 균형 계산

가중치가 없는 CG의 평형 계산

PNE의 존재 증명은 건설적입니다. 항상 PNE를 찾는 유한 알고리즘(개선 경로)을 보여줍니다.이것은 이 PNE를 찾기 위해 몇 단계가 필요한지에 대한 의문을 제기합니다. Fabrikant, Papadimitriu 및 Talwar는^[38] 다음을 증명했습니다.

• 모든 전략이 네트워크의 경로("네트워크 CG")이고 모든 플레이어가 동일한 전략 집합("대칭 CG")을 가지고 있다면, PNE는 최소 비용 흐름으로 감소하여 잠재력을 최대화함으로써 다항 시간 내에 계산될 수 있습니다.이 알고리듬은 원자가 아닌 CG에 적용될 수 있습니다. 특정 평활도 가정 하에서 이러한 게임의 내쉬 평형은 강력한 다항식 시간에 근사할 수 있습니다.
• 전략이 일반적인 하위 집합일 수 있거나 플레이어가 서로 다른 전략 집합("비대칭 CG")을 가질 수 있는 경우 PNE 계산은 PLS-완전입니다.이는 기하급수적으로 긴 개선 경로를 가진 예가 있음을 의미합니다.또한 지정된 상태에서 도달할 수 있는 내쉬 평형을 찾는 것이 PSPACE-완전하다는 것을 의미합니다.
• 클래스 PLS의 모든 문제는 퍼텐셜 함수 인수에 의해 순수 평형이 존재해야 하는 게임으로 제시될 수 있습니다.

Even-Dar, Kesselman 및 Mansour는^[30] 로드 밸런싱 설정에서 평형으로 수렴하는 데 필요한 단계 수를 분석합니다.

Caragiannis, Fanelli, Gravin 및 스코팔릭은^[39] 상수 인자 근사 PNE를 계산하는 알고리듬을 제시합니다.특히:

• 선형 지연 함수의 경우 근사 비율은 2+ε이고 런타임은 플레이어 수, 리소스 수 및 1/ε에서 다항식입니다.
• 지연 함수가 차수 d 다항식인 경우 근사 비율은 d입니다^O(d).

그들의 알고리즘은 대략적인 평형으로 이어지는 최상의 반응 움직임의 짧은 시퀀스를 식별합니다.또한 보다 일반적인 CG의 경우 PNE의 다항식 근사를 달성하는 것이 PLS-완전이라는 것을 보여줍니다.

가중 네트워크 CG의 평형 계산

Fotakis, Kontogiannis 및^[19] Spirakis는 선형 지연 함수가 있는 가중 네트워크 CG에서 유사 다항식 시간(플레이어 수 n 및 플레이어 가중치 W의 합에서 다항식)에서 PNE를 찾는 알고리듬을 제시합니다.그들의 알고리즘은 탐욕스러운 최상의 반응 알고리즘입니다: 플레이어는 자신의 몸무게가 감소하는 순서로 게임에 들어가고, 기존 플레이어의 전략에 가장 잘 반응하는 것을 선택합니다.

Panagopoulou와^[20] Spirakis는 Fotakis, Kontogiannis 및 Spirakis의 알고리즘이 실제로 n과 로그 W에서 시간 다항식으로 실행된다는 경험적 증거를 보여줍니다.그들은 또한 이 알고리즘을 극적으로 가속화하는 초기 전략 벡터를 제안합니다.

일반적으로 가중 네트워크 CG에는 PNE가 없을 수 있습니다.Milchtaich는^[14] 주어진 가중 네트워크 CG에 PNE가 있는지 여부를 결정하는 것이 다음과 같은 경우에도 NP-hard임을 증명합니다.

• 두 명의 플레이어가 있습니다. 모든 플레이어는 모든 경로를 사용할 수 있습니다. 모든 비용 함수는 음수가 아닙니다.
• 두 개의 플레이어가 있습니다. CG는 가중치가 없고 비용은 플레이어별이며 음수가 아닙니다.

그 증거는 방향이 있는 에지-분리 경로 ^[40]문제에서 감소하는 것입니다.

Caragiannis, Fanelli, Gravin 및 스코팔릭은^[41] 가중 CG에서 상수 인자 근사 PNE를 계산하는 알고리듬을 제시합니다.특히:

• 선형 지연 함수를 사용하는 경우 $근사{\displaystyle \frac{\mathrm{}비율}{}}$은${\displaystyle }$3 + ${\displaystyle \mathrm{52}}$ +${\displaystyle }$O ($$ ) \$displaystyle {{frac {3+{\sqrt {5$}}{$2}}$+ O(\epsilon $)\}$이며, 런타임은 재생 횟수, 리소스 수 및 1/10진수에서 다항식입니다.
• 지연 함수가 차수 d 다항식인 경우 근사 비율은 ${\displaystyle {d\mathrm{}}^{}}$ ${\displaystyle {2d}^{}}$ +${\displaystyle {}^{}}$o (${\displaystyle d^{}}$ {$displaystyle$ d$^{2d+o(d$입니다.

그들의 결과를 증명하기 위해, 그들은 가중 CG가 잠재적인 기능을 가지고 있지 않을 수도 있지만, 모든 가중 CG가 특정 잠재적인 게임에 의해 근사될 수 있다는 것을 보여줍니다.이를 통해 모든 가중 CG에 (d!)-근사 PNE가 있음을 알 수 있습니다.그들의 알고리즘은 그러한 대략적인 PNE로 이어지는 최상의 응답 이동의 짧은 시퀀스를 식별합니다.

혼잡 게임 분류 요약

요약하면 CG는 다양한 매개 변수에 따라 분류할 수 있습니다.

• 플레이어 수 및 분할 가능성: 원자 CG, 분할 가능한 CG 또는 비원자 CG;
• 플레이어의 가중치: 가중치가 부여되지 않은 CG 또는 가중치가 부여된 CG(자원 독립 가중치 또는 자원별 가중치
• 동일한 리소스를 사용하는 여러 플레이어에 대한 비용 함수: 동일하거나 특정 플레이어(분리 가능하거나 분리 불가능한 비용 함수 포함).
• 가능한 전략: 하나의 리소스(싱글톤 CG) 또는 네트워크의 경로(네트워크 CG) 또는 임의의 하위 집합(일반 CG).
• 서로 다른 플레이어의 전략 세트: 서로 다른(비대칭 CG) 또는 동일한(대칭 CG).

참고 항목

• 모든 CG에는 내쉬 균형이 있기 때문에 다음 자연스러운 주제는 품질을 분석하는 것입니다.이것은 혼잡 게임에서 무정부 상태의 가격 개념을 사용하여 수행됩니다.
• ◦자원 할당 게임은^[42][31] 혼잡 게임과 다소 관련이 있습니다.
• 불완전한 정보:Facchini, van Megen, Borm 및 Tijs는^[35] Rosenthal의 모델을 불완전한 정보가 있는 환경으로 확장합니다.그들은 관련 베이지안 게임이 잠재적인 게임이므로 순수한 베이지안-내시 균형을 가지고 있음을 증명합니다.
• 연합:Fotakis, Kontogiannis 및^[43] Spirakis는 플레이어가 연합에 참여하는 CG를 연구합니다.
• 자연 속의 혼잡 게임:Milinsky는^[44] 자연스러운 CG가 내쉬 평형으로 수렴하는 실험을 설명합니다.그의 실험에서, 그는 탱크의 두 끝에서 6개의 스틱백을 먹였습니다.두 끝 사이의 물고기 분포는 평균적으로 먹이 공급률의 비율과 비슷해서 어떤 개별 물고기도 다른 쪽으로 이동하여 먹이 속도를 증가시킬 수 없었습니다.Mlichtaich는^[3] 특정 간 경쟁에서 CG에 대한 보다 일반적인 치료법을 제시합니다.

레퍼런스

외부 링크

• 잠재력과 혼잡 게임에 대한 이세이 만수르의 강의 노트.
• 잠재력과 혼잡 게임에 대한 마이클 펠드먼과 노암 니산의 강의 노트.
• Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.