Team learning as a game

A FIN-learning machine M receives successive values of the function f it is learning; at some point M outputs conjecture which should be a correct index of f. When n machines simultaneously learn the same function f and at least k of these machines output correct indices of f, we have team learning [k, n]FIN. Papers [DKV92, DK96] show that sometimes a team or a probabilistic learner can simulate another one, if its probability p (or team success ratio k/n) is close enough. On the other hand, there are critical ratios which make simulation of FIN(p2) by FIN(p1) impossible whenever p2 < r < pl for some critical ratio r. Accordingly to [DKV92] the critical ratio closest to 1/2 from the left is 24/49; [DK96] provides other unusual constants. These results are complicated and provide a full picture of comparisons only for FINlearners with success ratio above 12/25. We generalize [k, n]FIN teams to asymmetric teams [AFS97]. We introduce a two player game on two 0-1 matrices defining two asymmetric teams. The result of the game reflects the comparative power of these asymmetric teams. Hereby we show that the problem to determine whether [k_l, n_l]FIN Í [k2, n2]FIN is algorithmically solvable. We also show that the set of all critical ratios is well-ordered. Simulating asymmetric teams with probabilistic machines from [AFS97] provides some insight about the unusual constants like 24/49.