Game Theory: Strategic Interactions

What is Game Theory?

• Involves mathematical models of strategic interactions among rational agents.
• Applicable to social science, logic, systems science, and computer science.
• Originated with John von Neumann's 1928 proof.
• Extensively developed in the 1950s, applied to political, economic, and military situations.
• "Game" signifies interaction where each player's outcome depends on decisions of others.
• Used to analyze various situations.

Example Games and Questions

• Auctions raise the question of how to bid.
• Routing asks how to avoid congestion.
• Social networks examine how to spread information.
• Economics considers how to set product prices.
• Security focuses on how to allocate limited resources to protect a target.

Selfish Routing (Roughgarden & Tardos)

• Model involves a network of $n$ nodes and $m$ edges.
• Each edge $e$ carries a cost function $\mathcal{L}_e(x)$, dependent on traffic amount.
• Flow represents traffic rate from source $s$ to target $t$.

Wardrop Equilibrium

• Traffic splits among paths ensuring all used paths have equal cost; unused paths have no less cost.
• A Wardrop equilibrium functions as a Nash equilibrium.

Braess's Paradox

• Adding network capacity can surprisingly increase average latency for users.

Price of Anarchy

• Measures the difference between Wardrop equilibrium and optimal routing.
• Formula: $PoA = \frac{\text{Cost of Wardrop Equilibrium}}{\text{Cost of Optimal Routing}}$

Mechanism Design

• Subfield of game theory focused on designing games to achieve a desired outcome despite self-interested players.
• Called "reverse game theory" due to starting with the outcome and designing the game backward.

Example

• Auctions ask how to maximize revenue for the seller.
• Voting examines how to design a system that reflects voters' preferences accurately.
• Task assignment considers how to maximize social welfare.

Revelation Principle

• In many settings, focusing on truthful mechanisms is sufficient, where players are incentivized to report true preferences.
• Simplifies mechanism design by focusing on truthful mechanisms.

VCG Mechanism

• A truthful mechanism that maximizes social welfare.
• Players pay the externality they impose on others.
• Widely used due to efficiency and truthfulness.

Review: Achievable Rate Region for Gaussian MAC

• For a Gaussian MAC, the equation is $Y = X_1 + X_2 + Z$ where $Z \sim \mathcal{N}(0, N)$.
• With power constraint $P_1, P_2$, the achievable rate region is the convex hull of rate pairs $(R_1, R_2)$.
• Rates must satisfy:
  • $R_1 < I(X_1; Y|X_2) = \frac{1}{2}log(1 + \frac{P_1}{P_2 + N})$
  • $R_2 < I(X_2; Y|X_1) = \frac{1}{2}log(1 + \frac{P_2}{P_1 + N})$
  • $R_1 + R_2 < I(X_1, X_2; Y) = \frac{1}{2}log(1 + \frac{P_1 + P_2}{N})$
• Corner points are achieved by time-sharing.
• The capacity region is the achievable region.

Gaussian Broadcast Channel

• Given by:
  • $Y_1 = X + Z_1$
  • $Y_2 = X + Z_2$
  • $Z_1 \sim \mathcal{N}(0, N_1)$, $Z_2 \sim \mathcal{N}(0, N_2)$
• Assume $N_1 \le N_2$, meaning user 1 is "better" than user 2.
• Independent messages should be sent to both users.
• Write $X = U + V$, allocate powers $P_U$ and $P_V$.
• Send information $W_2$ for user 2 in the "cloud" $U$ and $W_1$ for user 1 in $V$.
• User 2 decodes $W_2$ treating $V$ as noise.
• User 1 decodes $W_1$ after subtracting out $W_2$.

Encoding

• Codebook $\mathcal{C}_2$ for $W_2$: $U^n(W_2) \sim i.i.d. \mathcal{N}(0, P_U)$
• For each $U^n(w_2)$, generate a codebook $\mathcal{C}_1(w_2)$ for $W_1$: $V^n(w_1) \sim i.i.d. \mathcal{N}(0, P_V)$
• $X^n = U^n(w_2) + V^n(w_1)$.

Decoding

• User 2 decodes $W_2$, finding $\hat{W}_2$ such that $(U^n(\hat{W}2), Y_2^n) \in A{\epsilon}^{(n)}$.
• Declared $\hat{W}_2$ if unique. Achievable rate: $R_2 < I(U; Y_2) = \frac{1}{2}log(1 + \frac{P_U}{P_V + N_2})$.
• User 1 subtracts out $U^n(\hat{w}_2)$ and decodes $W_1$: look for $\hat{W}_1$ such that $(V^n(\hat{W}_1), Y_1^n - U^n(\hat{W}2)) \in A{\epsilon}^{(n)}$
• Declared $\hat{W}_1$ if unique.
• Achievable rate: $R_1 < I(V; Y_1|U) = \frac{1}{2}log(1 + \frac{P_V}{N_1})$.

Inner Bound

• Shown visually in a rate region diagram.

Capacity Region

