Rational Competitive Analysis
  Much work in computer science has adopted competitive analysis as a tool for
decision making under uncertainty. In this work we extend competitive analysis
to the context of multi-agent systems. Unlike classical competitive analysis
where the behavior of an agent's environment is taken to be arbitrary, we
consider the case where an agent's environment consists of other agents. These
agents will usually obey some (minimal) rationality constraints. This leads to
the definition of rational competitive analysis. We introduce the concept of
rational competitive analysis, and initiate the study of competitive analysis
for multi-agent systems. We also discuss the application of rational
competitive analysis to the context of bidding games, as well as to the
classical one-way trading problem.
