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

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
Department:
Computer Science
Role:
Author
ORCID:
0000-0002-5436-7890
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
Publisher:
Springer, Cham Publisher's website
Journal:
WINE 2018: The 14th Conference on Web and Internet Economics Journal website
Volume:
11316
Pages:
168-187
Series:
Lecture Notes in Computer Science
Host title:
WINE 2018: Web and Internet Economics
Publication date:
2018-11-21
Acceptance date:
2018-09-24
DOI:
ISSN:
0302-9743
Source identifiers:
941351
ISBN:
9783030046125
Keywords:
Pubs id:
pubs:941351
UUID:
uuid:6b643ee2-10ef-4658-b710-ea21d6d4ceba
Local pid:
pubs:941351
Deposit date:
2018-11-13

Terms of use


Views and Downloads






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

TO TOP