Arrow Research search

Author name cluster

Sujata Ghosh

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers
2 author rows

Possible papers

11

TARK Conference 2025 Conference Paper

Are Large Random Graphs Always Safe to Hide?

  • Sourav Chakraborty 0001
  • Sujata Ghosh
  • Smiha Samanta

We discuss winning possibilities of players in various variants of cops and robber game played on large random graphs, a testbed for various kinds of network queries, search problems in particular. We explore the use of logic frameworks to investigate such results; in particular, we show that whenever a winning condition for either player can be expressed as a certain kind of formula in first-order logic, that player almost always wins. In the process, we obtain more insight into the logic-game connection from the zero-one law perspective.

KR Conference 2025 Conference Paper

Reasoning About Knowledge on Regular Expressions Is 2EXPTIME-Complete

  • Avijeet Ghosh
  • Sujata Ghosh
  • François Schwarzentruber

Logics for reasoning about knowledge and actions have seen many applications in various domains of multi-agent systems, including epistemic planning. Change of knowledge based on observations about the surroundings forms a key aspect in such planning scenarios. Public Observation Logic (POL) is a variant of public announcement logic for reasoning about knowledge that gets updated based on public observations. Each state in an epistemic (Kripke) model is equipped with a set of expected observations. These states evolve as the expectations get matched with the actual observations. In this work, we prove that the satisfiability problem of POL is 2EXPTIME-complete.

KR Conference 2023 Conference Paper

On Simple Expectations and Observations of Intelligent Agents: A Complexity Study

  • Sourav Chakraborty
  • Avijeet Ghosh
  • Sujata Ghosh
  • François Schwarzentruber

Public observation logic (POL) reasons about agent expectations and agent observations in various real world situations. The expectations of agents take shape based on certain protocols about the world around and they remove those possible scenarios where their exceptions and observations do not match. This in turn influences the epistemic reasoning of these agents. In this work, we study the computational complexity of the satisfaction problems of various fragments of POL. In the process, we also highlight the inevitable link that these fragments have with the well-studied Public announcement logic.

IJCAI Conference 2022 Conference Paper

On Verifying Expectations and Observations of Intelligent Agents

  • Sourav Chakraborty
  • Avijeet Ghosh
  • Sujata Ghosh
  • François Schwarzentruber

Public observation logic (POL) is a variant of dynamic epistemic logic to reason about agent expectations and agent observations. Agents have certain expectations, regarding the situation at hand, that are actuated by the relevant protocols, and they eliminate possible worlds in which their expectations do not match with their observations. In this work, we investigate the computational complexity of the model checking problem for POL and prove its PSPACE-completeness. We also study various syntactic fragments of POL. We exemplify the applicability of POL model checking in verifying different characteristics and features of an interactive system with respect to the distinct expectations and (matching) observations of the system. Finally, we provide a discussion on the implementation of the model checking algorithms.

TARK Conference 2017 Conference Paper

What Drives People's Choices in Turn-Taking Games, if not Game-Theoretic Rationality?

  • Sujata Ghosh
  • Aviad Heifetz
  • Rineke Verbrugge
  • Harmen de Weerd

In an earlier experiment, participants played a perfect information game against a computer, which was programmed to deviate often from its backward induction strategy right at the beginning of the game. Participants knew that in each game, the computer was nevertheless optimizing against some belief about the participant's future strategy. In the aggregate, it appeared that participants applied forward induction. However, cardinal effects seemed to play a role as well: a number of participants might have been trying to maximize expected utility. In order to find out how people really reason in such a game, we designed centipede-like turn-taking games with new payoff structures in order to make such cardinal effects less likely. We ran a new experiment with 50 participants, based on marble drop visualizations of these revised payoff structures. After participants played 48 test games, we asked a number of questions to gauge the participants' reasoning about their own and the opponent's strategy at all decision nodes of a sample game. We also checked how the verbalized strategies fit to the actual choices they made at all their decision points in the 48 test games. Even though in the aggregate, participants in the new experiment still tend to slightly favor the forward induction choice at their first decision node, their verbalized strategies most often depend on their own attitudes towards risk and those they assign to the computer opponent, sometimes in addition to considerations about cooperativeness and competitiveness.

LORI Conference 2015 Conference Paper

