Logo image
Back
Simple Delegated Choice
Preprint   Open access

Simple Delegated Choice

Ali Khodabakhsh, Emmanouil Pountourakis and Samuel Taggart
arXiv.org
24 Jun 2024
DOI: https://doi.org/10.48550/arxiv.2406.16343
url
https://arxiv.org/abs/2406.16343View
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute,  Open

Abstract

Computer Science - Computer Science and Game Theory
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024) This paper studies delegation in a model of discrete choice. In the delegation problem, an uninformed principal must consult an informed agent to make a decision. Both the agent and principal have preferences over the decided-upon action which vary based on the state of the world, and which may not be aligned. The principal may commit to a mechanism, which maps reports of the agent to actions. When this mechanism is deterministic, it can take the form of a menu of actions, from which the agent simply chooses upon observing the state. In this case, the principal is said to have delegated the choice of action to the agent. We consider a setting where the decision being delegated is a choice of a utility-maximizing action from a set of several options. We assume the shared portion of the agent's and principal's utilities is drawn from a distribution known to the principal, and that utility misalignment takes the form of a known bias for or against each action. We provide tight approximation analyses for simple threshold policies under three increasingly general sets of assumptions. With independently-distributed utilities, we prove a $3$-approximation. When the agent has an outside option the principal cannot rule out, the constant approximation fails, but we prove a $\log \rho/\log\log \rho$-approximation, where $\rho$ is the ratio of the maximum value to the optimal utility. We also give a weaker but tight bound that holds for correlated values, and complement our upper bounds with hardness results. One special case of our model is utility-based assortment optimization, for which our results are new.

Metrics

26 Record Views

Details

Logo image