Conference item icon

Conference item

Learning convex partitions and computing game-theoretic equilibria from best response queries

Abstract:

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 ε 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(1ε)) queries, and Constant-Region Generalised Binary Search (CR-GBS...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1007/978-3-030-04612-5_12

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
ORCID:
0000-0002-5436-7890
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Publisher:
Springer, Cham Publisher's website
Volume:
11316
Pages:
168-187
Series:
Lecture Notes in Computer Science
Publication date:
2018-11-21
Acceptance date:
2018-09-24
DOI:
ISSN:
0302-9743
Pubs id:
pubs:941351
URN:
uri:6b643ee2-10ef-4658-b710-ea21d6d4ceba
UUID:
uuid:6b643ee2-10ef-4658-b710-ea21d6d4ceba
Local pid:
pubs:941351
ISBN:
978-3-030-04612-5

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP