More Like this

1. Sequential language-based decisions

   A. Bjorndahl ; J. Y. Halpern ( June 2023 , Proceedings of Nineteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK))

   In earlier work, we introduced the framework of language-based decisions, the core idea of which was to modify Savage's classical decision-theoretic framework by taking actions to be descriptions in some language, rather than functions from states to outcomes, as they are defined classically. Actions had the form ``if psi then do phi''', where psi and phi$ were formulas in some underlying language, specifying what effects would be brought about under what circumstances. The earlier work allowed only one-step actions. But, in practice, plans are typically composed of a sequence of steps. Here, we extend the earlier framework to \emph{sequential} actions, making it much more broadly applicable. Our technical contribution is a representation theorem in the classical spirit: agents whose preferences over actions satisfy certain constraints can be modeled as if they are expected utility maximizers. As in the earlier work, due to the language-based specification of the actions, the representation theorem requires a construction not only of the probability and utility functions representing the agent's beliefs and preferences, but also the state and outcomes spaces over which these are defined, as well as a ``selection function'' which intuitively captures how agents disambiguate coarse descriptions. The (unbounded) depth of action sequencingmore »adds substantial interest (and complexity!) to the proof.« less
2. Scalable Decision-Theoretic Planning in Open and Typed Multiagent Systems

   https://doi.org/10.1609/aaai.v34i05.6200  

   Eck, Adam ; Shah, Maulik ; Doshi, Prashant ; Soh, Leen-Kiat ( June 2020 , Proceedings of the AAAI Conference on Artificial Intelligence)

   In open agent systems, the set of agents that are cooperating or competing changes over time and in ways that are nontrivial to predict. For example, if collaborative robots were tasked with fighting wildfires, they may run out of suppressants and be temporarily unavailable to assist their peers. We consider the problem of planning in these contexts with the additional challenges that the agents are unable to communicate with each other and that there are many of them. Because an agent's optimal action depends on the actions of others, each agent must not only predict the actions of its peers, but, before that, reason whether they are even present to perform an action. Addressing openness thus requires agents to model each other's presence, which becomes computationally intractable with high numbers of agents. We present a novel, principled, and scalable method in this context that enables an agent to reason about others' presence in its shared environment and their actions. Our method extrapolates models of a few peers to the overall behavior of the many-agent system, and combines it with a generalization of Monte Carlo tree search to perform individual agent reasoning in many-agent open environments. Theoretical analyses establish the numbermore »of agents to model in order to achieve acceptable worst case bounds on extrapolation error, as well as regret bounds on the agent's utility from modeling only some neighbors. Simulations of multiagent wildfire suppression problems demonstrate our approach's efficacy compared with alternative baselines.« less
3. Language-based decisions

   Bjorndahl, A. ; Halpern, J. Y. ( June 2021 , Proceedings of Eighteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK))

   In Savage's classic decision-theoretic framework, actions are formally defined as functions from states to outcomes. But where do the state space and outcome space come from? Expanding on recent work by Blume, Easley, and Halpern [2006], we consider a language-based framework in which actions are identified with (conditional) descriptions in a simple underlying language, while states and outcomes (along with probabilities and utilities) are constructed as part of a representation theorem. Our work expands the role of language from that of Blume, Easley, and Halpern by using it not only for the conditions that determine which actions are taken, but also the effects. More precisely, we take the set of actions to be built from those of the form do(phi), for formulas phi in the underlying language. This presents a problem: how do we interpret the result of do(phi) when phi is underspecified (i.e., compatible with multiple states)? We answer this using tools familiar from the semantics of counterfactuals; roughly speaking, do(phi) maps each state to the ``closest'' phi-state. This notion of ``closest'' is also something we construct as part of the representation theorem; in effect, then, we prove that (under appropriate assumptions) the agent is acting as if eachmore »underspecified action is first made definite and then evaluated (i.e., by maximizing expected utility). Of course, actions in the real world are often not presented in a fully precise manner, yet agents reason about and form preferences among them all the same. Our work brings the abstract tools of decision theory into closer contact with such real-world scenarios.« less
4. Decision-Theoretic Planning with Communication in Open Multiagent Systems

   Kakarlapudi, Anirudh ; Anil, Gayathri ; Eck, Adam ; Doshi, Prashant ; Soh, Leen-Kiat ( August 2022 , Uncertainty in artificial intelligence)

   In open multiagent systems, the set of agents operating in the environment changes over time and in ways that are nontrivial to predict. For example, if collaborative robots were tasked with fighting wildfires, they may run out of suppressants and be temporarily unavailable to assist their peers. Because an agent's optimal action depends on the actions of others, each agent must not only predict the actions of its peers, but, before that, reason whether they are even present to perform an action. Addressing openness thus requires agents to model each other’s presence, which can be enhanced through agents communicating about their presence in the environment. At the same time, communicative acts can also incur costs (e.g., consuming limited bandwidth), and thus an agent must tradeoff the benefits of enhanced coordination with the costs of communication. We present a new principled, decision-theoretic method in the context provided by the recent communicative interactive POMDP framework for planning in open agent settings that balances this tradeoff. Simulations of multiagent wildfire suppression problems demonstrate how communication can improve planning in open agent environments, as well as how agents tradeoff the benefits and costs of communication under different scenarios.
5. Interaction Mechanisms on Facebook Dynamics Using a Common Knowledge Model

   https://doi.org/10.1007/978-3-030-65347-7_33  

   Kuhlman, C.J. ; Korkmaz, G. ; Ravi, S.S. ; Vega-Redondo, F. ( December 2020 , Complex Networks & Their Applications)

   Web-based interactions allow agents to coordinate and to take actions (change state) jointly, i.e., to participate in collective action such as a protest, facilitating spread of contagion to large groups within networked populations. In game theoretic contexts, coordination requires that agents share common knowledge about each other. Common knowledge emerges within a group when each member knows the states and the types (preferences) of the other members, and critically, each member knows that everyone else has this information. Hence, these models of common knowledge and coordination on communication networks are fundamentally different from influence-based unilateral contagion models, such as those devised by Granovetter and Centola. Common knowledge arises in many settings in practice, yet there are few operational models that can be used to compute contagion dynamics. Moreover, these models utilize different mechanisms for driving contagion. We evaluate the three mechanisms of a common knowledge model that can represent web-based communication among groups of people on Facebook. We evaluate these mechanisms on five social (media) networks with wide-ranging properties. We demonstrate that different mechanisms can produce widely varying behaviors in terms of the extent of contagion spreading and the speed of contagion transmission.