๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Inclusion Problems in Parallel Learning and Games

โœ Scribed by Martin Kummer; Frank Stephan

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
840 KB
Volume
52
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis

In a recent paper Kinber, Smith, Velauthapillai, and Wiehagen introduced a new notion of parallel learning.'' They call a set S of functions (m, n)-learnable if there is a learning machine which for any n-tuple of pairwise distinct functions from S learns at least m functions correctly from examples of their behavior after seeing some finite amount of input. One of the basic open questions in this area is the inclusion problem,'' i.e., the question for which m, n, h, k, every (m, n)-learnable class is also (h, k)-learnable. In this paper we develop a general approach to solve this problem. The idea is to associate with each m, n, h, k in a uniform way a finite 2-player game such that the first player has a winning strategy in this game iff every (m, n)-learnable class is (h, k)-learnable. In this way we take the recursion theoretic disguise off the problem and isolate its combinatorial core. We also explicitly characterize the ``strength'' of each particular noninclusion by the complexity of an oracle which is needed to overcome it. It turns out that there are exactly three different types of noninclusions.

๐Ÿ“œ SIMILAR VOLUMES

Learning and decision costs in one-perso
Learning and decision costs in one-person games
โœ Charles Romeo; Barry Sopher ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 227 KB ๐Ÿ‘ 1 views

This paper reports the results of a two-part data analysis of learning in a repeated costly decision experiment. In the ยฎrst part we test payo dominance under the hypothesis of expected payo maximization. We utilize a dynamic probability distribution over decisions for each player, characterizing wh

Learning and communication in sender-rec
Learning and communication in sender-receiver games: an econometric investigation
โœ Andreas Blume; Douglas V. DeJong; George R. Neumann; N. E. Savin ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 388 KB

## Abstract This paper compares stimulus response (SR) and beliefโ€based learning (BBL) using data from experiments with senderโ€“receiver games. The environment, extensive form games played in a population setting, is novel in the empirical literature on learning in games. Both the SR and BBL models