Numerical Solutions to Ordinary Differential Equations

Numerical Solution of Ordinary Differential Equations

• Analytical solutions to ordinary differential equations (ODEs) can be found in some special cases.
• Numerical solutions are often needed since most ODEs can’t be solved analytically.

First Order ODEs and Discretization

• For a first order ODE: $\frac{dy}{dx} = f(x, y), y(x_0) = y_0$
• The x-coordinate can be discretized as: $x_0, x_1 = x_0 + h, x_2 = x_0 + 2h,..., x_n = x_0 + nh$
• $h$ represents the step size in the discretization.
• Derivatives can be approximated using the finite difference method: $\frac{dy}{dx} \approx \frac{y_{i+1} - y_i}{h}$

Euler Method

• The Euler method is a numerical method to solve ODEs
• Gives the formula: $y_{i+1} = y_i + hf(x_i, y_i)$
• Given an initial value $y(x_0) = y_0$, we can calculate $y_1, y_2,..., y_n$.

Example of Euler Method

• Given the ODE $\frac{dy}{dx} = -2xy, y(0) = 1$, solve using the Euler method with $h = 0.1$.
• The Euler method formula becomes: $y_{i+1} = y_i - 2hx_iy_i$
• Starting with $y_0 = 1, x_0 = 0$, we find $y_1 = 1$, $y_2 = 0.98$, and $y_3 = 0.9408$.

Error Analysis of Euler Method

• The error of the Euler method is proportional to the step size $h$.
• Since the Euler method has error $\propto h$, it is called a first-order method.
• To reduce error: Use smaller step sizes and/or higher-order methods

Taylor Expansion

• Taylor expansion is applied for error analysis and to derive other numerical methods: $y(x + h) = y(x) + hy'(x) + \frac{h^2}{2!}y''(x) + \frac{h^3}{3!}y'''(x) +...$

Second-Order Taylor Method

• The second-order Taylor method uses the first three terms of the Taylor expansion:
• $y_{i+1} = y_i + hy'(x_i) + \frac{h^2}{2!}y''(x_i)$
• Rewritten: $y_{i+1} = y_i + hf(x_i, y_i) + \frac{h^2}{2!}f'(x_i, y_i)$
• $f'(x_i, y_i)$ can be expressed as $\frac{\partial f}{\partial x} + \frac{\partial f}{\partial y}\frac{dy}{dx} = \frac{\partial f}{\partial x} + \frac{\partial f}{\partial y}f(x, y)$

Example of Second-Order Taylor Method

• Given the ODE $\frac{dy}{dx} = -2xy, y(0) = 1$, solve it using the second-order Taylor method with $h = 0.1$.
• Calculate the partial derivatives of : $f(x, y) = -2xy$
• $\frac{\partial f}{\partial x} = -2y$ and $\frac{\partial f}{\partial y} = -2x$ resulting in $f'(x, y) = -2y + 4x^2y$
• The second-order Taylor method formula becomes: $y_{i+1} = y_i - 2hx_iy_i + h^2(-y_i + 2x_i^2y_i)$
• Starting with $y_0 = 1, x_0 = 0$, we find $y_1 = 0.99$ and $y_2 = 0.960594$.

Física

Vectores

• Vectors have magnitude and direction

Suma de vectores

Método gráfico

• Vectors are placed consecutively, maintaining direction and magnitude.
• The resultant vector connects the origin of the first vector with the end of the last vector.

Método analítico

• To sum vectors analytically:
• Decompose vectors into horizontal ($v_x$) and vertical ($v_y$) components.
  • $v_x = v \cdot \cos(\theta)$
  • $v_y = v \cdot \sin(\theta)$
• Sum the horizontal and vertical components.
  • $R_x = v_{1x} + v_{2x} +... + v_{nx}$
  • $R_y = v_{1y} + v_{2y} +... + v_{ny}$
• Calculate the magnitude of the resultant vector.
  • $|R| = \sqrt{R_x^2 + R_y^2}$
• Calculate the direction of the resultant vector.
  • $\theta = \arctan(\frac{R_y}{R_x})$

Producto de vectores

Producto escalar

• The dot product of two vectors results in a scalar.
• $\vec{A} \cdot \vec{B} = |\vec{A}| \cdot |\vec{B}| \cdot \cos(\theta)$
• The dot product is maximum when vectors are parallel ($\theta = 0$) and zero when vectors are perpendicular ($\theta = 90$).

