A mere bounded number of random bits judiciously employed by a probabilistically correct algorithmic coordinator is shown to increase the power of learning to coordinate compared to deterministic algorithmic coordinators. Furthermore, these probabilistic algorithmic coordinators are provably not characterized in power by teams of deterministic ones. An insightful, enumeration technique based, normal form characterization of the classes that are learnable by total computable coordinators is given. These normal forms are for insight only since it is shown that the complexity of the normal form of a total computable coordinator can be infeasible ompared to the original coordinator. Montagna and Osherson showed that the competence class of a total coordinator cannot be strictly improved by another total coordinator. It is shown in the present paper that the competencies of any two total coordinators are the same modulo isomorphism. Furthermore, a completely effective, index set version of this competency isomorphism result is given, where all the coordinators are total computable.We also investigate the competence classes of total coordinators from the points of view of topology and descriptive set theory.

Case, J., Jain, S., Montagna, F., Simi, G., Sorbi, A. (2005). On learning to coordinate: random bits help, insightful normal forms, and competency isomorphisms. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 71, 308-332 [10.1016/j.jcss.2004.10.014].

On learning to coordinate: random bits help, insightful normal forms, and competency isomorphisms.

MONTAGNA, FRANCO;SIMI, GIULIA;SORBI, ANDREA
2005-01-01

Abstract

A mere bounded number of random bits judiciously employed by a probabilistically correct algorithmic coordinator is shown to increase the power of learning to coordinate compared to deterministic algorithmic coordinators. Furthermore, these probabilistic algorithmic coordinators are provably not characterized in power by teams of deterministic ones. An insightful, enumeration technique based, normal form characterization of the classes that are learnable by total computable coordinators is given. These normal forms are for insight only since it is shown that the complexity of the normal form of a total computable coordinator can be infeasible ompared to the original coordinator. Montagna and Osherson showed that the competence class of a total coordinator cannot be strictly improved by another total coordinator. It is shown in the present paper that the competencies of any two total coordinators are the same modulo isomorphism. Furthermore, a completely effective, index set version of this competency isomorphism result is given, where all the coordinators are total computable.We also investigate the competence classes of total coordinators from the points of view of topology and descriptive set theory.
2005
Case, J., Jain, S., Montagna, F., Simi, G., Sorbi, A. (2005). On learning to coordinate: random bits help, insightful normal forms, and competency isomorphisms. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 71, 308-332 [10.1016/j.jcss.2004.10.014].
File in questo prodotto:
File Dimensione Formato  
asprinted.pdf

non disponibili

Descrizione: Articolo unico
Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 332.29 kB
Formato Adobe PDF
332.29 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/23817