1 Search Results for "Bechtel, Curtis"

Document
DOI: 10.4230/LIPIcs.ITCS.2021.37
Delegated Stochastic Probing

Authors: Curtis Bechtel and Shaddin Dughmi

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Delegation covers a broad class of problems in which a principal doesn't have the resources or expertise necessary to complete a task by themselves, so they delegate the task to an agent whose interests may not be aligned with their own. Stochastic probing describes problems in which we are tasked with maximizing expected utility by "probing" known distributions for acceptable solutions subject to certain constraints. In this work, we combine the concepts of delegation and stochastic probing into a single mechanism design framework which we term delegated stochastic probing. We study how much a principal loses by delegating a stochastic probing problem, compared to their utility in the non-delegated solution. Our model and results are heavily inspired by the work of Kleinberg and Kleinberg in "Delegated Search Approximates Efficient Search." Building on their work, we show that there exists a connection between delegated stochastic probing and generalized prophet inequalities, which provides us with constant-factor deterministic mechanisms for a large class of delegated stochastic probing problems. We also explore randomized mechanisms in a simple delegated probing setting, and show that they outperform deterministic mechanisms in some instances but not in the worst case.
Cite as

Curtis Bechtel and Shaddin Dughmi. Delegated Stochastic Probing. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bechtel_et_al:LIPIcs.ITCS.2021.37,
  author =	{Bechtel, Curtis and Dughmi, Shaddin},
  title =	{{Delegated Stochastic Probing}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{37:1--37:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.37},
  URN =		{urn:nbn:de:0030-drops-135763},
  doi =		{10.4230/LIPIcs.ITCS.2021.37},
  annote =	{Keywords: Delegation, Mechanism Design, Algorithmic Game Theory}
}
  • Refine by Author
  • 1 Bechtel, Curtis
  • 1 Dughmi, Shaddin

  • Refine by Classification
  • 1 Theory of computation → Algorithmic mechanism design

  • Refine by Keyword
  • 1 Algorithmic Game Theory
  • 1 Delegation
  • 1 Mechanism Design

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact