Videos

Algorithms, Approximation, and Learning in Market and Mechanism Design: "Dual Reduction and Elementary Games with Senders and Receivers"

Presenter
November 8, 2023
Keywords:
  • market design
  • mechanism design
  • auctions
  • matching
  • approximation
  • equilibrium analysis
  • algorithmic game theory
  • complexity
  • economic theory
  • discrete optimization
  • graph theory
  • mathematical programming
Abstract
Consider the incentive constraints that define the incentive-compatible mechanisms of a senders-receivers game. Duals of these linear constraints form Markov chains on the senders' type sets and the receivers' action sets. The minimal nonempty absorbing sets of these Markov chains can be interpreted as the types and actions in a dual-reduced game. Any incentive-compatible mechanism of a dual-reduced game induces an equivalent incentive compatible mechanism for the original game. We say that a game is elementary if all nontrivial incentive constraints can be satisfied as strict inequalities in incentive-compatible mechanisms. Any senders-receivers game can be reduced to an elementary game by iterative dual reduction.