A Note on Reliability-Based Preference Dynamics

  • Sujata Ghosh
  • Fernando R. Velázquez-Quesada

Abstract This paper continues a line of work that studies individual preference upgrades in order to model situations akin to a process of public deliberation in collective decision making. It proposes a general upgrade policy, presenting its semantic definition and a corresponding modality for describing its effects as well as a complete axiom system.

TARK Conference 2015 Conference Paper

Do players reason by forward induction in dynamic perfect information games?

  • Sujata Ghosh
  • Aviad Heifetz
  • Rineke Verbrugge

We conducted an experiment where participants played a perfect-information game against a computer, which was programmed to deviate often from its backward induction strategy right at the beginning of the game. Participants knew that in each game, the computer was nevertheless optimizing against some belief about the participant's future strategy. It turned out that in the aggregate, participants were likely to respond in a way which is optimal with respect to their best-rationalization extensive form rationalizability conjecture - namely the conjecture that the computer is after a larger prize than the one it has foregone, even when this necessarily meant that the computer has attributed future irrationality to the participant when the computer made the first move in the game. Thus, it appeared that participants applied forward induction. However, there exist alternative explanations for the choices of most participants; for example, choices could be based on the extent of risk aversion that participants attributed to the computer in the remainder of the game, rather than to the sunk outside option that the computer has already foregone at the beginning of the game. For this reason, the results of the experiment do not yet provide conclusive evidence for Forward Induction reasoning on the part of the participants.

LORI Conference 2015 Conference Paper

Human Strategic Reasoning in Dynamic Games: Experiments, Logics, Cognitive Models

  • Sujata Ghosh
  • Tamoghna Halder
  • Khyati Sharma
  • Rineke Verbrugge

Abstract This article provides a three-way interaction between experiments, logic and cognitive modelling so as to bring out a shared perspective among these diverse areas, aiming towards better understanding and better modelling of human strategic reasoning in dynamic games.

AIJ Journal 2014 Journal Article

Hidden protocols: Modifying our expectations in an evolving world

  • Hans van Ditmarsch
  • Sujata Ghosh
  • Rineke Verbrugge
  • Yanjing Wang

When agents know a protocol, this leads them to have expectations about future observations. Agents can update their knowledge by matching their actual observations with the expected ones. They eliminate states where they do not match. In this paper, we study how agents perceive protocols that are not commonly known, and propose a semantics-driven logical framework to reason about knowledge in such scenarios. In particular, we introduce the notion of epistemic expectation models and a propositional dynamic logic-style epistemic logic for reasoning about knowledge via matching agentsʼ expectations to their observations. It is shown how epistemic expectation models can be obtained from epistemic protocols. Furthermore, a characterization is presented of the effective equivalence of epistemic protocols. We introduce a new logic that incorporates updates of protocols and that can model reasoning about knowledge and observations. Finally, the framework is extended to incorporate fact-changing actions, and a worked-out example is given.

TARK Conference 2011 Conference Paper

Hidden protocols

  • Hans van Ditmarsch
  • Sujata Ghosh
  • Rineke Verbrugge
  • Yanjing Wang 0001

When agents know a protocol, this leads them to have expectations about future observations. Agents can update their knowledge by matching their actual observations with the expected ones. They eliminate states where they do not match. In this paper, we study how agents perceive protocols that are not commonly known, and propose a logic to reason about knowledge in such scenarios.

LORI Conference 2011 Conference Paper

Playing Extensive Form Negotiation Games: A Tool-Based Analysis (Abstract)

  • Sujata Ghosh
  • Sumit Sourabh
  • Rineke Verbrugge

This paper reports the development of a simple tool, NEGEXT, written in the platform-independent Java language. NEGEXT has been constructed to aid real people doing actual negotiations, when the ways to negotiate are simply too many to be computed by a normal human mind. This toolkit will also help in planning one’s strategic moves in negotiation situations when the opponents’ possible moves can be approximated. Even though some visualization tools for extensive form game trees already exist, we believe we are the first to make a tree-based negotiation toolkit that incorporates the possibility of representing learning from game to game, by sequential and parallel composition (cf. [1]). Moreover, the toolkit has a model-checking component which computes whether and how an individual or a specific coalition can achieve a given objective.

v2026.09.13