Dynamic Epistemic Logic of Resource Bounded Information Mining Agents

Summary

This partial ingest is based on the extracted full PDF text. Dolgorukov, Galimullin, and Gladyshev introduce SPQ, a dynamic epistemic logic for agents that can purchase trustworthy information through semi-public group queries. Queries have agent-dependent costs, agents have budgets, group members can share resources, the query occurrence is public, and the answer is private to the querying group. The paper proves soundness, completeness, a small-model theorem, polynomial-time model checking, and decidability.

Key Claims

• Resource-bounded epistemic agents can be modeled as perfect reasoners whose access to new information is constrained by costs and budgets.
• Semi-public queries capture the case where everyone sees that a group asked a question, but only group members learn the answer.
• Group queries can pool resources: the framework chooses the cheapest group member’s access cost and distributes that cost among the group.
• Linear inequalities in the object language let agents reason about costs, budgets, and budget comparisons.
• SPQ has a complete axiomatisation, is decidable, and admits polynomial-time global model checking.

Methods / Formalism

• The language includes propositional atoms, linear inequalities over terms c_i(A) and b_i, epistemic operators K_i, common knowledge C_G, and dynamic query operators [?^A_G]phi.
• A model is

$$M=(W,({\sim }_i{)}_{i\in AG},Cost,Bdg,V),$$

where Cost assigns nonnegative query costs and Bdg assigns agent budgets at each state.

• The budget-satisfaction formula BCS(G,A) says every group member can cover their share of the minimum cost of query A.
• The updated model for [?^A_G] removes states where the budget constraint is unsatisfied, refines epistemic relations for group members according to the truth of A, and reduces group members’ budgets by the shared query cost.
• Semi-Public Query Logic records the query-update semantics and model-checking result.

Evidence / Experiments

• The paper is theoretical.
• A telescope-building example illustrates a group that can afford information jointly even though no single agent can afford it alone.
• Main formal results include soundness, completeness, non-compactness, a small-model theorem, polynomial-time model checking, and decidability of satisfiability.

Connections

• Seeds Dynamic Epistemic Logic in the wiki with an explicitly resource-bounded update model.
• Connects to Strategic Reasoning because knowledge acquisition can require coalition formation and resource sharing.
• Connects to Formal Methods through model checking and decidability.
• Pairs naturally with Galimullin2025 - Changing the Rules of the Game, which also adds dynamic updates to multi-agent formal models.

Open Questions

• The base paper handles one resource type and propositional queried formulas; richer resources and querying arbitrary formulas are left for future work.
• The model assumes trustworthy information sources and perfect logical reasoning.
• The choice of resource-sharing rule is built into the semantics but alternative rules are expressible.

Citation

Dolgorukov, V., Galimullin, R., and Gladyshev, M. (2024). Dynamic Epistemic Logic of Resource Bounded Information Mining Agents. AAMAS 2024 extended version, arXiv:2401.13369v1.