- arXiv.org
- Popular Physics
- Space Physics
- Data Analysis, Statistics and Probability
- History and Philosophy of Physics
- Physics and Society
- Optics
- General Physics
- Biological Physics
- Atomic and Molecular Clusters
- Fluid Dynamics
- Plasma Physics
- Atomic Physics
- Geophysics
- Medical Physics
- Atmospheric and Oceanic Physics
- Accelerator Physics
- Chemical Physics
- Instrumentation and Detectors
- Computational Physics
- Classical Physics
- Physics Education

- History and Overview
- Analysis of PDEs
- Number Theory
- Information Theory
- Statistics Theory
- Mathematical Physics
- Combinatorics
- Symplectic Geometry
- Operator Algebras
- Probability
- Complex Variables
- Representation Theory
- Algebraic Geometry
- Group Theory
- Metric Geometry
- Optimization and Control
- General Mathematics
- Differential Geometry
- Dynamical Systems
- Numerical Analysis
- Logic
- Geometric Topology
- Quantum Algebra
- General Topology
- Rings and Algebras
- Functional Analysis
- K-Theory and Homology
- Spectral Theory
- Commutative Algebra
- Classical Analysis and ODEs
- Algebraic Topology
- Category Theory

- Computational Complexity
- Symbolic Computation
- General Literature
- Information Retrieval
- Information Theory
- Formal Languages and Automata Theory
- Multiagent Systems
- Computer Vision and Pattern Recognition
- Numerical Analysis
- Other Computer Science
- Social and Information Networks
- Databases
- Sound
- Learning
- Neural and Evolutionary Computing
- Software Engineering
- Programming Languages
- Operating Systems
- Emerging Technologies
- Artificial Intelligence
- Mathematical Software
- Hardware Architecture
- Computer Science and Game Theory
- Discrete Mathematics
- Human-Computer Interaction
- Cryptography and Security
- Digital Libraries
- Systems and Control
- Distributed, Parallel, and Cluster Computing
- Computational Engineering, Finance, and Science
- Performance
- Networking and Internet Architecture
- Computation and Language
- Data Structures and Algorithms
- Robotics
- Graphics
- Computational Geometry
- Multimedia
- Computers and Society
- Logic in Computer Science

- Jun 29 2017 cs.GT arXiv:1706.09132v1We study Nash equilibria and the price of anarchy in the classical model of Network Creation Games introduced by Fabrikant et al. In this model every agent (node) buys links at a prefixed price $\alpha>0$ in order to get connected to the network formed by all the $n$ agents. In this setting, the reformulated tree conjecture states that for $\alpha > n$, every Nash equilibrium network is a tree. Since it was shown that the price of anarchy for trees is constant, if the tree conjecture were true, then the price of anarchy would be constant for $\alpha >n$. Moreover, Demaine et al. conjectured that the price of anarchy for this model is constant. Up to now the last conjecture has been proven in (i) the \emphlower range, for $\alpha = O(n^{1-\epsilon})$ with $\epsilon \geq \frac{1}{\log n}$ and (ii) in the \emphupper range, for $\alpha > 65n$. In contrast, the best upper bound known for the price of anarchy for the remaining range is $2^{O(\sqrt{\log n})}$. In this paper we give new insights into the structure of the Nash equilibria for different ranges of $\alpha$ and we enlarge the range for which the price of anarchy is constant. Regarding the upper range, we prove that every Nash equilibrium is a tree for $\alpha > 17n$ and that the price of anarchy is constant even for $\alpha > 9n$. In the lower range, we show that any Nash equilibrium for $\alpha < n/C$ with $C > 4$, induces an $\epsilon-$distance-almost-uniform graph.
- Jun 29 2017 cs.GT arXiv:1706.09060v1We study a strategic version of the multi-armed bandit problem, where each arm is an individual strategic agent and we, the principal, pull one arm each round. When pulled, the arm receives some private reward $v_a$ and can choose an amount $x_a$ to pass on to the principal (keeping $v_a-x_a$ for itself). All non-pulled arms get reward $0$. Each strategic arm tries to maximize its own utility over the course of $T$ rounds. Our goal is to design an algorithm for the principal incentivizing these arms to pass on as much of their private rewards as possible. When private rewards are stochastically drawn each round ($v_a^t \leftarrow D_a$), we show that: - Algorithms that perform well in the classic adversarial multi-armed bandit setting necessarily perform poorly: For all algorithms that guarantee low regret in an adversarial setting, there exist distributions $D_1,\ldots,D_k$ and an approximate Nash equilibrium for the arms where the principal receives reward $o(T)$. - Still, there exists an algorithm for the principal that induces a game among the arms where each arm has a dominant strategy. When each arm plays its dominant strategy, the principal sees expected reward $\mu'T - o(T)$, where $\mu'$ is the second-largest of the means $\mathbb{E}[D_{a}]$. This algorithm maintains its guarantee if the arms are non-strategic ($x_a = v_a$), and also if there is a mix of strategic and non-strategic arms.
- Additively separable hedonic games and fractional hedonic games have received considerable attention. They are coalition forming games of selfish agents based on their mutual preferences. Most of the work in the literature characterizes the existence and structure of stable outcomes (i.e., partitions in coalitions), assuming that preferences are given. However, there is little discussion on this assumption. In fact, agents receive different utilities if they belong to different partitions, and thus it is natural for them to declare their preferences strategically in order to maximize their benefit. In this paper we consider strategyproof mechanisms for additively separable hedonic games and fractional hedonic games, that is, partitioning methods without payments such that utility maximizing agents have no incentive to lie about their true preferences. We focus on social welfare maximization and provide several lower and upper bounds on the performance achievable by strategyproof mechanisms for general and specific additive functions. In most of the cases we provide tight or asymptotically tight results. All our mechanisms are simple and can be computed in polynomial time. Moreover, all the lower bounds are unconditional, that is, they do not rely on any computational or complexity assumptions.

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of ...

Māris Ozols Oct 21 2016 21:06 UTCPiotr Migdał Apr 18 2014 18:43 UTC

...(continued)A podcast summarizing this paper, by Geoff Engelstein: [The Dice Tower # 351 - Dealing with the Mockers (43:55 - 50:36)](http://dicetower.coolstuffinc.com/tdt-351-dealing-with-the-mockers), and [an alternative link on the BoardGameGeek](http://boardgamegeek.com/boardgamepodcastepisode/117163/tdt-351