Knowledge, probability, and adversaries

ABSTRACT

What should it mean for an agent to know or believe an assertion is true with probability 9.99? Different papers [2, 6, 15] give different answers, choosing to use quite different probability spaces when computing the probability that an agent assigns to an event. We show that each choice can be understood in terms of a betting game. This betting game itself can be understood in terms of three types of adversaries influencing three different aspects of the game. The first selects the outcome of all nondeterministic choices in the system; the second represents the knowledge of the agent's opponent in the betting game (this is the key place the papers mentioned above differ); and the third is needed in asynchronous systems to choose the time the bet is placed. We illustrate the need for considering all three types of adversaries with a number of examples. Given a class of adversaries, we show how to assign probability spaces to agents in a way most appropriate for that class, where “most appropriate” is made precise in terms of this betting game. We conclude by showing how different assignments of probability spaces (corresponding to different opponents) yield different levels of guarantees in probabilistic coordinated attack.

REFERENCES

• 1: ~AUMANN, R.J. Agreeing to disagrec. Anm Star. 4, 6 (1976), 1236-1239.
• 1a: ~Blackwell. D., and Girshick, M.A. Theory of Games and Statistical Decistons. Wiley, New ~York, 1954.
• 2: Ronald Fagin , Joseph Y. Halpern, Reasoning about Knowledge and Probability, Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, p.277-293, March 01, 1988
• 3: Ronald Fagin , Joseph Y. Halpern, Uncertainty, belief, and probability, Computational Intelligence, v.7 n.3, p.160-173, Aug. 1991 [doi>10.1111/j.1467-8640.1991.tb00391.x]
• 4: R. Fagin , Joseph Y. Halpern , Nimrod Megiddo, A logic for reasoning about probabilities, Information and Computation, v.87 n.1-2, p.78-128, July/August 1990 [doi>10.1016/0890-5401(90)90060-U]
• 5: ~FISCHER, M. J., AND ZUCK, L D. Relative knowledge and behef (extended abstract). Tech. Rep. YALEU/DCS/TR-589. Yale Univ., New Haven, Conn., 1987.
• 6: ~FISCHER, M. J., ,AND ZUCK, L.m. Reasoning about uncertainty in fault-tolerant distributed systems. Tech. Rep. YALEU/DCS/TR-643, Yale Umv., New Haven, Conn., 1988.
• 7: ~FISCHER, M. J., AND ZUCK, L.D. Uncertain knowledge in distributed systems. Tech. Rep. YALEU/DCS/TR-604. Yale Univ., New Haven, Coim., 1988.
• 8: ~FREUND, J. E Puzzle or paradox'? Amer. Star. 19, 4 (1965), 29-44.
• 9: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 10: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 11: ~HALMOS, P. Measure T/woO,. Van Nostrand, 1950.
• 12: ~HALPERN, J. Y, AND FAGIN, R. Modelling knowledge and action In distributed systems. Dist. Computing3, 4 (1989), 159 179.
• 13: Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Journal of the ACM (JACM), v.37 n.3, p.549-587, July 1990 [doi>10.1145/79147.79161]
• 14: Joseph Y. Halpern , Yoram Moses, A guide to completeness and complexity for modal logics of knowledge and belief, Artificial Intelligence, v.54 n.3, p.319-379, April 1992 [doi>10.1016/0004-3702(92)90049-4]
• 15: Joseph Halpern , Yjoram Moses , Mark Tuttle, A knowledge-based analysis of zero knowledge, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.132-147, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62224]
• 16: Joseph Y. Halpern , Moshe Y. Vardi, The complexity of reasoning about knowledge and time. I. lower bounds, Journal of Computer and System Sciences, v.38 n.1, p.195-237, February 1989 [doi>10.1016/0022-0000(89)90039-1]
• 17: ~LEHMANN, D., .AND SIlEI,kH, S. Reasoning about time and chance, lnf Contr. 53 (1982), 165 198.
• 18: ~LEkVIS, D. A subjectivist's guide to objective chance. In Ifs' (W L. Harper, R Stalnaker, and G. Pearce, eds.). Reldel, Dordrecht, Netherlands, 1980, pp. 267-297.
• 19: ~PAC;ELS, H.R. The Cosmic Code.' Quantum Mechanics' as the Language of Nature. Simon and Schuster, New' York, 1982.
• 20: Praskash Panangaden , Kim Taylor, Concurrent common knowledge: a new definition of agreement for asynchronous systems, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.197-209, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62579]
• 21: ~RABIN, M.O. Probabdistic algorithm for testing pnmality. J. Number of Theory 12 (198(/) 128 138.
• 22: RABIN, M.O. N-process mutual exclusion with bounded waiting by 4 - log revalued shared variable..1. Comput. Syst. Scz 25, 1 (1982), 66-75.
• 23: Sn,XI:ER, G. Conditional probability. Int. Stat. Rec. 53, 3 (1985), 261-277
• 24: SOLOVAS, R., AND STRASSEN, V. A fast Monte Carlo test for primality. SLqM J. Computing 6, 1 (1977), 84-85.
• 25: ~V4N FR,X~XSSEN, B. C. A temporal framework for conditionals and chance. In IJs (W. L. ~Harper, R. Stalnaker, and G. Pearce, eds). Reidel, Dordrecht, Netherlands, 1980, pp. ~323 340.
• 26: V^Rm, M Y. Automatic verification of probabilistlc concurrent finite-state programs. In Proceedings of the 20th IEEE 5)'mpostum on Foundatzons' of Com?uter Science. iEEE, New York, 1985, pp 327 388.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.4 Performance Analysis and Design Aids**
          Subjects: Verification**; Formal models**

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Theory, Verification

Keywords:
Byzantine generals problem, coordinated attack problem, game theory, knowledge, probabilistic knowledge, probability