Last Update: August 17, 2017.

Click for abstract

This thesis contains two parts.

Part I introduces novel frameworks for modeling uncertainty in auctions. This enables us to provide robust analysis to alternative specifications of preferences and information structures in Vickrey and VCG auctions.

Part II introduces novel frameworks for understanding first-order methods in optimization. This enables us to (1) break 20-year barriers on the running time used for solving positive linear programs, (2) reduce the complexity for solving positive semidefinite programs, and (3) strengthen the theory of matrix multiplicative weight updates and improve the theory of linear-sized spectral sparsification.

*Outcome:
Doctor of Science in Computer Science.*

Supervisor: | Jonathan Kelner | Associate Professor | MIT Math |

Supervisor: | Silvio Micali | Professor | MIT EECS |

Member: | Nir Shavit | Professor | MIT EECS |

Member: | Shafi Goldwasser | Professor | MIT EECS |

Click for abstract

In mechanism design, we replace the strong assumption that each
player knows his own payoff type *exactly* with the more
realistic assumption that he knows it only *approximately*: each
player i only knows that his true type θ_{i} is one among
a set K_{i}, and adversarially and secretly chosen in K_{i}
at the beginning of the game.

This model is closely related to the Knightian notion of uncertainty in economics, but we consider it from purely mechanism design's perspective. In particular, we study the classical problem of maximizing social welfare in auctions when players know their true valuations only within a constant multiplicative factor δ ∈ (0,1).

For single good auctions, we prove that no dominant-strategy mechanism can guarantee better social welfare than assigning the good to a random player. On the positive side, we provide tight upper and lower bounds for the social welfare achievable in undominated strategies, whether deterministically or probabilistically.

For multiple-good auctions, we prove that all dominant-strategy mechanisms can guarantee only an exponentially small fraction of the maximum social welfare, and the celebrated VCG mechanism (which is no longer dominant-strategy) guarantees, in undominated strategies, at most a doubly exponentially small fraction.

For general games beyond auctions, we provide definitional foundations for this new approximate-type model, and provide a universality result showing that all reasonable (including Bayesian or Knightian) models of type uncertainty are equivalent to our set-theoretic one, at least for the setting when the type space is "convex".

*Outcome: Master of Science in Computer Science.
Outcome: William A. Martin SM Thesis Award .*

Supervisor: | Silvio Micali | Professor | MIT EECS |

Member: | Ron Rivest | Professor | MIT EECS |

Member: | Shafi Goldwasser | Professor | MIT EECS |

Click for abstract

Nash equilibrium, named after John Forbes Nash, has become the most widely used solution concept in game theory, and is a profile of strategies in which none of the players has the incentive to unilaterally change her own. Recent advance of algorithmic game theory encourages computer scientists to estimate for example the computability or the approximation from an algorithm-theoretical point of view.

This dissertation studies two famous cases in algorithmic game theory.

The first one is the optimal pricing strategy with incomplete information. We define the rationality of agents to be the strategy satisfying Bayesian Nash Equilibrium, and establish the connection to the iteration of a monotone function. Based on this connection we design a polynomial algorithm to help calculate the exact equilibrium and the optimal pricing, with analytical approaches and techniques in matrix analysis.

The second one is a mechanism design problem in which we need to set up a truthful mechanism to ensure that players sit in a Nash Equilibrium when they report their true internal value. Our work is different with the majority of studies since we disallow the transfer of money. In the two-facility game in a metric space, we manage to prove theoretical lower and upper bounds for the approximation ratio in both the deterministic and randomized cases. Our bounds are tight up to a constant and significantly improve the best known results.

*Outcome: Bachelor of Science in Math and Physics.
Outcome: Excellent Undergraduate Thesis Award.*

- Chinese version. [PDF]
- English version. [paper 1] [paper 2]
- Defense presentation. [PPT in both English and Chinese]

Supervisor: | Pinyan Lu | Associate Researcher | MSRA |

Thesis Reviewer: | Wei Chen | Lead Researcher / Adjunct Professor | MSRA / Tsinghua University |

Chair: | Rencheng Shang | Professor | Tsinghua University |

Member: | Jiajiong Xiong | Professor | Tsinghua University |

Member: | Yansong Li | Associate Professor | Tsinghua University |