126 CHAPTER 5 Partially Distributed Learning Algorithms and affects what has to be learned by every other player over time. In many network- ing and communication scenarios, the above information and behavior assumptions regarding the other players may not hold or require a central authority or a coordina- tor. We will see now these assumptions can be relaxed. In particular, we will study the case where players can adjust their behavior only in response to their own realized utilities; they have no knowledge of the overall structure of the game, the number of players that interact can be random, they may not observe the actions or utilities of the other players, they occasionally make mistakes on their choices and readapt by experience. In situations such as wireless communications, it may be desirable to have a learning procedure that does not require any information about the other play- ers actions or utilities, and as little memory (small number of parameters in terms of past own-actions and past own-utilities) as possible. Such a rule is said to be uncou- pled or fully distributed. It has been shown in Hart and Mas-Colell (2003) that for a broad class of games, there is no general algorithm which would allow the play- ers' period-by-period behavior to converge to a Nash equilibrium 2 . Therefore, there is no guarantee for uncoupled dynamics that behaviors will approach Nash equilib- rium most of the time. The publications (Foster and Vohra, 1997; Hart and Mas-Colell, 2000) show that regret-minimizing procedures can cause the empirical frequency dis-