Zeyuan ALLEN-ZHU

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.

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".

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.