TY - GEN

T1 - Contextual search in the presence of irrational agents

AU - Krishnamurthy, Akshay

AU - Lykouris, Thodoris

AU - Podimata, Chara

AU - Schapire, Robert

N1 - Publisher Copyright:
© 2021 Owner/Author.

PY - 2021/6/15

Y1 - 2021/6/15

N2 - 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.

AB - 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.

KW - Adversarial corruptions

KW - Binary search

KW - Dynamic pricing

UR - http://www.scopus.com/inward/record.url?scp=85108142994&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108142994&partnerID=8YFLogxK

U2 - 10.1145/3406325.3451120

DO - 10.1145/3406325.3451120

M3 - Conference contribution

AN - SCOPUS:85108142994

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 910

EP - 918

BT - STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Khuller, Samir

A2 - Williams, Virginia Vassilevska

PB - Association for Computing Machinery

T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021

Y2 - 21 June 2021 through 25 June 2021

ER -