**Reference**:- Erik D. Demaine and Morteza Zadimoghaddam, “Constant Price of Anarchy in Network-Creation Games via Public-Service Advertising”,
*Internet Mathematics*, volume 8, number 1–2, 2012, pages 29–45. **Abstract**:-
Network creation games have been studied in many different settings recently.
These games are motivated by social networks in which selfish agents want to
construct a connection graph among themselves. Each node wants to minimize
its average or maximum distance to the others, without paying much to
construct the network. Many generalizations have been considered, including
non-uniform interests between nodes, general graphs of allowable edges,
bounded budget agents, etc. In all of these settings, there is no known
constant bound on the price of anarchy. In fact, in many cases, the price of
anarchy can be very large, namely, a constant power of the number of agents.
This means that we have no control on the behavior of network when agents act
selfishly. On the other hand, the price of stability in all these models is
constant, which means that there is chance that agents act selfishly and we
end up with a reasonable social cost.
In this paper, we show how to use an advertising campaign (as introduced in SODA 2009 [2]) to find such efficient equilibria in (

*n*,*k*)*-uniform bounded budget connection*game [10]; our result holds for*k*= ω(log(*n*)). More formally, we present advertising strategies such that, if an α fraction of the agents agree to cooperate in the campaign, the social cost would be at most*O*(1/α) times the optimum cost. This is the first constant bound on the price of anarchy that interestingly can be adapted to different settings. We also generalize our method to work in cases that α is not known in advance. Also, we do not need to assume that the cooperating agents spend all their budget in the campaign; even a small fraction (β fraction) of their budget is sufficient to obtain a constant price of anarchy. **Comments**:- This paper is also available from Taylor & Francis Online.
**Copyright**:- Copyright held by the authors.
**Availability**:- The paper is available in PostScript (315k) and PDF (312k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- NetworkCreationAdvertising_WAW2010 (Constant Price of Anarchy in Network Creation Games via Public Service Advertising)

See also other papers by Erik Demaine.

Last updated May 16, 2024 by Erik Demaine.