Search

Motivation-Framework. Apparently, it is in human’s nature to act selfishly. Game Theory, founded by von Neumann and Morgenstern [39, 40], provides us with strategic games, an important mathematical model to describe and analyze such a selfish behavior and its resulting conflicts. In a strategic game, each of a finite set of players aims for an optimal value of its private objective function by choosing either a pure strategy (a single strategy) or a mixed strategy (a probability distribution over all pure strategies) from its strategy set. Strategic games in which the strategy sets are finite are called finite strategic games. Each player chooses its strategy once and for all, and all players’ choices are made non-cooperatively and simultaneously (that is, when choosing a strategy each player is not informed of the strategies chosen by any other player). One of the basic assumption in strategic games is that the players act rational, that is, consistently in pursuit of their private objective function. For a concise introduction to contemporary Game Theory we recommend [25]. [ABSTRACT FROM AUTHOR]

In this work, we introduce and study a simple, graph-theoretic model for selfish scheduling among m non-cooperative users over a collection of nmachines; however, each user is restricted to assign its unsplittable load to one from a pair of machines that are allowed for the user. We model these bounded interactions using an interaction graph, whose vertices and edges are the machines and the users, respectively. We study the impact of our modeling assumptions on the properties of Nash equilibria in this new model. The main findings of our study are outlined as follows: - We prove, as our main result, that the parallel links graph is the best-case interaction graph - the one that minimizes expected makespan of the standard fully mixed Nash equilibrium - among all 3-regular interaction graphs. The proof employs a graph-theoretic lemma about orientations in 3-regular graphs, which may be of independent interest. - We prove a lower bound on Coordination Ratio[16] - a measure of the cost incurred to the system due to the selfish behavior of the users. In particular, we prove that there is an interaction graph incurring Coordination Ratio . This bound is shown for pure Nash equilibria. - We present counterexample interaction graphs to prove that a fully mixed Nash equilibrium may sometimes not exist at all. Moreover, we prove properties of the fully mixed Nash equilibrium for complete bipartite graphs and hypercube graphs. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling a given flow on a synchronous distributed network. This problem arises using diffusion-based approaches to compute a balancing flow, which has to be scheduled afterwards. We show that every distributed scheduling strategy requires at least 3/2 times the minimum number of rounds. Furthermore we give a distributed algorithm for flows on tree networks, which requires at most two times the optimal number of rounds. [ABSTRACT FROM AUTHOR]

The Euclidean Algorithm was first documented by Euclid (320-275 BC). Knuth (1981), p. 318, writes: "We might call it the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day." It performs division with remainder repeatedly until the remainder becomes zero. With inputs 13 and 9 it performs the following: This allows us to compute the greatest common divisor (gcd) of two integers as the last non-vanishing remainder. In the example, the gcd of 13 and 9 is computed as 1. [ABSTRACT FROM AUTHOR]