Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.jcss.2004.10.014
Title: On learning to coordinate: Random bits help, insightful normal forms, and competency isomorphisms
Authors: Case, J.
Jain, S. 
Montagna, F.
Simi, G.
Sorbi, A.
Keywords: Coordination
Learning
Probabilistic machines
Issue Date: 2005
Source: 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 (3) : 308-332. ScholarBank@NUS Repository. https://doi.org/10.1016/j.jcss.2004.10.014
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 compared 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. © 2004 Elsevier Inc. All rights reserved.
Source Title: Journal of Computer and System Sciences
URI: http://scholarbank.nus.edu.sg/handle/10635/41122
ISSN: 00220000
DOI: 10.1016/j.jcss.2004.10.014
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

2
checked on Jan 17, 2018

WEB OF SCIENCETM
Citations

3
checked on Nov 20, 2017

Page view(s)

52
checked on Jan 14, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.