论文标题
关于竞争性秘书问题，延期选择
On a Competitive Secretary Problem with Deferred Selections
论文作者
论文摘要
我们在与多个代理商的设置中研究秘书问题。在标准秘书问题中，一系列任意奖励按随机订单在线到达，一个决策者做出了立即且不可撤销的决定，是否在其到达时是否接受每个奖励。在许多情况下，由于关于竞争的隐含假设，在许多情况下出现了立即决定的要求。也就是说，如果决策者不立即获得所提供的奖励，则其他人将获得。本文的新颖性在于引入了竞争是内源性的多代理模型。在我们的模型中，多个代理商竞争到达奖项，但决策不必立即做出。相反，代理可以选择以前的奖项，只要可用（即，不是由其他代理商获得）。如果多个代理商选择了奖励，则关系被随机或根据全球排名打破。这引起了一个多代理游戏，在该游戏中，游戏规则不强制选择的时间，而是代理商策略的重要组成部分。我们研究了这个游戏中平衡的结构和性能。对于随机打破的打破，我们表征了游戏的均衡，并表明尽管代理商竞争，但仍有预期的均衡社会福利几乎是最佳的。对于排名排名的领带，我们在3代理游戏中给出了平衡的全部表征，并表明，随着代理的数量的增长，非Immediate Selections下每个代理商的获胜概率都接近了她在即时选择下的获胜概率。
We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes an immediate and irrevocable decision whether to accept each award upon its arrival. The requirement to make immediate decisions arises in many cases due to an implicit assumption regarding competition. Namely, if the decision maker does not take the offered award immediately, it will be taken by someone else. The novelty in this paper is in introducing a multi-agent model in which the competition is endogenous. In our model, multiple agents compete over the arriving awards, but the decisions need not be immediate; instead, agents may select previous awards as long as they are available (i.e., not taken by another agent). If an award is selected by multiple agents, ties are broken either randomly or according to a global ranking. This induces a multi-agent game in which the time of selection is not enforced by the rules of the games, rather it is an important component of the agent's strategy. We study the structure and performance of equilibria in this game. For random tie breaking, we characterize the equilibria of the game, and show that the expected social welfare in equilibrium is nearly optimal, despite competition among the agents. For ranked tie breaking, we give a full characterization of equilibria in the 3-agent game, and show that as the number of agents grows, the winning probability of every agent under non-immediate selections approaches her winning probability under immediate selections.
