Abstract:
We study network formation with n players and link cost α > 0. After the network is built, an adversary randomly deletes one link according to a certain probability distribution. Cost for player？ ν incorporates the expected number of players to which？ ν will become disconnected. We focus on unilateral link formation and Nash equilibrium. We show existence of Nash equilibria and a price of stability of 1 + ο(1) under moderate assumptions on the adversary and n ≥ 9. We prove bounds on the price of anarchy for two special adversaries: one removes a link chosen uniformly at random, while the other removes a link that causes a maximum number of player pairs to be separated. We show an Ο(1) bound on the price of anarchy for both adversaries, the constant being bounded by 15 + ο(1) and 9 + ο(1), respectively.

Abstract:
We study network formation with n players and link cost \alpha > 0. After the network is built, an adversary randomly deletes one link according to a certain probability distribution. Cost for player v incorporates the expected number of players to which v will become disconnected. We show existence of equilibria and a price of stability of 1+o(1) under moderate assumptions on the adversary and n \geq 9. As the main result, we prove bounds on the price of anarchy for two special adversaries: one removes a link chosen uniformly at random, while the other removes a link that causes a maximum number of player pairs to be separated. For unilateral link formation we show a bound of O(1) on the price of anarchy for both adversaries, the constant being bounded by 10+o(1) and 8+o(1), respectively. For bilateral link formation we show O(1+\sqrt{n/\alpha}) for one adversary (if \alpha > 1/2), and \Theta(n) for the other (if \alpha > 2 considered constant and n \geq 9). The latter is the worst that can happen for any adversary in this model (if \alpha = \Omega(1)). This points out substantial differences between unilateral and bilateral link formation.

Abstract:
We study network formation with the bilateral link formation rule (Jackson and Wolinsky 1996) with $n$ players and link cost $\alpha>0$. After the network is built, an adversary randomly destroys one link according to a certain probability distribution. Cost for player $v$ incorporates the expected number of players to which $v$ will become disconnected. This model was previously studied for unilateral link formation (K. 2011). We prove existence of pairwise Nash equilibria under moderate assumptions on the adversary and $n\geq 9$. As the main result, we prove bounds on the price of anarchy for two special adversaries: one destroys a link chosen uniformly at random, while the other destroys a link that causes a maximum number of player pairs to be separated. We prove bounds tight up to constants, namely $O(1)$ for one adversary (if $\alpha>1/2$), and $\Theta(n)$ for the other (if $\alpha>2$ considered constant and $n \geq 9$). The latter is the worst that can happen for any adversary in this model (if $\alpha=\Omega(1)$).

Abstract:
We study the price of anarchy in a class of graph coloring games (a subclass of polymatrix common-payoff games). In those games, players are vertices of an undirected, simple graph, and the strategy space of each player is the set of colors from $1$ to $k$. A tight bound on the price of anarchy of $\frac{k}{k-1}$ is known (Hoefer 2007, Kun et al. 2013), for the case that each player's payoff is the number of her neighbors with different color than herself. The study of more complex payoff functions was left as an open problem. We compute payoff for a player by determining the distance of her color to the color of each of her neighbors, applying a non-negative, real-valued, concave function $f$ to each of those distances, and then summing up the resulting values. This includes the payoff functions suggested by Kun et al. (2013) for future work as special cases. Denote $f^*$ the maximum value that $f$ attains on the possible distances $0,\dots,k-1$. We prove an upper bound of $2$ on the price of anarchy for concave functions $f$ that are non-decreasing or which assume $f^*$ at a distance on or below $\lfloor\frac{k}{2}\rfloor$. Matching lower bounds are given for the monotone case and for the case that $f^*$ is assumed in $\frac{k}{2}$ for even $k$. For general concave functions, we prove an upper bound of $3$. We use a simple but powerful technique: we obtain an upper bound of $\lambda \geq 1$ on the price of anarchy if we manage to give a splitting $\lambda_1 + \dots + \lambda_k = \lambda$ such that $\sum_{s=1}^k \lambda_s \cdot f(|s-p|) \geq f^*$ for all $p \in \{1,\dots,k\}$. The discovery of working splittings can be supported by computer experiments. We show how, once we have an idea what kind of splittings work, this technique helps in giving simple proofs, which mainly work by case distinctions, algebraic manipulations, and real calculus.

Abstract:
We study expansions of pseudodifferential operators from the Hörmander class in a special family of functions called brushlets. We prove that such operators have a sparse representation in a brushlet system. Using this sparsity, we show that a pseudodifferential operator extends to a bounded operator between α-modulation spaces. These spaces were introduced by Gröbner in [15]. They are, in some sense, intermediate spaces between the classical Besov and Modulation spaces.

Abstract:
A first principles thermodynamic model of sliding friction is derived. The model predictions are in agreement with the observed friction laws both in macro- and nanoscale. When applied to calculating the friction coefficient the model provides a quantitative agreement with recent atomic force microscopy measurements on a number of materials.