Abstract: In large-scale or evolving networks, such as the Internet,
there is no authority possible to enforce a centralized traffic management.
In such situations, Game Theory and the concepts of Nash equilibria
and Congestion Games [8] are a suitable framework for analyzing
the equilibrium effects of selfish routes selection to network delays.
We focus here on layered networks where selfish users select paths to
route their loads (represented by arbitrary integer weights). We assume
that individual link delays are equal to the total load of the link. We
focus on the algorithm suggested in [2], i.e. a potential-based method
for finding pure Nash equilibria (PNE) in such networks. A superficial
analysis of this algorithm gives an upper bound on its time which is
polynomial in n (the number of users) and the sum of their weights. This
bound can be exponential in n when some weights are superpolynomial.
We provide strong experimental evidence that this algorithm actually
converges to a PNE in strong polynomial time in n (independent of the
weights values). In addition we propose an initial allocation of users
to paths that dramatically accelerates this algorithm, compared to an
arbitrary initial allocation. A by-product of our research is the discovery
of a weighted potential function when link delays are exponential to their
loads. This asserts the existence of PNE for these delay functions and
extends the result of

Abstract: Distributed algorithm designers often assume that system processes execute the same predefined software. Alternatively, when they do not assume that, designers turn to non-cooperative games and seek an outcome that corresponds to a rough consensus when no coordination is allowed. We argue that both assumptions are inapplicable in many real distributed systems, e.g., the Internet, and propose designing self-stabilizing and Byzantine fault-tolerant distributed game authorities. Once established, the gameauthority can secure the execution of any complete information game. As a result, we reduce costs that are due to the processes˘ freedom of choice. Namely, we reduce the price of malice.

Abstract: Distributed algorithm designers often assume that system processes execute the same predefined software. Alternatively, when they do not assume that, designers turn to non-cooperative games and seek an outcome that corresponds to a rough consensus when no coordination is allowed. We argue that both assumptions are inapplicable in many real distributed systems, e.g., the Internet, and propose designing self-stabilizing and Byzantine fault-tolerant distributed game authorities. Once established, the gameauthority can secure the execution of any complete information game. As a result, we reduce costs that are due to the processes˘ freedom of choice. Namely, we reduce the price of malice.