• Capacity region is the closure of rate pairs $(R_1, R_2)$.
• Rates must satisfy:
  • $R_1 \le \frac{1}{2}log(1 + \frac{\alpha P}{N_1})$
  • $R_2 \le \frac{1}{2}log(1 + \frac{(1 - \alpha)P}{\alpha P + N_2})$
• For some $0 \le \alpha \le 1$.
• Choose $P_V = \alpha P$ and $P_U = (1 - \alpha)P$.

Why is superposition coding optimal?

• Key idea: Successive refinement of information.
• $X \longrightarrow Y_1 \longrightarrow Y_2$
• Degradedness: $I(X; Y_1) \ge I(X; Y_2), \forall P_X$
• For information to $Y_2$, full resolution (required by $Y_1$) is unnecessary.

Duality

• Relates Broadcast Channel and Multiple Access Channel.

Broadcast Channel

• One encoder sends messages to multiple decoders.

Multiple Access Channel

• Multiple encoders send messages to one decoder.
• Roles of encoder and decoder are swapped.
• Message $W_i$ becomes side information $U_i$.

Análisis de Algoritmos

• Orden de Complejidad Asintótica describes the limit of an algorithm when the size of the input becomes infinitely larger.

Notación Big-O

• $O(g(n))$ defines the set of functions that grow no faster than $g(n)$, where $n$ is the size of the input.

Notación Omega

• $\Omega(g(n))$ defines the set of functions that grow no slower than $g(n)$.

Notación Theta

• $\Theta(g(n))$ defines the set of functions that grow at the same rate as $g(n)$.

Clases de Complejidad Comunes

• $O(1)$ or Constant, can be exemplified by accessing an array element via its index.
• $O(log n)$ or Logarithmic, can be exemplified by a binary search in a sorted array.
• $O(n)$ or Linear, can be exemplified by a search within an unsorted Array.
• $O(n log n)$ or Linear-Logarithmic, can be exemplified by efficient sequencing algorithms (merge sort).
• $O(n^2)$ or Quadratic, can be exemplified by bubble sequencing.
• $O(n^3)$ or Cubic, can be exemplified by matrix multiplication.
• $O(2^n)$ or Exponential, can be exemplified by a traveler dilemma.
• $O(n!)$ or Factorial, can be exemplified by creating complete list specifications.

Análisis de Bucles

• Bucle Simple: The complexity is the number of times the loop runs multiplied by the complexity of the operations within the loop.
• Bucles Anidados: The complexity is the product of the number of iterations of all loops.

Análisis de Recursión

• Recursion algorithms' complexity are determined with recurrence relations.
• The recurrence relation for binary search is $T(n) = T(n/2) + O(1)$.
• Solutions are $T(n) = O(log n)$.

Example of Code (Python)

def linear_search(arr, target):
    """
    Looks for a goal in an array.
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i # Returns index if located.
    return -1 # Returns -1 if not located.

• Complexity: $O(n)$ in the worst case, where $n$ is the length of the array.

Tips for Improving Complexity

• Efficient data structures should be used such as tables and hash search trees.
• Apply divide and win algorithms.
• Avoid redundant calculations by memorization.

Warning

• Asymptotic complexity analysis provides performance information lacking important constants and factors for low order small entry sizes.

What is Algorithmic Trading

• Uses computer programs to follow an algorithm for placing a trade.
• Algorithms consider timing, price, quantity, and mathematical models.
• Widely used by investment banks, pension funds, hedge funds, and other institutional traders.

Why do Algo Trading?

• Minimizes transaction costs and improves order execution speed.
• Takes advantage of arbitrage and diversifies trading.
• Allows backtesting and reduces human error.

Types of Strategies

Trend Following

• Identifies and capitalizes on existing market trends.
• Uses moving averages or technical indicators to identify trends and execute trades accordingly.

Mean Reversion

• Identifies deviations from the average asset price.
• Executes trades based on the expectation that price reverts to its mean level.
• Relies on statistical analysis and probability.

Arbitrage

• Exploits price differences for the same asset in different markets.
• Identifies price differences, buys cheaper assets, and sells more expensive ones simultaneously.
• Aims to generate risk-free profits from temporary mispricing.

Index Fund Trading

• Replicates performance of a specific market index like the S&P 500.
• Automatically buys and sells stocks in proportion to the index's holdings.
• Implements a low-cost, passive investment strategy.

Mathematical Model Based

• Identifies trading opportunities using sophisticated mathematical models.
• Models incorporate statistical analysis, econometric modeling, and machine learning.

How to get Started with Algorithmic Trading

• Learn Python programming language.
• Establish a brokerage account with API access via Interactive Brokers or Alpaca.
• Find a data provider like Polygon or IEX Cloud.
• Develop and backtest the algorithm using historical data for refinement.
• Automate the algorithm and monitor its performance.

Conclusion

• Algorithmic trading is a tool that improves trading.
• Understand risks before using algorithmic trading.
• Can be a valuable asset with planning and execution.