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

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 6780
Unqiue Words: 1508

##### #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
None.
###### Tweets
DO: Hotelling Games with Multiple Line Faults. https://t.co/edbFPz8LaL
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

##### #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
None.
###### Tweets
DO: Asynchronous Majority Dynamics in Preferential Attachment Trees. https://t.co/rFRJnqy4Hd
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

##### #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
###### Tweets
themathgay: RT @DO: Deep Learning-powered Iterative Combinatorial Auctions. https://t.co/cDTEVNxzsw
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 7044
Unqiue Words: 1804

##### #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
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

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
Online
###### Stats
Tracking 158,360 papers.