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
Authors
Bibliographic Details
- Publisher:
- Association for Computing Machinery Publisher's website
- Journal:
- ACM Transactions on Economics and Computation Journal website
- Volume:
- 9
- Issue:
- 1
- Article number:
- 3
- Publication date:
- 2021-01-02
- Acceptance date:
- 2020-02-01
- DOI:
- EISSN:
-
2167-8383
- ISSN:
-
2167-8375
Item Description
- Language:
- English
- Keywords:
- Pubs id:
-
1072718
- Local pid:
- pubs:1072718
- Deposit date:
- 2021-07-14
Terms of use
- Copyright holder:
- Association for Computing Machinery
- Copyright date:
- 2021
- Rights statement:
- © 2020 Association for Computing Machinery.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from the Association for Computing Machinery at: https://doi.org/10.1145/3434412
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record