Iterated Regret Minimization: A More Realistic Solution Concept (2008)
Halpern, Joseph Y., Pass, Rafael
For some well-known games, such as the Traveler's Dilemma or the Centipede Game, traditional game-theoretic solution concepts--and most notably Nash equilibrium--predict outcomes that are not...
Toward Expressive and Scalable Sponsored Search Auctions (2008)
Martin, David J., Gehrke, Johannes, Halpern, Joseph Y.
Internet search results are a growing and highly profitable advertising platform. Search providers auction advertising slots to advertisers on their search result pages. Due to the high volume of...
Game Theory with Costly Computation (2008)
Halpern, Joseph Y., Pass, Rafael
We develop a general game-theoretic framework for reasoning about strategic agents performing possibly costly computation. In this framework, many traditional game-theoretic results (such as the...
Abraham, Ittai, Dolev, Danny, Halpern, Joseph Y.
Consider an asynchronous system with private channels and $n$ processes, up to $t$ of which may be faulty. We settle a longstanding open question by providing a Byzantine agreement protocol that...
A Formal Foundation for XrML (2008)
Halpern, Joseph Y., Weissman, Vicky
XrML is becoming a popular language in industry for writing software licenses. The semantics for XrML is implicitly given by an algorithm that determines if a permission follows from a set of...
Beyond Nash Equilibrium: Solution Concepts for the 21st Century (2008)
Nash equilibrium is the most commonly-used notion of equilibrium in game theory. However, it suffers from numerous problems. Some are well known in the game theory community; for example, the Nash...
Defaults and Normality in Causal Structures (2008)
A serious defect with the Halpern-Pearl (HP) definition of causality is repaired by combining a theory of causality with a theory of defaults. In addition, it is shown that (despite a claim to the...
Kash, Ian A., Friedman, Eric J., Halpern, Joseph Y.
Many protocols for distributed and peer-to-peer systems have the feature that nodes will stop providing service for others once they have received a certain amount of service. Examples include...
A first-order conditional logic is considered, with semantics given by a variant of epsilon-semantics, where p -> q means that Pr(q | p) approaches 1 super-polynomially --faster than any inverse...
Lotem, Arnon, Halpern, Joseph Y.
A data-driven model of learning is proposed, where a network of nodes and links is constructed that represents what has been heard and observed. Autism is viewed as the consequence of a disorder in...
Lotem, Arnon, Halpern, Joseph Y.
A data-driven model of learning is proposed, where a network of nodes and links is constructed that represents what has been heard and observed. Autism is viewed as the consequence of a disorder in...
A Game-Theoretic Analysis of Updating Sets of Probabilities (2007)
Grunwald, Peter D., Halpern, Joseph Y.
We consider how an agent should update her uncertainty when it is represented by a set $\P$ of probability distributions and the agent observes that a random variable $X$ takes on value $x$, given...
A Knowledge-Based Analysis of Global Function Computation (2007)
Halpern, Joseph Y., Petride, Sabina
Consider a distributed system N in which each agent has an input value and each communication link has a weight. Given a global function, that is, a function f whose value depends on the whole...
Generalized Solution Concepts in Games with Possibly Unaware Players (2007)
Rego, Leandro C., Halpern, Joseph Y.
Most work in game theory assumes that players are perfect reasoners and have common knowledge of all significant aspects of the game. In earlier work, we proposed a framework for representing and...
Efficiency and Nash Equilibria in a Scrip System for P2P Networks (2007)
Friedman, Eric J., Halpern, Joseph Y., Kash, Ian
A model of providing service in a P2P network is analyzed. It is shown that by adding a scrip system, a mechanism that admits a reasonable Nash equilibrium that reduces free riding can be obtained....
Optimizing Scrip Systems: Efficiency, Crashes, Hoarders, and Altruists (2007)
Kash, Ian A., Friedman, Eric J., Halpern, Joseph Y.
We discuss the design of efficient scrip systems and develop tools for empirically analyzing them. For those interested in the empirical study of scrip systems, we demonstrate how characteristics of...
Worst-Case Background Knowledge for Privacy-Preserving Data Publishing (2007)
Martin, David J., Kifer, Daniel, Machanavajjhala, Ashwin, Gehrke, Johannes, Halpern, Joseph Y.
Recent work has shown the necessity of considering an attacker's background knowledge when reasoning about privacy in data publishing. However, in practice, the data publisher does not know what...
Lower Bounds on Implementing Robust and Resilient Mediators (2007)
Abraham, Ittai, Dolev, Danny, Halpern, Joseph Y.
We consider games that have (k,t)-robust equilibria when played with a mediator, where an equilibrium is (k,t)-robust if it tolerates deviations by coalitions of size up to k and deviations by up to...
Extensive Games with Possibly Unaware Players (2007)
Halpern, Joseph Y., Rêgo, Leandro C.
Standard game theory assumes that the structure of the game is common knowledge among players. We relax this assumption by considering extensive games where agents may be unaware of the complete...
Computer Science and Game Theory: A Brief Survey (2007)
There has been a remarkable increase in work at the interface of computer science and game theory in the past decade. In this article I survey some of the main themes of work in the area, with a...
Dealing With Logical Omniscience: Expressiveness and Pragmatics (2007)
Halpern, Joseph Y., Pucella, Riccardo
We examine four approaches for dealing with the logical omniscience problem and their potential applicability: the syntactic approach, awareness, algorithmic knowledge, and impossible possible...
Characterizing Solution Concepts in Games Using Knowledge-Based Programs (2006)
Halpern, Joseph Y., Moses, Yoram
We show how solution concepts in games such as Nash equilibrium, correlated equilibrium, rationalizability, and sequential equilibrium can be given a uniform definition in terms of...
Rational Secret Sharing and Multiparty Computation: Extended Abstract (2006)
Halpern, Joseph Y., Teague, Vanessa
We consider the problems of secret sharing and multiparty computation, assuming that agents prefer to get the secret (resp., function value) to not getting it, and secondarily, prefer that as few as...
Using Sets of Probability Measures to Represent Uncertainty (2006)
I explore the use of sets of probability measures as a representation of uncertainty.
Expressing Security Properties Using Selective Interleaving Functions (2006)
Halpern, Joseph Y., Petride, Sabina
McLean's notion of Selective Interleaving Functions (SIFs) is perhaps the best-known attempt to construct a framework for expressing various security properties. We examine the expressive power of...
Modeling Adversaries in a Logic for Security Protocol Analysis (2006)
Halpern, Joseph Y., Pucella, Riccardo
Logics for security protocol analysis require the formalization of an adversary model that specifies the capabilities of adversaries. A common model is the Dolev-Yao model, which considers only...
Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic (2006)
Halpern, Joseph Y., Rego, Leandro Chaves
There has been a great of work on characterizing the complexity of the satisfiability and validity problem for modal logics. In particular, Ladner showed that the validity problem for all logics...
Reasoning About Knowledge of Unawareness (2006)
Halpern, Joseph Y., Rego, Leandro Chaves
Awareness has been shown to be a useful addition to standard epistemic logic for many applications. However, standard propositional logics for knowledge and awareness cannot express the fact that an...
Using First-Order Logic to Reason about Policies (2006)
Halpern, Joseph Y., Weissman, Vicky
A policy describes the conditions under which an action is permitted or forbidden. We show that a fragment of (multi-sorted) first-order logic can be used to represent and reason about policies....
Evidence with Uncertain Likelihoods (2005)
Halpern, Joseph Y., Pucella, Riccardo
An agent often has a number of hypotheses, and must choose among them based on observations, or outcomes of experiments. Each of these observations can be viewed as providing evidence for or against...
When Ignorance is Bliss (2005)
Grunwald, Peter D., Halpern, Joseph Y.
It is commonly-accepted wisdom that more information is better, and that information should never be ignored. Here we argue, using both a Bayesian and a non-Bayesian analysis, that in some situations...
Interactive Unawareness Revisited (2005)
Halpern, Joseph Y., Rego, Leandro C.
We analyze a model of interactive unawareness introduced by Heifetz, Meier and Schipper (HMS). We consider two axiomatizations for their model, which capture different notions of validity. These...
Probabilistic Algorithmic Knowledge (2005)
Halpern, Joseph Y., Pucella, Riccardo
The framework of algorithmic knowledge assumes that agents use deterministic knowledge algorithms to compute the facts they explicitly know. We extend the framework to allow for randomized knowledge...
Intransitivity and Vagueness (2004)
There are many examples in the literature that suggest that indistinguishability is intransitive, despite the fact that the indistinguishability relation is typically taken to be an equivalence...
Sleeping Beauty Reconsidered: Conditioning and Reflection in Asynchronous Systems (2004)
A careful analysis of conditioning in the Sleeping Beauty problem is done, using the formal model for reasoning about knowledge and probability developed by Halpern and Tuttle. While the Sleeping...
A Logic for Reasoning about Evidence (2004)
Halpern, Joseph Y., Pucella, Riccardo
We introduce a logic for reasoning about evidence that essentially views evidence as a function from prior beliefs (before making an observation) to posterior beliefs (after making the observation)....
When Ignorance is Bliss (2004)
It is commonly-accepted wisdom that more information is better, and that information should never be ignored. Here we argue, using both a Bayesian and a non-Bayesian analysis, that in some situations...
Joseph Y. Halpern, Daphne Koller
Non-deductive reasoning systems are often representation dependent: representing the same situation in two di#erent ways may cause such a system to return two di#erent answers.
Anonymity and Information Hiding in Multiagent Systems (2004)
Halpern, Joseph Y., O'Neill, Kevin R.
We provide a framework for reasoning about information-hiding requirements in multiagent systems and for reasoning about anonymity in particular. Our framework employs the modal logic of knowledge...
Knowledge-Based Sythesis of Distributed Systems Using Event Structures (2004)
Bickford, Mark, Constable, Robert C., Halpern, Joseph Y., Petride, Sabina
To produce a program guaranteed to satisfy a given specification one can synthesize it from a formal constructive proof that a computation satisfying that specification exists. This process is...
Knowledge-Based Sythesis of Distributed Systems Using Event Structures (2004)
Bickford, Mark, Constable, Robert C., Halpern, Joseph Y., Petride, Sabina
To produce a program guaranteed to satisfy a given specification one can synthesize it from a formal constructive proof that a computation satisfying that specification exists. This process is...
A Knowledge-Theoretic Analysis of Uniform Distributed Coordination and Failure Detectors (2004)
Halpern, Joseph Y., Ricciardi, Aleta
It is shown that, in a precise sense, if there is no bound on the number of faulty processes in a system with unreliable but fair communication, Uniform Distributed Coordination (UDC) can be attained...
Complete Axiomatizations For Reasoning About (2004)
Joseph Y. Halpern, Ron Van, Der Meyden, Y. Vardi
Sound and complete axiomatizations are provided for a number of di#erent logics involving modalities for knowledge and time. These logics arise from di#erent choices for various parameters regarding...
Representation Dependence in Probabilistic Inference (2003)
Halpern, Joseph Y., Koller, Daphne
Non-deductive reasoning systems are often {\em representation dependent}: representing the same situation in two different ways may cause such a system to return two different answers. Some have...
What Causes a System to Satisfy a Specification? (2003)
Chockler, Hana, Halpern, Joseph Y., Kupferman, Orna
Even when a system is proven to be correct with respect to a specification, there is still a question of how complete the specification is, and whether it really covers all the behaviors of the...
Characterizing and Reasoning about Probabilistic and Non-Probabilistic Expectation (2003)
Halpern, Joseph Y., Pucella, Riccardo
Expectation is a central notion in probability theory. The notion of expectation also makes sense for other notions of uncertainty. We introduce a propositional logic for reasoning about expectation,...
Responsibility and blame: a structural-model approach (2003)
Chockler, Hana, Halpern, Joseph Y.
Causality is typically treated an all-or-nothing concept; either A is a cause of B or it is not. We extend the definition of causality introduced by Halpern and Pearl [2001] to take into account the...
What is an Inference Rule? (2003)
Ronald Fagin, Joseph Y. Halpern, Moshe Y. Vardi
What is an inference rule? This question does not have a unique answer. One usually nds two distinct standard answers in the literature: validity inference ( ` v ' if for every substitution , the...
Levesque's Axiomatization of Only Knowing is (2003)
Joseph Y. Halpern, Gerhard Lakemeyer
We show that the axiomatization given by Levesque for his logic of "only knowing" (Levesque 1990), which he showed to be sound and complete for the unquantified version of the logic and conjectured...
Multi-Agent Only Knowing (2003)
Joseph Y. Halpern, Gerhard Lakemeyer
Levesque introduced a notion of "only knowing", with the goal of capturing certain types of nonmonotonic reasoning. Levesque's logic dealt with only the case of a single agent. Recently, both Halpern...
Francis C. Chu, Joseph Y. Halpern
Many di#erent rules for decision making have been introduced in the literature. We show that a notion of generalized expected utility proposed in [Chu and Halpern 2003] is a universal decision rule,...
Francis C. Chu, Joseph Y. Halpern
We propose a generalization of expected utility that we call generalized EU (GEU), where a decision maker's beliefs are represented by plausibility measures and the decision maker's tastes are...
Great Expectations. Part I: On the Customizability of Generalized Expected Utility (2003)
Chu, Francis C., Halpern, Joseph Y.
We propose a generalization of expected utility that we call generalized EU (GEU), where a decision maker's beliefs are represented by plausibility measures, and the decision maker's tastes are...
Great Expectations. Part II: Generalized Expected Utility as a Universal Decision Rule (2003)
Chu, Francis C., Halpern, Joseph Y.
Many different rules for decision making have been introduced in the literature. We show that a notion of generalized expected utility proposed in Part I of this paper is a universal decision rule,...
Using Counterfactuals in Knowledge-Based Programming (2003)
Halpern, Joseph Y., Moses, Yoram
This paper adds counterfactuals to the framework of knowledge-based programs of Fagin, Halpern, Moses, and Vardi. The use of counterfactuals is illustrated by designing a protocol in which an agent...
Responsibility and Blame: A Structural-Model (2003)
Hana Chockler, Joseph Y. Halpern
Causality is typically treated an all-or-nothing concept; either A is a cause of B or it is not. We extend the definition of causality introduced by Halpern and Pearl [2001a] to take into account the...
Peter D. Grunwald, Joseph Y. Halpern
As examples such as the Monty Hall puzzle show, applying conditioning to update a probability distribution on a "naive space", which does not take into account the protocol used, can often lead to...
Analysis of a Cone-Based Distributed Topology Control (2003)
Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-min Wang, Roger Wattenhofer
The topology of a wireless multi-hop network can be controlled byvarying the transmission power at eachnode. In this paper, we give a detailed analysis of a cone-based distributed topology control...
Minimum-Energy Mobile Wireless Networks Revisited (2003)
We propose a protocol that, given a communication network, computes a subnetwork such that, for every pair (u, v) of nodes connected in the original network, there is a a minimum-energy path between...
Gossip-Based Ad Hoc Routing (2003)
Zygmunt J. Haas, Joseph Y. Halpern, Li Li
Many ad hoc routing protocols are based on some variant of flooding. Despite various optimizations, many routing messages are propagated unnecessarily. We propose a gossiping-based approach, where...
A Decision-Theoretic Approach to Resource Allocation in Wireless Multimedia Networks (2003)
Zygmunt Haas, Joseph Y. Halpern, Li Li, Stephen B. Wicker
The allocation of scarce spectral resources to support as many user applications as possible while maintaining reasonable quality of service is a fundamental problem in wireless communication. We...
Peter D. Grunwald, Joseph Y. Halpern
As examples such as the Monty Hall puzzle show, applying conditioning to update a probability distribution on a "naive space", which does not take into account the protocol used, can often lead to...
Modeling Belief in Dynamic Systems, Part I: Foundations (2003)
Friedman, Nir, Halpern, Joseph Y.
Belief change is a fundamental problem in AI: Agents constantly have to update their beliefs to accommodate new observations. In recent years, there has been much work on axiomatic characterizations...
Modeling Belief in Dynamic Systems, Part II: Revisions and Update (2003)
Friedman, Nir, Halpern, Joseph Y.
The study of belief change has been an active area in philosophy and AI. In recent years two special cases of belief change, belief revision and belief update, have been studied in detail. In a...
A logic for reasoning about upper probabilities (2003)
Halpern, Joseph Y., Pucella, Riccardo
We present a propositional logic %which can be used to reason about the uncertainty of events, where the uncertainty is modeled by a set of probability measures assigning an interval of probability...
From Statistical Knowledge Bases to Degrees of Belief (2003)
Bacchus, Fahiem, Grove, Adam, Halpern, Joseph Y., Koller, Daphne
An intelligent agent will often be uncertain about various properties of its environment, and when acting in that environment it will frequently need to quantify its uncertainty. For example, if the...
Secrecy in Multiagent Systems (2003)
O'Neill, Kevin R., Halpern, Joseph Y.
We introduce a general framework for reasoning about secrecy and privacy requirements in multiagent systems. Our definitions extend earlier definitions of secrecy and nondeducibility given by Shannon...
Grunwald, Peter D., Halpern, Joseph Y.
As examples such as the Monty Hall puzzle show, applying conditioning to update a probability distribution on a ``naive space'', which does not take into account the protocol used, can often lead to...
Using First-Order Logic to Reason about Policies (2003)
Joseph Y. Halpern, Vicky Weissman
A policy describes the conditions under which an action is permitted or forbidden. We show that a fragment of (multi-sorted) first-order logic can be used to represent and reason about policies....
Probabilistic Algorithmic Knowledge (2003)
Joseph Y. Halpern, Riccardo Pucella
The framework of algorithmic knowledge assumes that agents use deterministic knowledge algorithms to compute the facts they explicitly know. We extend the framework to allow for randomized knowledge...
A Logic for Reasoning about Evidence (2003)
Joseph Y. Halpern, Riccardo Pucella
We introduce a logic for reasoning about evidence, that essentially views evidence as a function from prior beliefs (before making an observation) to posterior beliefs (after making the observation)...
Lexicographic probability, conditional probability, and nonstandard probability (2003)
The relationship between Popper spaces (conditional probability spaces that satisfy some regularity conditions), lexicographic probability systems (LPS's), and nonstandard probability spaces (NPS's)...
On the Relationship between Strand Spaces and Multi-Agent Systems (2003)
Halpern, Joseph Y., Pucella, Riccardo
Strand spaces are a popular framework for the analysis of security protocols. Strand spaces have some similarities to a formalism used successfully to model protocols for distributed systems, namely...
Modeling Adversaries in a Logic for Security Protocol (2003)
Joseph Y. Halpern, Riccardo Pucella
Logics for security protocol analysis require the formalization of an adversary model that specifies the capabilities of adversaries. A common model is the Dolev-Yao model, which considers only...
Revisiting the Foundations of Authentication Logics (2003)
Joseph Y. Halpern, Riccardo Pucella
In this paper, we make the point that the problems with logics in the BAN tradition are not with the idea of basing reasoning about security protocols using epistemic notions, but with some of the...
The Complexity of Reasoning About Knowledge and Time: Synchronous (2002)
Joseph Y. Halpern, Moshe Y. Vardi
We study the propositional modal logic of knowledge and time for distributed systems. We consider a number of logics (ninety-six in all!), which vary according to the choice of language and the...
Analysis of a Cone-Based Distributed Topology Control (2002)
Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-min Wang, Roger Wattenhofer
The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...
P. D. Gronwald, J. Y. Halpern, Peter D. Grijnwald, Joseph Y. Halpern
As examples such as the Monty Hall puzzle show, applying conditioning to update a probability distribution on a "naive space", which does not take into account the protocol used, can often lead to...
Joseph Y. Halpern, Mosh Y. Vardi
This paper focuses on lower bounds; a sequel will deal with the corresponding upper bounds. Typical results include a lCl[-completeness result for the language with common knowledge with respect to...
Peter D. Grunwald, Joseph Y. Halpern
As examples such as the Monty Hall puzzle show, applying conditioning to update a probability distribution on a "naive space", which does not take into account the protocol used, can often lead to...
Gossip Based Ad-Hoc Routing (2002)
Haas, Zygmunt, Halpern, Joseph Y., Li, Erran L.
Many ad hoc routing protocols are based on some variant of flooding. Despite various optimizations, many routing messages are propagated unnecessarily. We propose a gossiping-based approach, where...
Minimum-Energy Mobile Wireless Networks Revisited (2002)
Li, Erran L., Halpern, Joseph Y.
We propose a protocol that, given a communication network, computes a subnetwork such that, for every pair $(u,v)$ of nodes connected in the original network, there is a minimum-energy path between...
Li, Erran L., Halpern, Joseph Y., Bahl, Paramvir, Wang, Yi-Min, Wattenhofer, Roger
The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...
Joseph Y. Halpern, Riccardo Pucella
We present a propositional logic to reason about the uncertainty of events, where the uncertainty is modeled by a set of probability measures assigning an interval of probability to each event. We...
On the Relationship between Strand Spaces and (2002)
Joseph Y. Halpern, Riccardo Pucella
this paper appears in the Proceedings of the 8th ACM Conference on Computer and Communications Security, 2001. Supported in part by NSF under grant IRI96 -25901 and IIS-0090145 and by ONR under...
Reasoning about Expectation (2002)
Joseph Y. Halpern, Riccardo Pucella
Expectation is a central notion in probability theory.
Gossip-Based Ad Hoc Routing (2002)
Zygmunt J. Haas, Joseph Y. Halpern, Li Li
Many ad hoc routing protocols are based on some variant of flooding. Despite various optimizations, many routing messages are propagated unnecessarily. We propose a gossiping-based approach, where...
Joseph Y. Halpern, Riccardo Pucella
We present a propositional logic to reason about the uncertainty of events, where the uncertainty is modeled by a set of probability measures assigning an interval of probability to each event. We...