Philosophy Faculty Database
Philosophy
Arts & Sciences
Duke University

 HOME > Arts & Sciences > Philosophy > Faculty    Search Help Login pdf version printable version 

Publications [#236214] of Vincent Conitzer

Duke :: Philosophy :: Faculty :: Vincent Conitzer

Journal articles or Book chapters PUBLISHED

  1. Conitzer, V; Sandholm, T, Communication complexity as a lower bound for learning in games, Proceedings, Twenty-First International Conference on Machine Learning, ICML 2004 (December, 2004), pp. 185-192.
    (last updated on 2024/03/28)

    Abstract:
    A fast-growing body of research in the AI and machine learning communities addresses learning in games, where there are multiple learners with different interests. This research adds to more established research on learning in games conducted in economics. In part because of a clash of fields, there are widely varying requirements on learning algorithms in this domain. The goal of this paper is to demonstrate how communication complexity can be used as a lower bound on the required learning time or cost. Because this lower bound does not assume any requirements on the learning algorithm, it is universal, applying under any set of requirements on the learning algorithm. We characterize exactly the communication complexity of various solution concepts from game theory, namely Nash equilibrium, iterated dominant strategies (both strict and weak), and backwards induction. This gives the tighest lower bounds on learning in games that can be obtained with this method.


Duke University * Arts & Sciences * Philosophy * Faculty * Staff * Grad * Reload * Login