Show simple item record

dc.contributor.authorElsässer, R.en
dc.contributor.authorGairing, M.en
dc.contributor.authorLücking, T.en
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorMonien, Burkharden
dc.creatorElsässer, R.en
dc.creatorGairing, M.en
dc.creatorLücking, T.en
dc.creatorMavronicolas, Mariosen
dc.creatorMonien, Burkharden
dc.description.abstractIn this work, we introduce and study a simple, graph-theoretic model for selfish scheduling among m non-cooperative users over a collection of n machinesen
dc.description.abstracthowever, 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 Ω (log n/log log n). 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. © Springer-Verlag Berlin Heidelberg 2005.en
dc.source1st International Workshop on Internet and Network Economics, WINE 2005en
dc.subjectMathematical modelsen
dc.subjectMeasurement theoryen
dc.subjectTheorem provingen
dc.subjectGraph theoryen
dc.subjectBounded interactionsen
dc.subjectCoordinate measuring machinesen
dc.subjectGraph-theoretic modelen
dc.subjectNon-cooperative usersen
dc.subjectRestricted schedulingen
dc.titleA simple graph-theoretic model for selfish restricted schedulingen
dc.description.volume3828 LNCSen
dc.description.endingpage209 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Conference code: 67467en
dc.description.notesCited By :4</p>en
dc.source.abbreviationLect. Notes Comput. Sci.en

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record