We introduce a very complex game based on an approximate solution of a NP-hard problem, so that the probability of victory grows monotonically, but of an unknown amount, with the resources each player employs. We formulate this model in the computational learning framework and focus on the problem of computing a confidence interval for the losing probability. We deal with the problem of reducing the width of this interval under a given threshold in both batch and on-line modality. While the former leads to a feasible polynomial complexity, the on-line learning strategy may get stuck in an indeterminacy trap: the more we play the game the broader becomes the confidence interval. In order to avoid this indeterminacy we organise in a better way the knowledge, introducing the notion of virtual game to achieve the goal efficiently. Then we extend the one-player to a team mode game. Namely, we improve the success of a team by redistributing the resources among the players and exploiting their mutual cooperation to treat the indeterminacy phenomenon suitably.
Cooperative games in a stochastic environment / B. Apolloni, S. Bassis, S. Gaito, D. Malchiodi - In: Neural nets : 14th Italian Workshop on Neural Nets, WIRN VIETRI 2003, Vietri sul Mare, Italy, June 4 - 7, 2003; proceedings / [a cura di] B. Apolloni, M. Marinaro and R. Tagliaferri. - Berlin : Springer, 2003. - ISBN 978-3-540-20227-1. - pp. 25-34 (( convegno 14th Italian Workshop on Neural Nets, WIRN 2003.
|Titolo:||Cooperative games in a stochastic environment|
APOLLONI, BRUNO (Primo)
BASSIS, SIMONE (Secondo)
GAITO, SABRINA TIZIANA (Penultimo)
MALCHIODI, DARIO (Ultimo)
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2003|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1007/b13826|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|