Top 5 Arxiv Papers Today in Computer Science And Game Theory


2.025 Mikeys
#1. On the Price of Anarchy of Cost-Sharing in Real-Time Scheduling Systems
Eirini Georgoulaki, Kostas Kollias
We study cost-sharing games in real-time scheduling systems where the activation cost of the server at any given time is a function of its load. We focus on monomial cost functions and consider both the case when the degree is less than one (inducing positive externalities for the jobs) and when it is greater than one (inducing negative externalities for the jobs). For the former case, we provide tight price of anarchy bounds which show that the price of anarchy grows to infinity as a polynomial of the number of jobs in the game. For the latter, we observe that existing results provide constant and tight (asymptotically in the degree of the monomial) bounds on the price of anarchy. We then switch our attention to improving the price of anarchy by means of a simple coordination mechanism that has no knowledge of the instance. We show that our mechanism reduces the price of anarchy of games with $n$ jobs and unit activation costs from $\Theta(\sqrt{n})$ to $2$. We also show that for a restricted class of instances a similar...
more | pdf | html
Figures
None.
Tweets
DO: On the Price of Anarchy of Cost-Sharing in Real-Time Scheduling Systems. https://t.co/fj8cDFNFMT
timelessdev: RT @DO: On the Price of Anarchy of Cost-Sharing in Real-Time Scheduling Systems. https://t.co/fj8cDFNFMT
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 6780
Unqiue Words: 1508

2.007 Mikeys
#2. Hotelling Games with Multiple Line Faults
Avi Cohen, David Peleg
The Hotelling game consists of n servers each choosing a point on the line segment, so as to maximize the amount of clients it attracts. Clients are uniformly distributed along the line, and each client buys from the closest server. In this paper, we study a fault-prone version of the Hotelling game, where the line fails at multiple random locations. Each failure disconnects the line, blocking the passage of clients. We show that the game admits a Nash equilibrium if and only if the rate of faults exceeds a certain threshold, and calculate that threshold approximately. Moreover, when a Nash equilibrium exists we show it is unique and construct it explicitly. Hence, somewhat surprisingly, the potential occurrence of failures has a stabilizing effect on the game (provided there are enough of them). Additionally, we study the social cost of the game (measured in terms of the total transportation cost of the clients), which also seems to benefit in a certain sense from the potential presence of failures.
more | pdf | html
Figures
None.
Tweets
DO: Hotelling Games with Multiple Line Faults. https://t.co/edbFPz8LaL
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

2.001 Mikeys
#3. Asynchronous Majority Dynamics in Preferential Attachment Trees
Maryam Bahrani, Nicole Immorlica, Divyarthi Mohan, S. Matthew Weinberg
We study information aggregation in networks where agents make binary decisions (labeled incorrect or correct). Agents initially form independent private beliefs about the better decision, which is correct with probability $1/2+\delta$. The dynamics we consider are asynchronous (each round, a single agent updates their announced decision) and non-Bayesian (agents simply copy the majority announcements among their neighbors, tie-breaking in favor of their private signal). Our main result proves that when the network is a tree formed according to the preferential attachment model~\cite{BarabasiA99}, with high probability, the process stabilizes in a correct majority. We extend our results to other tree structures, including balanced $M$-ary trees for any $M$.
more | pdf | html
Figures
None.
Tweets
DO: Asynchronous Majority Dynamics in Preferential Attachment Trees. https://t.co/rFRJnqy4Hd
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

1.998 Mikeys
#4. Deep Learning-powered Iterative Combinatorial Auctions
Jakob Weissteiner, Stefania Ionescu, Nils Olberg, Sven Seuken
In this paper, we study the design of deep learning-powered iterative combinatorial auctions (ICAs). We build on the work by Brero et al. (2018), who have successfully integrated support vector regression (SVR) into the preference elicitation algorithm of an ICA. However, their SVR-based approach also has its limitations because the algorithm requires solving the auction's winner determination problem (WDP) given predicted value functions. With expressive kernels (like gaussian, exponential or high degree polynomial kernels), the WDP cannot be solved for large domains. While linear or low-degree polynomial kernels have better computational scalability, these kernels have limited expressiveness. In this work, we address these shortcomings by using deep neural networks (DNNs) instead of SVRs for learning bidders' valuation functions. Our main contribution is to show that the resulting maximization step of DNNs consisting of rectified linear units as activation functions can always be reformulated into a mixed integer linear program...
more | pdf | html
Figures
Tweets
themathgay: RT @DO: Deep Learning-powered Iterative Combinatorial Auctions. https://t.co/cDTEVNxzsw
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 7044
Unqiue Words: 1804

1.995 Mikeys
#5. On Relevant Equilibria in Reachability Games
Thomas Brihaye, Véronique Bruyère, Aline Goeminne, Nathan Thomasset
We study multiplayer reachability games played on a finite directed graph equipped with target sets, one for each player. In those reachability games, it is known that there always exists a Nash equilibrium (NE) and a subgame perfect equilibrium (SPE). But sometimes several equilibria may coexist such that in one equilibrium no player reaches his target set whereas in another one several players reach it. It is thus very natural to identify "relevant" equilibria. In this paper, we consider different notions of relevant equilibria including Pareto optimal equilibria and equilibria with high social welfare. We provide complexity results for various related decision problems.
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

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 158,360 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 158,360 papers.