| Résumé | We study path coloring games that describe situations in which
selfish entities possess communication requests in a multifiber
all-optical network. Each player is charged according to the maximum fiber
multiplicity that her color (wavelength) choice incurs and the social cost
is the maximum player cost. We investigate the price of anarchy of such
games and provide two different upper bounds for general graphs---namely
the number of wavelengths and the minimum length of a path of maximum
disutility, over all worst-case Nash Equilibria---as well as matching
lower bounds which hold even for trees. We also prove constant bounds for
the price of anarchy in chains and rings in which the number of
wavelengths is relatively small compared to the load of the network; in
the opposite case we show that the price of anarchy can be unbounded.
This is joint work with Aris Pagourtzis, George Pierrakos, and Katerina Potika. |