TechTalks from event: FOCS 2011

We will be uploading the videos for FOCS 2011 during the week of Nov 28th 2011. If you find any discrepancy, please let us know by clicking on report error link on talk page. If you did not permit the video to be published and by mistake we have published your talk, please notify us immediately at support AT weyond.com

1B

  • How Bad is Forming Your Own Opinion? Authors: David Bindel and Jon Kleinberg and Sigal Oren
    A long-standing line of work in economic theory has studied models by which a group of people in a social network, each holding a numerical opinion, can arrive at a shared opinion through repeated averaging with their neighbors in the network. Motivated by the observation that consensus is rarely reached in real opinion dynamics, we study a related sociological model in which individuals' intrinsic beliefs counterbalance the averaging process and yield a diversity of opinions. By interpreting the repeated averaging as best-response dynamics in an underlying game with natural payoffs, and the limit of the process as an equilibrium, we are able to study the cost of disagreement in these models relative to a social optimum. We provide a tight bound on the cost at equilibrium relative to the optimum; our analysis draws a connection between these agreement models and extremal problems for generalized eigenvalues. We also consider a natural network design problem in this setting, where adding links to the underlying network can reduce the cost of disagreement at equilibrium.
  • The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. Authors: Paul W. Goldberg and Christos H. Papadimitriou and Rahul Savani
    We show that the widely used homotopy method for solving fixpoint problems, as well as the Harsanyi-Selten equilibrium selection process for games, are PSPACE-complete to implement. Extending our result for the Harsanyi-Selten process, we show that several other homotopy-based algorithms for solving games are also PSPACE-complete to implement. A further application of our techniques yields the result that it is PSPACE-complete to compute any of the equilibria that could be found via the classical Lemke-Howson algorithm, a complexity-theoretic strengthening of the result in [24]. These results show that our techniques can be widely applied and suggest that the PSPACE-completeness of implementing homotopy methods is a general principle.
  • Welfare and Profit Maximization with Production Costs Authors: Avrim Blum and Anupam Gupta and Yishay Mansour and Ankit Sharma
    Combinatorial Auctions are a central problem in Algorithmic Mechanism Design: pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare, revenue, or profit). The problem has been well-studied in the case of limited supply (one copy of each item), and in the case of digital goods (the seller can produce additional copies at no cost). Yet the case of resources---think oil, labor, computing cycles, etc.---neither of these abstractions is just right: additional supplies of these resources can be found, but only at a cost (where the marginal cost is an increasing function). In this work, we initiate the study of the algorithmic mechanism design problem of combinatorial pricing under increasing marginal cost. The goal is to sell these goods to buyers with unknown and arbitrary combinatorial valuation functions to maximize either the social welfare, or our own profit; specifically we focus on the setting of \emph{posted item prices} with buyers arriving online. We give algorithms that achieve constant factor approximations for a class of natural cost functions---linear, low-degree polynomial, logarithmic---and that give logarithmic approximations for all convex marginal cost functions (along with a necessary additive loss). We show that these bounds are essentially best possible for these settings
  • The Second-Belief Mechanism. Authors: Jing Chen and Silvio Micali
    In settings of incomplete information, we put forward a very conservative ---indeed, purely set-theoretic--- model of the knowledge that the players may have about the types of their opponents. Yet, we prove that such knowledge can be successfully and robustly leveraged by means of a solution concept relying on very weak assumptions: in essence, via extensive-form mechanisms under “mutual” knowledge of rationality. We demonstrate the potential of our approach in auctions of a single good by 1. considering a new revenue benchmark, always lying between the highest and second-highest valuation, 2. proving that no classical mechanism can even slightly approximate it in any robust way, and 3. providing a new mechanism that perfectly and robustly achieves it, with the extra property that the good will always be sold out at the end of the auction. Our impossibility result for robustly implementing our revenue benchmark applies not only to implementation in dominant strategies, but also to any implementation ``at equilibrium", as well as to implementation in undominated strategies.