Effects of Symmetry on Paradoxes in Non-Cooperative Distributed Computing

Hisao Kameda () and Yoshihisa Hosokawa ()
Additional contact information
Hisao Kameda: University of Tsukuba, Institute of Information Sciences and Electronics
Yoshihisa Hosokawa: University of Tsukuba, Graduate School of Systems and Information Engineering

A chapter in ICM Millennium Lectures on Games, 2003, pp 373-390 from Springer

Abstract: Summary Distributed computer systems consist of nodes (hosts, computers), un­der which a communication follows from connected nodes. Jobs (or transactions) arrive at each node. Jobs can be forwarded through the communication means to other nodes for remote processing. We assume that there is a decision maker at each node who strives to optimize non-cooperatively the mean response time (the cost) for a job arriving at the node, by choosing the job-processing rate at the node and job forwarding rates. This is regards in a non-cooperative game. Numerical ex­amples of a Braess-like paradox in which the performance for all decision makers in the system in a Nash equilibrium is worse with a communication means than without it, have been reported. Unlike the original Braess paradox, this behavior occurs in the models examined only in the case of finitely many users (decision makers) and not in the case of infinitesimal users, and the degree of performance degradation can increase without bound. Examples are presented which show that against our previous intuition the Braess-like paradox is strongest, i. e. the degree of performance degradation of all users in the Brass-like paradox is highest, in the completely symmetrical system wherein the parameter values describing each user are identical.

Keywords: Braess paradox; cost optimization; distributed computer sys­tem; distributed decision; load balancing; Nash equilibrium; Pareto inefficiency; prisoners’ dilemma (search for similar items in EconPapers)
Date: 2003
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-662-05219-8_24

Ordering information: This item can be ordered from
http://www.springer.com/9783662052198

DOI: 10.1007/978-3-662-05219-8_24

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().