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.

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.

Sample Sizes : None.

Authors: 2

Total Words: 6780

Unqiue Words: 1508

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.

DO:
Hotelling Games with Multiple Line Faults. https://t.co/edbFPz8LaL

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

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.

DO:
Asynchronous Majority Dynamics in Preferential Attachment Trees. https://t.co/rFRJnqy4Hd

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 0

Unqiue Words: 0

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
themathgay:
RT @DO: Deep Learning-powered Iterative Combinatorial Auctions. https://t.co/cDTEVNxzsw

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 7044

Unqiue Words: 1804

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.

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.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible