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.

Cooperative games in a stochastic environment

B. Apolloni
Primo
;
S. Bassis
Secondo
;
S. Gaito
Penultimo
;
D. Malchiodi
Ultimo
2003

Abstract

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.
Settore INF/01 - Informatica
Book Part (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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: http://hdl.handle.net/2434/56220
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact