  Many learning algorithms are known to converge to an equilibrium for specific
classes of games if the same learning algorithm is adopted by all agents.
However, when the agents are self-interested, a natural question is whether
agents have a strong incentive to adopt an alternative learning algorithm that
yields them greater individual utility. We capture such incentives as an
algorithm's rationality ratio, which is the ratio of the highest payoff an
agent can obtain by deviating from a learning algorithm to its payoff from
following it. We define a learning algorithm to be $c$-rational if its
rationality ratio is at most $c$ irrespective of the game. We first establish
that popular learning algorithms such as fictitious play and regret matching
are not $c$-rational for any constant $c\geq 1$. We then propose and analyze
two algorithms that are provably $1$-rational under mild assumptions, and have
the same properties as (a generalized version of) fictitious play and regret
matching, respectively, if all agents follow them. Finally, we show that if an
assumption of perfect monitoring is not satisfied, there are games for which
$c$-rational algorithms do not exist, and illustrate our results with numerical
case studies.
