received_1440262454047345.jpeg

# Algorithmic Game Theory - Winter Term 2023/24 ## Lecture 5: Mechanism Design without Money ### 1. Introduction In the previous lectures, we looked at settings where payments were possible. However, there are many settings where payments are impossible or undesirable. * Selecting a search engi...

# Algorithmic Game Theory - Winter Term 2023/24 ## Lecture 5: Mechanism Design without Money ### 1. Introduction In the previous lectures, we looked at settings where payments were possible. However, there are many settings where payments are impossible or undesirable. * Selecting a search engine * Electing a political leader * Allocating scarce resources **Mechanism Design without Money:** Design a game so that in equilibrium the outcome is socially desirable, even though players act selfishly. ### 2. Social Choice Function * Set of possible outcomes $O$. * Set of $n$ agents. * Each agent $i$ has a type $\theta_i \in \Theta_i$. * $\theta = (\theta_1,..., \theta_n) \in \Theta = \Theta_1 \times... \times \Theta_n$ is the type profile. * Each agent $i$ has a utility function $u_i : O \times \Theta_i \rightarrow \mathbb{R}$. * Social Choice Function (SCF) $f : \Theta \rightarrow O$ * Mapping from type profiles to outcomes. * Specifies what outcome should be implemented for each possible type profile. **Examples:** * **Voting:** * $O$: set of candidates * $\Theta_i$: set of all possible preference orderings over candidates. * $f$: winner determination rule * **Public Project:** * $O = \{ \text{build, don't build} \}$ * $\Theta_i$: cost of the project for agent $i$ * $f(\theta) = \text{build}$ if and only if $\sum_i \theta_i \leq C$. * **Matching:** * $O$: set of all possible matchings * $\Theta_i$: preferences of agent $i$ over possible partners. * $f$: stable matching ### 3. Implementation **Mechanism:** A game form $G = (A_1,..., A_n, g)$, where * $A_i$ is the set of possible actions (strategies) of agent $i$. * $g: A_1 \times... \times A_n \rightarrow O$ is the outcome function. **Implementation:** A mechanism $G = (A_1,..., A_n, g)$ implements the SCF $f$ in equilibrium concept $X$ if for all $\theta \in \Theta$: * There exists an equilibrium $a \in A_1 \times... \times A_n$ of $G$ under solution concept $X$ given $\theta$. * $g(a) = f(\theta)$. **Dominant Strategy Implementation:** A mechanism $G = (A_1,..., A_n, g)$ implements the SCF $f$ in dominant strategies if for all $\theta \in \Theta$: * $s_i(\theta_i)$ is a dominant strategy for each agent $i$. * $g(s_1(\theta_1),..., s_n(\theta_n)) = f(\theta)$. **Truthful Implementation:** A mechanism $G = (A_1,..., A_n, g)$ truthfully implements the SCF $f$ in dominant strategies if for all $\theta_i \in \Theta_i$, $\theta \in \Theta$, and $i$: * $A_i = \Theta_i$. * $s_i(\theta_i) = \theta_i$ is a dominant strategy for each agent $i$. * $g(\theta) = f(\theta)$. ### 4. Strategy-proofness SCF $f$ is strategy-proof if telling the truth is a dominant strategy for each agent. $f$ is strategy-proof if for all $i$, all $\theta_i, \theta'_i \in \Theta_i$, and all $\theta_{-i} \in \Theta_{-i}$: $$ u_i(f(\theta_i, \theta_{-i}), \theta_i) \geq u_i(f(\theta'_i, \theta_{-i}), \theta_i) $$ ### 5. Example: Facility Location * Set of possible outcomes $O = \mathbb{R}$. * Set of $n$ agents. * Each agent $i$ has a type $\theta_i \in \mathbb{R}$. * Agent $i$'s utility function is $u_i(o, \theta_i) = -|o - \theta_i|$. **Median Rule:** Selects the median of the reported locations. * $f(\theta) = \text{median}(\theta_1,..., \theta_n)$. **Theorem:** The median rule is strategy-proof. * **Proof:** W.l.o.g., assume that agent $i$’s true location $\theta_i$ is less than the median of all agents’ reported locations. * Case 1: $\theta'_i < \theta_i$ * Reporting $\theta'_i$ instead of $\theta_i$ will not change the median. * Agent $i$ is indifferent between reporting $\theta'_i$ and $\theta_i$. * Case 2: $\theta'_i > \theta_i$ * If the new median is less than $\theta_i$, then agent $i$ is worse off. * If the new median is greater than $\theta_i$, then agent $i$ is better off. * However, agent $i$ can always do better by reporting $\theta_i + \epsilon$ for some small $\epsilon > 0$. * Therefore, the median rule is strategy-proof. ### 6. Gibbard-Satterthwaite Theorem **Theorem:** If * $|O| \geq 3$, * $f$ is onto (i.e., for every outcome $o \in O$, there exists a type profile $\theta \in \Theta$ such that $f(\theta) = o$), and * $f$ is strategy-proof, then $f$ is dictatorial (i.e., there exists an agent $i$ such that $f(\theta)$ only depends on $\theta_i$). **Implications:** * The Gibbard-Satterthwaite Theorem is a very negative result. * It says that any SCF that is onto and strategy-proof must be dictatorial. * In other words, the only SCFs that are strategy-proof are those that are dictatorial. ### 7. Circumventing Gibbard-Satterthwaite * Restricting the domain of preferences * Relaxing the onto condition * Changing the solution concept ### 8. Single-Peaked Preferences Agent $i$'s preferences are single-peaked if there exists a location $\theta_i$ such that for all $o, o' \in O$: $$ |o - \theta_i| < |o' - \theta_i| \Rightarrow u_i(o, \theta_i) > u_i(o', \theta_i) $$ In words, agent $i$'s utility decreases as the outcome moves away from their ideal point. ### 9. Black's Median Voter Theorem **Theorem:** If all agents have single-peaked preferences, then the median rule is strategy-proof and Pareto efficient. **Pareto Efficient:** An outcome is Pareto efficient if there is no other outcome that makes at least one agent better off without making any other agent worse off. **Proof:** * We already showed that the median rule is strategy-proof. * To see that it is Pareto efficient, note that any outcome other than the median can be improved upon by moving it closer to the median. * Therefore, the median rule is Pareto efficient.