The Taub Faculty of Computer Science Events and Talks

Whereas deterministic protocols are typically guaranteed to obtain particular goals of interest, probabilistic protocols typically provide only probabilistic guarantees. In this talk we initiate an investigation of the interdependence between actions and subjective beliefs of agents in a probabilistic setting. In particular, we study what probabilistic beliefs an agent should have when performing actions, in a protocol that must satisfy a given probabilistic constraint. It is shown that the agent need not believe that a fact f is true with probability at least x on any nontrivial measure of the cases. Our main result is that, in expectation, it should have sufficiently high beliefs in f. Indeed, if x is (1-epsilon^2) for some small value of epsilon then with probability (1-epsilon), when the agent acts it will assign a probabilistic belief no smaller than (1-epsilon) to the possibility that f holds. In other words, the agent must PROBABLY STRONGLY BELIEVE that f is true.