Conference proceeding
Simple Delegated Choice
PROCEEDINGS OF THE 2024 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, pp.569-590
01 Jan 2024
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
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. 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
1 Record Views
Details
- Title
- Simple Delegated Choice
- Creators
- Ali Khodabakhsh - Univ Texas Austin, Austin, TX 78712 USAEmmanouil Pountourakis - Drexel UniversitySamuel Taggart - Oberlin Coll, Oberlin, OH 44074 USA
- Contributors
- D P Woodruff (Editor)
- Publication Details
- PROCEEDINGS OF THE 2024 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, pp.569-590
- Conference
- 2024 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA
- Publisher
- Siam
- Number of pages
- 22
- Grant note
- CCF 2218813; CCF 2218814 / NSF; National Science Foundation (NSF)
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Identifiers
- 991021902496304721
UN Sustainable Development Goals (SDGs)
This output has contributed to the advancement of the following goals:
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Computer Science, Theory & Methods
- Mathematics
- Mathematics, Applied