IMG_3991.jpeg

# Algorithmic Game Theory ## What is Game Theory? Game theory is the study of **mathematical models of strategic interaction** among rational agents. It has applications in all fields of social science, as well as in logic, systems science and computer science. ### Traditional Game Theory vs. Alg...

# Algorithmic Game Theory ## What is Game Theory? Game theory is the study of **mathematical models of strategic interaction** among rational agents. It has applications in all fields of social science, as well as in logic, systems science and computer science. ### Traditional Game Theory vs. Algorithmic Game Theory | Traditional Game Theory | Algorithmic Game Theory | | :------------------------------------------------------ | :------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | Focus: | Focus: | | \- Existence theorems | \- Design | | \- Characterization | \- Efficiency | | \- (static) properties of equilibria | \- Computation | | Typical assumption: Agents can do arbitrary computation | Typical assumption: Agents are computationally bounded. (And the system might be designed by someone who wants to achieve a good outcome despite agents' selfishness) | ## Selfish Routing ### The Model * A network of $n$ nodes and $m$ edges. * Each edge $e$ has a cost function $c_e(x)$ which is the cost (or delay) incurred by each unit of traffic traversing edge $e$ when the traffic amount is $x$. * We assume $c_e(x)$ is non-negative and non-decreasing, i.e., the more congested the edge is, the higher the cost. * There are $k$ classes of users (or commodities). * For each class $i$, there is a source $s_i$ and a destination $t_i$. * There is a traffic amount (or demand) $r_i$ that needs to be routed from $s_i$ to $t_i$. ### Definition: Flows A **flow** $f$ consists of a flow rate $f_p \geq 0$ for each path $p$ in the network. * $f_p$: The amount of traffic following path $p$. * A flow $f$ is feasible for a set of demands $(r_1, \cdots, r_k)$ if for each $i$, the total flow from $s_i$ to $t_i$ is equal to $r_i$. * The amount of flow on edge $e$ is $f_e = \sum_{p: e \in p} f_p$. ### Definition: Cost The cost incurred by users of class $i$ is: $\qquad \sum_{p: s_i \rightarrow t_i} f_p \cdot c_p(f)$ Where $c_p(f) = \sum_{e \in p} c_e(f_e)$ is the cost of path $p$. The social cost of a flow $f$ is: $\qquad C(f) = \sum_{e \in E} f_e \cdot c_e(f_e)$ ### Definition: Wardrop Equilibrium A flow $f$ is at **Wardrop equilibrium** if for each class $i$ and each pair of paths $p, p'$ between $s_i$ and $t_i$: * If $f_p > 0$, then $c_p(f) \leq c_{p'}(f)$. * In other words, all flow is sent along shortest paths. ### Fact Wardrop equilibria always exist.