Journal article icon

Journal article

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.1145/3434412

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
Oxford college:
Balliol College
Role:
Author
Publisher:
Association for Computing Machinery
Journal:
ACM Transactions on Economics and Computation More from this journal
Volume:
9
Issue:
1
Article number:
3
Publication date:
2021-01-02
Acceptance date:
2020-02-01
DOI:
EISSN:
2167-8383
ISSN:
2167-8375
Language:
English
Keywords:
Pubs id:
1072718
Local pid:
pubs:1072718
Deposit date:
2021-07-14

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