Delay-Predictability Trade-offs in Reaching a Secret Goal
成果类型：
Article
署名作者：
Tsitsiklis, John N.; Xu, Kuang
署名单位：
Massachusetts Institute of Technology (MIT); Stanford University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.2017.1682
发表日期：
2018
页码：
587-596
关键词：
摘要：
We formulate a model of sequential decision making, dubbed the Goal Prediction game, to study the extent to which an overseeing adversary can predict the final goal of an agent who tries to reach that goal quickly, through a sequence of intermediate actions. Our formulation is motivated by the increasing ubiquity of large-scale surveillance and data collection infrastructures, which can be used to predict an agent's intentions and future actions, despite the agent's desire for privacy. Our main result shows that with a carefully chosen agent strategy, the probability that the agent's goal is correctly predicted by an adversary can be made inversely proportional to the time that the agent is willing to spend in reaching the goal, but cannot be made any smaller than that. Moreover, this characterization depends on the topology of the agent's state space only through its diameter.
来源URL：