We study a generalization of the secretary problem, where decisions do not
have to be made immediately upon candidates' arrivals. After arriving, each
candidate stays in the system for some (random) amount of time and then leaves,
whereupon the algorithm has to decide irrevocably whether to select this
candidate or not. The goal is to maximize the probability of selecting the best
candidate overall. We assume that the arrival and waiting times are drawn from
known distributions.
Our first main result is a characterization of the optimal policy for this
setting. We show that when deciding whether to select a candidate it suffices
to know only the time and the number of candidates that have arrived so far.
Furthermore, the policy is monotone non-decreasing in the number of candidates
seen so far, and, under certain natural conditions, monotone non-increasing in
the time. Our second main result is proving that when the number of candidates
is large, a single threshold policy is almost optimal.

more |
pdf
| html
None.

okateim:
2019/09/20 [5]
How to Hire Secretaries with Stochastic Departures (https://t.co/p6AMkcS0Vd)

DO:
How to Hire Secretaries with Stochastic Departures. https://t.co/6gBfHKkBcu

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

Supply chains are the backbone of the global economy. Disruptions to them can
be costly. Centrally managed supply chains invest in ensuring their resilience.
Decentralized supply chains, however, must rely upon the self-interest of their
individual components to maintain the resilience of the entire chain.
We examine the incentives that independent self-interested agents have in
forming a resilient supply chain network in the face of production disruptions
and competition. In our model, competing suppliers are subject to yield
uncertainty (they deliver less than ordered) and congestion (lead time
uncertainty or, "soft" supply caps). Competing retailers must decide which
suppliers to link to based on both price and reliability.
In the presence of yield uncertainty only, the resulting supply chain
networks are sparse. Retailers concentrate their links on a single supplier,
counter to the idea that they should mitigate yield uncertainty by diversifying
their supply base. This happens because retailers benefit from supply...

more |
pdf
| html
arxiv_org:
Strategic Formation and Reliability of Supply Chain Networks. https://t.co/GLBrawxlei https://t.co/MApeGF8Aeg

DO:
Strategic Formation and Reliability of Supply Chain Networks. https://t.co/c9KS8WsTLg

subhobrata1:
RT @arxiv_org: Strategic Formation and Reliability of Supply Chain Networks. https://t.co/GLBrawxlei https://t.co/MApeGF8Aeg

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 18582

Unqiue Words: 2976

The sequential allocation protocol is a simple and popular mechanism to
allocate indivisible goods, in which the agents take turns to pick the items
according to a predefined sequence. While this protocol is not strategy-proof,
it has been shown recently that finding a successful manipulation for an agent
is an NP-hard problem (Aziz et al., 2017). Conversely, it is also known that
finding an optimal manipulation can be solved in polynomial time in a few
cases: if there are only two agents or if the manipulator has a binary or a
lexicographic utility function. In this work, we take a parametrized approach
to provide several new complexity results on this manipulation problem.
Notably, we show that finding an optimal manipulation can be performed in
polynomial time if the number of agents is a constant and that it is
fixed-parameter tractable with respect to a parameter measuring the distance
between the preference rankings of the agents. Moreover, we provide an integer
program and a dynamic programming scheme to solve the...

more |
pdf
| html
None.

DO:
Parametrized Complexity of Manipulating Sequential Allocation. https://t.co/UX7SsjmMWt

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 0

Unqiue Words: 0

We consider concurrent stochastic games played on graphs with reachability
and safety objectives. These games can be solved by value iteration as well as
strategy iteration, each of them yielding a sequence of under-approximations of
the reachability value and a sequence of over-approximation of the safety
value, converging to it in the limit. For both approaches, we provide the first
(anytime) algorithms with stopping criteria. The stopping criterion for value
iteration is based on providing a convergent sequence of over-approximations,
which then allows to estimate the distance to the true value. For strategy
iteration, we bound the error by complementing the strategy iteration algorithm
for reachability by a new strategy iteration algorithm under-approximating the
safety-value.

more |
pdf
| html
None.

BrundageBot:
Stopping Criteria for Value and Strategy Iteration on Concurrent Stochastic Reachability Games. Julia Eisentraut, Jan Křetínský, and Alexej Rotar https://t.co/Q7PPNlYPdz

DO:
Stopping Criteria for Value and Strategy Iteration on Concurrent Stochastic Reachability Games. https://t.co/OA0xACNC0n

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 12117

Unqiue Words: 2150

Several relaxations of envy-freeness, tailored to fair division in settings
with indivisible goods, have been introduced within the last decade. Due to the
lack of general existence results for most of these concepts, great attention
has been paid to establishing approximation guarantees. In this work, we
propose a simple algorithm that is universally fair in the sense that it
returns allocations that have good approximation guarantees with respect to
four such fairness notions at once. In particular, this is the first algorithm
achieving a $(\phi -1)$-approximation of envy-freeness up to any good (EFX) and
a $\frac{2}{\phi +2}$-approximation of groupwise maximin share fairness (GMMS),
where $\phi$ is the golden ratio ($\phi \approx 1.618$). The best known
approximation factor for either one of these fairness notions prior to this
work was $1/2$. Moreover, the returned allocation achieves envy-freeness up to
one good (EF1) and a $2/3$-approximation of pairwise maximin share fairness
(PMMS). While EFX is our primary focus, we also...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

We study games with reachability objectives under energy constraints. We
first prove that under strict energy constraints (either only lower-bound
constraint or interval constraint), those games are LOGSPACE-equivalent to
energy games with the same energy constraints but without reachability
objective (i.e., for infinite runs). We then consider two kinds of relaxations
of the upper-bound constraints (while keeping the lower-bound constraint
strict): in the first one, called weak upper bound, the upper bound is
absorbing, in the sense that it allows receiving more energy when the upper
bound is already reached, but the extra energy will not be stored; in the
second one, we allow for temporary violations of the upper bound, imposing
limits on the number or on the amount of violations. We prove that when
considering weak upper bound, reachability objectives require memory, but can
still be solved in polynomial-time for one-player arenas; we prove that they
are in co-NP in the two-player setting. Allowing for bounded violations...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 10660

Unqiue Words: 2295

As a famous result, the ``37\% Law'' for Secretary Problem has widely
influenced peoples' perception on online decision strategies about choice.
However, using this strategy, too many attractive candidates may be rejected in
the first 37\%, and in practice people also tend to stop
earlier\cite{Bearden_early}. In this paper, we argued that in most cases, the
best-only optimization does not obtain an optimal outcome, while the optimal
cutoff should be $O(\sqrt{n})$. And we also showed that in some strict
objective that only cares several best candidates, $\Theta(n)$ skips are still
needed.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 2364

Unqiue Words: 733

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 192,915 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible