सोशल कॉस्ट और प्राइस ऑफ़ एनार्की

सोशल कॉस्ट (Social Cost)

• किसी गेम $G = (N, (S_i){i \in N}, (c_i){i \in N})$ और स्ट्रेटेजी प्रोफाइल $s = (s_1, \dots, s_n) \in S$ के लिए, सोशल कॉस्ट $CS(s) = \sum_{i \in N} c_i(s)$ होती है।

प्राइस ऑफ़ एनार्की (PoA)

• प्राइस ऑफ़ एनार्की एक इक्विलिब्रियम के सोशल कॉस्ट और ऑप्टिमल आउटकम के सोशल कॉस्ट के बीच सबसे ख़राब केस अनुपात है।
• $PoA = \frac{\max_{s \in S: s \text{ is an equilibrium}} CS(s)}{\min_{s \in S} CS(s)}$
• इसे कभी-कभी कोऑर्डिनेशन रेशियो भी कहा जाता है।

वार्डरो टॉप मॉडल (Wardrop Model)

• वार्डरो टॉप मॉडल एक टपल $G = (N, E, (S_i){i \in N}, (l_e){e \in E})$ है जहाँ:
  • $N$ प्लेयर्स का सेट है।
  • $E$ ग्राफ में एज का सेट है।
  • $S_i$ प्लेयर $i$ के लिए स्ट्रेटेजी का सेट है, जहाँ हर स्ट्रेटेजी ग्राफ के थ्रू एक पाथ है।
  • $l_e$ हर एज से एसोसिएटेड कॉस्ट (या लेटेंसी) फंक्शन है।

वार्डरो टॉप मॉडल में नैश इक्विलिब्रियम (Nash Equilibrium)

• वार्डरो टॉप मॉडल में नैश इक्विलिब्रियम एक ऐसी स्टेट है जिसमें कोई भी प्लेयर अपनी स्ट्रेटेजी (यानी, अपने पाथ) को बदलकर यूनिलैटरली अपनी कॉस्ट को इम्प्रूव नहीं कर सकता है।

वार्डरो टॉप मॉडल में सोशल कॉस्ट (Social Cost)

• वार्डरो टॉप मॉडल में सोशल कॉस्ट सभी प्लेयर्स की कॉस्ट का योग है: $CS(s) = \sum_{i \in N} c_i(s)$

ब्रेस्स का पैराडॉक्स (Braess's Paradox)

• मान लीजिये 1 यूनिट फ्लो $s$ से $t$ तक जाता है।
• डैशड एज के बिना:
  • पाथ $s \to a \to t$: कॉस्ट $x+1+x = 2x+1$।
  • नैश इक्विलिब्रियम पर, $x=\frac{1}{2}$, इसलिए कॉस्ट $2 \cdot \frac{1}{2} + 1 = 2$ है। सोशल कॉस्ट 2 है।
• डैशड एज के साथ:
  • पाथ $s \to a \to t$: कॉस्ट $x$।
  • पाथ $s \to b \to t$: कॉस्ट $1$।
  • नैश इक्विलिब्रियम पर, सारा फ्लो $s \to a \to b \to t$ के साथ जाता है। सोशल कॉस्ट $1+1=2$ है।
• ऑप्टिमल फ्लो $s \to a \to t$ के साथ $\frac{1}{2}$ और $s \to b \to t$ के साथ $\frac{1}{2}$ है, सोशल कॉस्ट $1.5$ है।
• इसलिए PoA $\frac{2}{1.5} = \frac{4}{3}$ है।

एनार्की की प्राइस को बाउंड करना (Bounding the Price of Anarchy)

• अगर सभी कॉस्ट फंक्शन लीनियर हैं, तो एनार्की की प्राइस ज़्यादा से ज़्यादा $\frac{4}{3}$ है।

प्रमाण (Proof)

• मान लीजिये $f_e$ इक्विलिब्रियम में एज $e$ पर फ्लो है, और $f_e^*$ ऑप्टिमल सोलुशन में एज $e$ पर फ्लो है। मान लीजिये $C(f) = \sum_e l_e(f_e) \cdot f_e$ फ्लो $f$ की सोशल कॉस्ट है।
• चूँकि $f$ एक इक्विलिब्रियम है, इसलिए पाथ $P$ का इस्तेमाल करने वाला प्लेयर पाथ $P'$ पर स्विच करके अपनी कॉस्ट को इम्प्रूव नहीं कर सकता है। इसलिए, $f$ में किसी भी पाथ $P$ और $f^*$ में किसी भी पाथ $P'$ के लिए, हमारे पास है (1) $\sum_{e \in P} l_e(f_e) \le \sum_{e \in P'} l_e(f_e)$।
• इसलिए, $\sum_e f_e^* \cdot l_e(f_e) \ge \sum_e f_e \cdot l_e(f_e)$।
• अब, चूँकि $l_e(x) = a_e \cdot x + b_e$ लीनियर है, इसलिए हमारे पास है $C(f) = \sum_e f_e \cdot l_e(f_e) = \sum_e f_e \cdot (a_e f_e + b_e)$।
• हम $\frac{C(f)}{C(f^)} = \frac{\sum_e f_e \cdot l_e(f_e)}{\sum_e f_e^ \cdot l_e(f_e^*)}$ को बाउंड करना चाहते हैं।
• $\frac{4}{3}$ की बाउंड टाइट है।