Delegated Pandora's Box
Delegated Pandora's Box
复制标题
委托潘多拉魔盒
DOI：
10.1145/3490486.3538267
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Patel, Neel
中科院分区：
文献类型：
--
作者：
Bechtel, Curtis;Dughmi, Shaddin;Patel, Neel
在委托问题中，委托人没有完成特定任务所需的资源，因此他们将任务委托给一个不受信任的代理人，该代理人的利益可能与他们自己的利益不同。给定任何此类问题和委托人可选择的机制空间，委托差距是委托人委托时的最佳效用与自己解决问题时的最佳效用的最坏情况比率。在这项工作中，我们考虑的广义潘多拉盒子问题，搜索问题，其中搜索解决方案引起已知的成本和解决方案的限制，由一些向下封闭的约束的代表团差距。首先，我们表明，有一个特殊的情况下，当所有的随机变量有二进制支持存在常数因子的代表团间隙拟阵约束。然而，即使是简单的非二进制问题实例，也不存在常数因子的委托差距。绕过这种不可能性，我们考虑两种变体：自由代理模型，其中代理不支付探测元素的成本，以及折扣成本近似，其中我们对所有成本进行折扣，目标是折扣因子和授权差距的双准则近似。我们发现，有常数因子的授权差距的自由代理人模型与折扣成本近似某些向下封闭的约束和常数折扣因子。然而，单靠这两种变式都无法实现经常性的授权差距。最后，我们考虑另一种称为共享成本模型的变体，在该模型中，委托人可以选择在委托搜索问题之前如何在他们和代理人之间共享成本。我们发现，共享成本模型表现出一定的向下封闭约束的常数因子的授权差距。
In delegation problems, a principal does not have the resources necessary to complete a particular task, so they delegate the task to an untrusted agent whose interests may differ from their own. Given any family of such problems and space of mechanisms for the principal to choose from, the delegation gap is the worst-case ratio of the principal's optimal utility when they delegate versus their optimal utility when solving the problem on their own. In this work, we consider the delegation gap of the generalized Pandora's box problem, a search problem in which searching for solutions incurs known costs and solutions are restricted by some downward-closed constraint. First, we show that there is a special case when all random variables have binary support for which there exist constant-factor delegation gaps for matroid constraints. However, there is no constant-factor delegation gap for even simple non-binary instances of the problem. Getting around this impossibility, we consider two variants: the free-agent model, in which the agent doesn't pay the cost of probing elements, and discounted-cost approximations, in which we discount all costs and aim for a bicriteria approximation of the discount factor and delegation gap. We show that there are constant-factor delegation gaps in the free-agent model with discounted-cost approximations for certain downward closed constraints and constant discount factors. However, constant delegation gaps can not be achieved under either variant alone. Finally, we consider another variant called the shared-cost model, in which the principal can choose how costs will be shared between them and the agent before delegating the search problem. We show that the shared-cost model exhibits a constant-factor delegation gap for certain downward closed constraints.
登录
查看更多内容
在线潘多拉魔盒和强盗
DOI：
10.1609/aaai.v33i01.33011885
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Hossein Esfandiari;M. Hajiaghayi;Brendan Lucier;M. Mitzenmacher
通讯作者：
M. Mitzenmacher
委托随机探测
DOI：
10.4230/lipics.itcs.2021.37
发表时间：
2021
期刊：
Innovations in Theoretical Computer Science (ITCS
影响因子：
--
作者：
Bechtel, Curtis;Dughmi, Shaddin
通讯作者：
Dughmi, Shaddin
DOI：
10.1137/1.9781611974331.ch72
发表时间：
2015-08
期刊：
--
影响因子：
--
作者：
Moran Feldman;O. Svensson;R. Zenklusen
通讯作者：
Moran Feldman;O. Svensson;R. Zenklusen
委托搜索近似于高效搜索
DOI：
10.1145/3219166.3219205
发表时间：
2018
期刊：
Proceedings of the 2018 ACM Conference on Economics and Computation
影响因子：
--
作者：
Kleinberg, Jon;Kleinberg, Robert
通讯作者：
Kleinberg, Robert