Econometrics in Games and Auctions (Part I)
Vasilis Syrgkanis (Microsoft Research)
4849 - 4860 of 20065 Results
Format results
PSI Lecture - Condensed Matter - Lecture 9
Aaron Szasz Alphabet (United States)
Complexity of the python’s lunch and quantum gravity in the lab
Hrant Gharibyan Stanford University
Dynamical Systems and Learning in Games (Part IV)
Georgios Piliouras (Singapore University of Technology and Design)Dynamical Systems and Learning in Games (Part III)
Georgios Piliouras (Singapore University of Technology and Design)Entropy decay for Davies semigroups of a one dimensional quantum lattice
Angela Capel Instituto de Ciencias Matemáticas (ICMAT)
Dynamical Systems and Learning in Games (Part II)
Georgios Piliouras (Singapore University of Technology and Design)Dynamical Systems and Learning in Games (Part I)
Georgios Piliouras (Singapore University of Technology and Design)
Econometrics in Games and Auctions (Part I)
Vasilis Syrgkanis (Microsoft Research)This short course will review recent advances in econometric theory for datasets that stem from the strategic interaction of participants in a game theoretic scenario. The course will cover basics of identification and estimation strategies for structural parameters of game theoretic models in settings like market entry games, dynamic games and auctions. In the first part, I will review basic econometric theory and in particular large sample asymptotic theory of generalized method of moment estimators and M-estimators, which forms the basis of many estimation and identification strategies proposed for game theoretic settings. I will then give an application of this theory to entry games of incomplete information. I will finish with an overview of how this approach extends to dynamic games of incomplete information. In the second part, I will analyze games of complete information and focus on the problem arising from the multiplicity of equilibria in these games, due to the unobserved heterogeneity of the participants. The latter leads to partial identification of the parameters of interest and set estimation. Finally, I will focus on econometrics of auction games and in particular estimation of the private value distribution in simple single item auctions. I will finish with a brief description of recent progress at the intersection of algorithmic game theory and econometrics.Detecting nonclassicality in restricted general probabilistic theories
Leevi Leppajarvi University of Turku
The formalism of general probabilistic theories provides a universal paradigm that is suitable for describing various physical systems including classical and quantum ones as particular cases. Contrary to the often assumed no-restriction hypothesis, the set of accessible measurements within a given theory can be limited for different reasons, and this raises a question of what restrictions on measurements are operationally relevant. We argue that all operational restrictions must be closed under simulation, where the simulation scheme involves mixing and classical post-processing of measurements. We distinguish three classes of such operational restrictions: restrictions on measurements originating from restrictions on effects; restrictions on measurements that do not restrict the set of effects in any way; and all other restrictions. As a setting to detect nonclassicality in restricted theories we consider generalizations of random access codes, an intriguing class of communication tasks that reveal an operational and quantitative difference between classical and quantum information processing. We formulate a natural generalization of them, called random access tests, which can be used to examine collective properties of collections of measurements. We show that the violation of a classical bound in a random access test is a signature of either measurement incompatibility or super information storability, and that we can use them to detect differences in different restrictions.
PSI Lecture - Condensed Matter - Lecture 9
Aaron Szasz Alphabet (United States)
Learning and Incentives (Part II)
Nika Haghtalab (UC Berkeley)Classically, the outcome of a learning algorithm is considered in isolation from the effects that it may have on the process that generates the data or the party who is interested in learning. In today's world, increasingly more people and organizations interact with learning systems, making it necessary to consider these effects. This tutorial will cover the mathematical foundation for addressing learning and learnability in the presence of economic and social forces. We will cover recent advances in the theory of machine learning and algorithmic economics. In the first half of this tutorial, we will consider strategic and adversarial interactions between learning algorithms and those affected by algorithmic actions. What makes these interactions especially powerful is that they often occur over a long-term basis and can corrupt data patterns that are essential for machine learning. In this part of the talk, we work with online decision processes (such as no-regret learning) and solution concepts (such as stackelberg and minmax equilibria) to discuss statistical and computational aspects of learning and learnability in the presence of such interactions. In the second half of the tutorial, we will consider collaborative interactions in machine learning. What makes these interactions especially beneficial is their ability to learn across multiple stakeholders' tasks. In this part of the talk, we see how online algorithms act as a medium for effective collaborations. We also discuss challenges involved in designing efficient data sharing mechanisms that fully account for learner's incentives.Learning and Incentives (Part I)
Nika Haghtalab (UC Berkeley)Classically, the outcome of a learning algorithm is considered in isolation from the effects that it may have on the process that generates the data or the party who is interested in learning. In today's world, increasingly more people and organizations interact with learning systems, making it necessary to consider these effects. This tutorial will cover the mathematical foundation for addressing learning and learnability in the presence of economic and social forces. We will cover recent advances in the theory of machine learning and algorithmic economics. In the first half of this tutorial, we will consider strategic and adversarial interactions between learning algorithms and those affected by algorithmic actions. What makes these interactions especially powerful is that they often occur over a long-term basis and can corrupt data patterns that are essential for machine learning. In this part of the talk, we work with online decision processes (such as no-regret learning) and solution concepts (such as stackelberg and minmax equilibria) to discuss statistical and computational aspects of learning and learnability in the presence of such interactions. In the second half of the tutorial, we will consider collaborative interactions in machine learning. What makes these interactions especially beneficial is their ability to learn across multiple stakeholders' tasks. In this part of the talk, we see how online algorithms act as a medium for effective collaborations. We also discuss challenges involved in designing efficient data sharing mechanisms that fully account for learner's incentives.Complexity of the python’s lunch and quantum gravity in the lab
Hrant Gharibyan Stanford University
This talk consists of two parts. At first, I will focus on geometric obstructions to decoding Hawking radiation (python’s lunch). Harlow and Hayden argued that distilling information out of Hawking radiation is computationally hard despite the fact that the quantum state of the black hole and its radiation is relatively un-complex. I will trace this computational difficulty to a geometric obstruction in the Einstein-Rosen bridge connecting the black hole and its radiation. Inspired by tensor network models, I will present a conjecture that relates the computational hardness of distilling information to geometric features of the wormhole.
Then, with the long-term goal of studying quantum gravity in the lab, I will discuss a proposal for a holographic teleportation protocol that can be readily executed in table-top experiments. This protocol exhibits similar behavior to that seen in recent traversable wormhole constructions. I will introduce the concept of "teleportation by size" to capture how the physics of operator-size growth naturally leads to information transmission. The transmission of a signal through a semi-classical holographic wormhole corresponds to a rather special property of the operator-size distribution we call "size winding".Zoom Link: https://pitp.zoom.us/j/93957279481?pwd=eGVTU1MwOGNWNkMyYlRiWGo0QnFldz09
Dynamical Systems and Learning in Games (Part IV)
Georgios Piliouras (Singapore University of Technology and Design)We examine questions in game theory and online learning from a dynamical systems perspective. Specifically, the goal of the tutorial is to establish links between typically distinct tools such as optimization theory (regret analysis), chaos theory, topology of dynamical systems and more traditional game theoretic ideas such as different classes of equilibria and Price of Anarchy. We will use these connections to elucidate recent results in the area as well as pose open questions.Dynamical Systems and Learning in Games (Part III)
Georgios Piliouras (Singapore University of Technology and Design)We examine questions in game theory and online learning from a dynamical systems perspective. Specifically, the goal of the tutorial is to establish links between typically distinct tools such as optimization theory (regret analysis), chaos theory, topology of dynamical systems and more traditional game theoretic ideas such as different classes of equilibria and Price of Anarchy. We will use these connections to elucidate recent results in the area as well as pose open questions.Entropy decay for Davies semigroups of a one dimensional quantum lattice
Angela Capel Instituto de Ciencias Matemáticas (ICMAT)
The mixing time of Markovian dissipative evolutions of open quantum many-body systems can be bounded using optimal constants of certain quantum functional inequalities, such as the logarithmic Sobolev constant, which is equivalent to some form of entropy decay. For classical spin systems, the positivity of such constants follows from a mixing condition on the Gibbs measure, via quasi-factorization results for the entropy. Inspired by the classical case, we present a strategy to derive the positivity of the logarithmic Sobolev constant associated to the dynamics of certain quantum systems from some clustering conditions on the Gibbs state of a local, commuting Hamiltonian. Subsequently, we apply it to show that for a finite-range, translation-invariant commuting Hamiltonian on a spin chain, the Davies semigroup describing the reduced dynamics resulting from the joint Hamiltonian evolution of a spin chain weakly coupled to a large heat bath thermalizes rapidly at any temperature. This, in particular, rigorously establishes the absence of dissipative phase transition for Davies evolutions over translation-invariant spin chains.
Dynamical Systems and Learning in Games (Part II)
Georgios Piliouras (Singapore University of Technology and Design)We examine questions in game theory and online learning from a dynamical systems perspective. Specifically, the goal of the tutorial is to establish links between typically distinct tools such as optimization theory (regret analysis), chaos theory, topology of dynamical systems and more traditional game theoretic ideas such as different classes of equilibria and Price of Anarchy. We will use these connections to elucidate recent results in the area as well as pose open questions.Dynamical Systems and Learning in Games (Part I)
Georgios Piliouras (Singapore University of Technology and Design)We examine questions in game theory and online learning from a dynamical systems perspective. Specifically, the goal of the tutorial is to establish links between typically distinct tools such as optimization theory (regret analysis), chaos theory, topology of dynamical systems and more traditional game theoretic ideas such as different classes of equilibria and Price of Anarchy. We will use these connections to elucidate recent results in the area as well as pose open questions.