...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>International game theory review >COMPACT REPRESENTATIONS OF SEARCH IN COMPLEX DOMAINS
【24h】

COMPACT REPRESENTATIONS OF SEARCH IN COMPLEX DOMAINS

机译：复杂域中搜索的紧凑表示

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We introduce a new zero-sum matrix game for modeling search in structured domains. In this game, one player tries to find a "bug" while the other tries to hide it. Both players exploit the structure of the "search" domain. Intuitively, this search game is a mathematical generalization of the well known binary search. The generalization is from searching over totally ordered sets to searching over more complex search domains such as trees, partial orders and general set systems. As there must be one row for every search strategy, and there are exponentially many ways to search even in very simple search domains, the game's matrix has exponential size ("space"). In this work we present two ways to reduce the space required to compute the Nash value (in pure strategies) of this game: 1. First we show that a Nash equilibrium in pure strategies can be computed by using a backward induction on the matrices of each "part" or sub structure of the search domain. This can significantly reduce the space required to represent the game. 2. Next, we show when general search domains can be represented as DAGs (Directed Acycliqe Graphs). As a result, the Nash equilibrium can be directly computed using the DAG. Consequently the space needed to compute the desired search strategy is reduced to O(n~2) where n is the size of the search domain.
机译：我们介绍了一种新的零和矩阵游戏，用于在结构化域中对搜索进行建模。在这个游戏中，一个玩家试图找到一个“ bug”，而另一个试图隐藏它。两家公司都利用“搜索”域的结构。直观地讲，该搜索游戏是众所周知的二进制搜索的数学概括。概括是从搜索完全有序集到搜索更复杂的搜索域（例如树，偏序和通用集系统）。由于每种搜索策略都必须有一行，并且即使在非常简单的搜索域中，也有成倍的搜索方式，因此游戏的矩阵具有指数大小（“空间”）。在这项工作中，我们提出了两种方法来减少计算此游戏的Nash值所需的空间（在纯策略中）：1.首先，我们证明了可以通过对矩阵A进行反向归纳来计算纯策略中的Nash平衡。搜索域的每个“部分”或子结构。这样可以大大减少代表游戏所需的空间。 2.接下来，我们显示何时可以将一般搜索域表示为DAG（有向无环图）。结果，可以使用DAG直接计算Nash平衡。因此，计算所需搜索策略所需的空间减少为O（n〜2），其中n是搜索域的大小。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号