Technical Report MSC-2019-24

Title: Belief Requirements in Probabilistic Systems
Authors: Nitzan Zamir
Supervisors: Yoram Moses
PDFCurrently accessibly only within the Technion network
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−a^2$ 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.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2019
To the main CS technical reports page

Computer science department, Technion