wiki

Semi-Public Query Logic

2 min read

Semi-Public Query Logic

Context

Dolgorukov2024 - Dynamic Epistemic Logic of Resource Bounded Information Mining Agents introduces SPQ, a DEL-style logic for agents whose information acquisition is limited by query costs and budgets.

Formal Statement

SPQ models have the form

where W is a state set, sim_i are epistemic equivalence relations, Cost(i,w,A) is the cost of query formula A for agent i at state w, Bdg(i,w) is the budget of agent i, and V is a valuation.

The language includes:

  • knowledge K_i phi;
  • common knowledge C_G phi;
  • linear inequalities over query-cost terms c_i(A) and budget terms b_i;
  • dynamic operators [?^A_G]phi for group G querying whether A is true.

For a group query, define a budget condition BCS(G,A) requiring each group member to afford its share of the minimum cost of A among the group. The update removes states where BCS(G,A) fails, refines group members’ epistemic relations by the truth value of A, leaves outsiders’ relations unchanged except for removed states, and decreases the budgets of group members by the shared cost.

The paper proves completeness, a small-model theorem, polynomial-time model checking, and decidability.

Derivation / Construction

  • Linear inequalities make costs and budgets object-language terms.
  • The semi-public update is public with respect to occurrence: all agents can rule out worlds where the query was unaffordable.
  • The answer is private to G: members distinguish A-worlds from not A-worlds, while outsiders do not learn the answer.
  • Budget decrease is state-dependent because costs and budgets may vary across epistemic alternatives.

Implications

  • SPQ separates information availability from logical ability: agents may reason perfectly but lack resources to obtain facts.
  • Group information acquisition becomes a strategic and epistemic object.
  • The logic is useful for verification and epistemic planning when sensing, querying, or data access has costs.

Graph View

Backlinks