טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentZamir Nitzan
SubjectBelief Requirements in Probabilistic Systems
DepartmentDepartment of Computer Science
Supervisor Professor Yoram Moses


Abstract

Reasoning about the relation between actions and knowledge in distributed systems has been of interest in the last decades. A recent novel work has established the connection between actions and knowledge of agents for protocols that are required to meet deterministic requirements.


Probabilistic distributed systems are of interest in a wide range of settings. Probabilistic protocols are used to facilitate symmetry breaking, load balancing and fault-tolerance. Participants in interactive proofs, and more generally in cryptography, typically follow probabilistic protocols. Similarly, in many competitive settings such as games, auctions and economic settings, agents follow probabilistic strategies which give rise to probabilistic systems.


Whereas deterministic protocols are typically guaranteed to obtain particular deterministic goals of interest, probabilistic protocols typically provide only probabilistic guarantees.

Thus, for protocols that provide probabilistic guarantees, the connection between actions and local information of an agent loosens.

This thesis initiates 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 i need not believe that C 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 C. Indeed, if the threshold of the probabilistic constraint is 1-a2 for some small value of a, then with probability 1-a, when the agent acts it will assign a probabilistic belief no smaller than 1-a to the possibility that C holds.

In other words, viewing strong belief as, intuitively, approximate knowledge, i must probably approximately know (PAK-know) that C is true when it acts.