Contextual search in the presence of irrational agents

Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, Robert Schapire

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study contextual search, a generalization of binary search in higher dimensions, which captures settings such as feature-based dynamic pricing. Standard game-theoretic formulations of this problem assume that agents act in accordance with a specific behavioral model. In practice, some agents may not subscribe to the dominant behavioral model or may act in ways that are seemingly arbitrarily irrational. Existing algorithms heavily depend on the behavioral model being (approximately) accurate for all agents and have poor performance even with a few arbitrarily irrational agents. We initiate the study of contextual search when some of the agents can behave in ways inconsistent with the underlying behavioral model. In particular, we provide two algorithms, one based on multidimensional binary search methods and one based on gradient descent. Our techniques draw inspiration from learning theory, game theory, high-dimensional geometry, and convex analysis.

Original languageEnglish (US)
Title of host publicationSTOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
EditorsSamir Khuller, Virginia Vassilevska Williams
PublisherAssociation for Computing Machinery
Pages910-918
Number of pages9
ISBN (Electronic)9781450380539
DOIs
StatePublished - Jun 15 2021
Externally publishedYes
Event53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy
Duration: Jun 21 2021Jun 25 2021

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Country/TerritoryItaly
CityVirtual, Online
Period6/21/216/25/21

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Adversarial corruptions
  • Binary search
  • Dynamic pricing

Fingerprint

Dive into the research topics of 'Contextual search in the presence of irrational agents'. Together they form a unique fingerprint.

Cite this