### Top 7 Arxiv Papers Today in Computer Science And Game Theory

##### #1. How to Hire Secretaries with Stochastic Departures
###### Thomas Kesselheim, Alexandros Psomas, Shai Vardi
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.
###### Tweets
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.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

##### #2. Strategic Formation and Reliability of Supply Chain Networks
###### Victor Amelkin, Rakesh Vohra
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
###### Tweets
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.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 18582
Unqiue Words: 2976

##### #3. Parametrized Complexity of Manipulating Sequential Allocation
###### Hugo Gilbert
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.
###### Tweets
DO: Parametrized Complexity of Manipulating Sequential Allocation. https://t.co/UX7SsjmMWt
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

##### #4. Stopping Criteria for Value and Strategy Iteration on Concurrent Stochastic Reachability Games
###### Julia Eisentraut, Jan Křetínský, Alexej Rotar
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.
###### Tweets
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.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 12117
Unqiue Words: 2150

##### #5. Multiple Birds with One Stone: Beating $1/2$ for EFX and GMMS via Envy Cycle Elimination
###### Georgios Amanatidis, Apostolos Ntokos, Evangelos Markakis
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.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

##### #6. Reachability Games with Relaxed Energy Constraints
###### Loïc Hélouët, Nicolas Markey, Ritam Raha
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.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 10660
Unqiue Words: 2295

##### #7. An Asymptotic Analysis on Generalized Secretary Problem
###### Zishuo Zhao
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.
###### Other stats
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.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 192,915 papers.