Suppose that an $m$-simplex is partitioned into $n$ convex regions having
disjoint interiors and distinct labels, and we may learn the label of any point
by querying it. The learning objective is to know, for any point in the
simplex, a label that occurs within some distance $\epsilon$ from that point.
We present two algorithms for this task: Constant-Dimension Generalised Binary
Search (CD-GBS), which for constant $m$ uses $poly(n, \log \left(
\frac{1}{\epsilon} \right))$ queries, and Constant-Region Generalised Binary
Search (CR-GBS), which uses CD-GBS as a subroutine and for constant $n$ uses
$poly(m, \log \left( \frac{1}{\epsilon} \right))$ queries.
We show via Kakutani's fixed-point theorem that these algorithms provide
bounds on the best-response query complexity of computing approximate
well-supported equilibria of bimatrix games in which one of the players has a
constant number of pure strategies. We also partially extend our results to
games with multiple players, establishing further query complexity bounds for
computing approximate well-supported equilibria in this setting.

给定一个划分成 $n$ 个具有不同标签和内部不相交的凸区域的 $m$- 单纯形，可通过查询了解任何点的标签，本文提出了两种算法：CD-GBS 和 CR-GBS，并通过 Kakutani 的不动点定理证明了这些算法在计算近似均衡时提供了较佳的查询复杂性界限。

从最佳反应查询中学习凸分割和计算博弈论均衡

Learning Convex Partitions and Computing Game-theoretic Equilibria from  Best Response Queries

Recent years have witnessed the successful application of low-dimensional
vector space representations of knowledge graphs to predict missing facts or
find erroneous ones. However, it is not yet well-understood to what extent
ontological knowledge, e.g. given as a set of (existential) rules, can be
embedded in a principled way. To address this shortcoming, in this paper we
introduce a general framework based on a view of relations as regions, which
allows us to study the compatibility between ontological knowledge and
different types of vector space embeddings. Our technical contribution is
two-fold. First, we show that some of the most popular existing embedding
methods are not capable of modelling even very simple types of rules, which in
particular also means that they are not able to learn the type of dependencies
captured by such rules. Second, we study a model in which relations are
modelled as convex regions. We show particular that ontologies which are
expressed using so-called quasi-chained existential rules can be exactly
represented using convex regions, such that any set of facts which is induced
using that vector space embedding is logically consistent and deductively
closed with respect to the input ontology.

本文提出了一种基于关系视图的框架，使我们可以研究本体知识和不同类型向量空间嵌入之间的兼容性，并证明了一些现有的嵌入方法无法建模一些简单的规则，同时研究了关系建模为凸区域的模型，发现使用凸区域可精确表示所谓的准链式存在量规则的本体，从而对于所有在这个向量空间内运用的事实都是逻辑一致和推导闭合的。