Producto vectorial

• The cross product of two vectors results in a vector.
• $\vec{A} \times \vec{B} = |\vec{A}| \cdot |\vec{B}| \cdot \sin(\theta) \cdot \hat{n}$
• $\hat{n}$ is a unit vector perpendicular to the plane formed by $\vec{A}$ and $\vec{B}$.
• The direction of $\hat{n}$ is determined by the right-hand rule.
• The cross product is maximum when vectors are perpendicular ($\theta = 90$) and zero when vectors are parallel ($\theta = 0$).

Algorithmic Game Theory - Winter Term 2023/24

Mechanism Design without Money

• It involves designing games where the outcome is good regardless of how players behave.

Goals of Mechanism Design

• Implement a social choice function (in dominant strategies).
• Maximize revenue.

Revelation Principle

• It focuses on mechanisms where players truthfully report their types.

Social Choice Functions

• A social choice function maps agent types to outcomes.
• Definitions:
  • Set of possible outcomes: $O$.
  • Set of $n$ agents.
  • Each agent $i$ has a type $\theta_i \in \Theta_i$.
  • $\Theta = \Theta_1 \times \dots \times \Theta_n$.
  • Social choice function: $f : \Theta \to O$.

Social Choice Function Examaples

• $O = {a, b}$, $n = 2$:
  • $f(\theta_1, \theta_2) = a$ if $\theta_1 + \theta_2 \geq 5$, and $b$ otherwise
• $O = {\text{allocation of goods}}$, $\theta_i = \text{valuation of agent } i$
• $O = {\text{set of edges in a graph}}$, $\theta_i = \text{set of edges agent } i \text{ considers "cheap"}$

Implementation in Dominant Strategies

• Relies on agents having types.

• Definition of a mechanism:

  • $(\Sigma_1, \dots, \Sigma_n, g)$, where $\Sigma_i$ is the set of strategies for agent $i$, and $g : \Sigma_1 \times \dots \times \Sigma_n \to O$ is the outcome function.

• Definition of implementing a social choice function:

  • A mechanism $(\Sigma_1, \dots, \Sigma_n, g)$ implements a social choice function $f$ in dominant strategies if there exists a strategy profile $s^* = (s_1^, \dots, s_n^)$ such that:
  • $s_i^*(\theta_i)$ is a dominant strategy for each agent $i$.
  • $g(s_1^(\theta_1), \dots, s_n^(\theta_n)) = f(\theta_1, \dots, \theta_n)$ for all $(\theta_1, \dots, \theta_n) \in \Theta$.

• A strategy $s_i^*$ is dominant if for all $\theta_i \in \Theta_i$:

  • $g(s_i^*(\theta_i), s_{-i}) \succeq_i g(s_i', s_{-i})$ for all $s_i' \in \Sigma_i$ and all $s_{-i} \in \Sigma_{-i}$.
  • where $\succeq_i$ is agent $i$'s preference relation.

Revelation Principle Details

• A mechanism is a direct mechanism is:

  • $\Sigma_i = \Theta_i$ for each agent $i$.
  • $g(\theta_1, \dots, \theta_n) = f(\theta_1, \dots, \theta_n)$ for all $(\theta_1, \dots, \theta_n) \in \Theta$.

• Definition of a truthful direct mechanism involves truthful reporting as a dominant strategy.

• If a social choice function can be implemented in dominant strategies, it can be implemented by a truthful direct mechanism.

Voting Example

• Involves $n$ agents and 2 alternatives ($A$ and $B$).
• Each agent $i$ has a preferred alternative $\theta_i \in {A, B}$.
• Social choice function selects the alternative preferred by the majority.
• Implementation in dominant strategies can be achieved using the VCG mechanism.

Impossibility Results

• Not all social choice functions can be implemented in dominant strategies.
• The Gibbard-Satterthwaite Theorem identifies conditions under which implementation in dominant strategies is impossible.

Circumventing Impossibility

• Solutions to avoid impoosibility results include:
• Money: VCG mechanism (Lecture 6).
• Restricted preferences: E.g., single-peaked preferences.
• Approximation: Implement a social choice function that is "close" to the desired one.
• Bayesian mechanism design: Assume agents have beliefs about the types of other agents.
• Relaxing Dominance: Implement in Bayes-Nash Equilibrium.