Coping with selfish on-going behaviors
======================================
A rational and selfish environment may have an incentive to cheat
the system it interacts with. Cheating the system amounts to
reporting a stream of inputs that is different from the one
corresponding to the real behavior of the environment. The system
may cope with cheating by charging penalties to cheats it detects.
In this paper, we formalize this setting by means of weighted
automata and their resilience to selfish environments. Automata have
proven to be a successful formalism for modeling the on-going
interaction between a system and its environment. In particular,
weighted finite automata (WFAs), which assign a cost to each input
word, are useful in modeling an interaction that has a quantitative
outcome. Consider a WFA $\A$ over the alphabet $\Sigma$. At each
moment in time, the environment may cheat $\A$ by reporting a letter
different from the one it actually generates. A penalty function
$\eta:\Sigma \times \Sigma \rightarrow \R^{\geq 0}$ maps each possible
false-report to a penalty, charged whenever the false-report is
detected. A detection-probability function $p:\Sigma \times \Sigma
\rightarrow [0,1]$ gives the probability of detecting each
false-report. We say that $\A$ is $(\eta,p)$-resilient to cheating
if $\zug{\eta,p}$ ensures that the minimal expected cost of an input
word is achieved with no cheating. Thus, a rational environment has
no incentive to cheat $\A$.
We study the basic problems arising in the analysis of this setting.
In particular, we consider the problem of deciding whether a given WFA
$\A$ is $(\eta,p)$-resilient with respect to a given penalty function
$\eta$ and a detection-probability function $p$; and the problem of
achieving resilience with minimum resources, namely, given $\A$ and
$\eta$, finding the minimal (with respect to
$\sum_{\s,\s'}\eta(\s,\s')\cdot p(\s,\s')$) detection-probability
function $p$, such that $\A$ is $(\eta,p)$-resilient. While for
general WFAs both problems are shown to be PSPACE-hard, we present
polynomial-time algorithms for deterministic WFAs.