Top 7 Arxiv Papers Today in Computer Science And Game Theory


2.082 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

2.016 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 18582
Unqiue Words: 2976

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

2.012 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 12117
Unqiue Words: 2150

1.997 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

1.997 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 10660
Unqiue Words: 2295

1.997 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 2364
Unqiue Words: 733

About

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
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 192,915 papers.