  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.
