You are an expert at summarizing long articles. Proceed to summarize the following text: 
due to the increasing use of wireless technology in communication networks , there has been a significant amount of research on methods of improving wireless performance . while there are many ways of measuring wireless performance , a good first step ( which has been extensively studied ) is the notion of _ capacity_. given a collection of communication links , the capacity of a network is simply the maximum number of simultaneously satisfiable links . this can obviously depend on the exact model of wireless communication that we are using , but is clearly an upper bound on the  usefulness " of the network . there has been a large amount of research on analyzing the capacity of wireless networks ( see e.g.  @xcite ) , and it has become a standard way of measuring the quality of a network . because of this , when introducing a new technology it is interesting to analyze its affect on the capacity . for example , we know that in certain cases giving transmitters the ability to control their transmission power can increase the capacity by @xmath4 or @xmath7 @xcite , where @xmath1 is the ratio of the longest link length to the smallest transmitter - receiver distance , and can clearly never decrease the capacity . however , while the capacity might improve , it is not nearly as clear that the _ achieved _ capacity will improve . after all , we do not expect our network to actually have performance that achieves the maximum possible capacity . we show that not only might these improved technologies not help , they might in fact _ decrease _ the achieved network capacity . following andrews and dinitz  @xcite and sgeirsson and mitra  @xcite , we model each link as a self - interested agent and analyze various types of game - theoretic behavior ( nash equilibria and no - regret behavior in particular ) . we show that a version of _ braess s paradox _ @xcite holds : adding new technology to the networks ( such as the ability to control powers ) can actually decrease the average capacity at equilibrium . our main results show that in the context of wireless networks , and particularly in the context of the sinr model , there is a version of _ braess s paradox _  @xcite . in his seminal paper , braess studied congestion in road networks and showed that adding additional roads to an existing network can actually make congestion _ worse _ , since agents will behave selfishly and the additional options can result in worse equilibria . this is completely analogous to our setting , since in road networks adding extra roads can not hurt the network in terms of the value of the optimum solution , but can hurt the network since the _ achieved _ congestion gets worse . in this work we consider the physical model ( also called the sinr model ) , pioneered by moscibroda and wattenhofer  @xcite and described more formally in section  [ sec : models ] . intuitively , this model works as follows : every sender chooses a transmission power ( which may be pre - determined , e.g.  due to hardware limitations ) , and the received power decreased polynomially with the distance from the sender . a transmission is successful if the received power from the sender is large enough to overcome the interference caused by other senders plus the background noise .    with our baseline being the sinr model , we then consider four ways of  improving " a network : adding power control , adding interference cancellation , adding both power control and interference cancellation , and decreasing the sinr threshold . with all of these modifications it is easy to see that the optimal capacity can only increase , but we will show that the equilibria can become worse . thus  improving " a network might actually result in worse performance .    the game - theoretic setup that we use is based on  @xcite and will be formally described in section  [ sec : game - theory ] , but we will give an overview here . we start with a game in which the players are the links , and the strategies depend slightly on the model but are essentially possible power settings at which to transmit . the utilities depend on whether or not the link was successful , and whether or not it even attempted to transmit . in a pure nash equilibrium every player has a strategy ( i.e.  power setting ) and has no incentive to deviate : any other strategy would result in smaller utility . in a mixed nash equilibrium every link has a probability distribution over the strategies , and no link has any incentive to deviate from their distribution . finally , no - regret behavior is the empirical distribution of play when all players use _ no - regret _ algorithms , which are a widely used and studied class of learning algorithms ( see section  [ sec : game - theory ] for a formal definition ) . it is reasonably easy to see that any pure nash is a mixed nash , and any mixed nash is a no - regret behavior . for all of these , the quality of the solution is the achieved capacity , i.e.  the average number of successful links . our first result is for interference cancellation ( ic ) , which has been widely proposed as a practical method of increasing network performance  @xcite . the basic idea of interference cancellation is quite simple . first , the strongest interfering signal is detected and decoded . once decoded , this signal can then be subtracted (  canceled " ) from the original signal . subsequently , the next strongest interfering signal can be detected and decoded from the now  cleaner " signal , and so on . as long as the strongest remaining signal can be decoded in the presence of the weaker signals , this process continues until we are left with the desired transmitted signal , which can now be decoded . this clearly can increase the capacity of the network , and even in the worst case can not decrease it . and yet due to bad game - theoretic interactions it might make the achieved capacity worse :    [ thm : ic - intro ] there exists a set of links in which the _ best _ no - regret behavior under interference cancellation achieves capacity at most @xmath8 times the _ worst _ no - regret behavior without interference cancellation , for some constant @xmath9 . however , for every set of links the worst no - regret behavior under interference cancellation achieves capacity that is at least a constant fraction of the best no - regret behavior without interference cancellation . thus ic can make the achieved capacity worse , but only by a constant factor . note that since every nash equilibrium ( mixed or pure ) is also no - regret , this implies the equivalent statements for those type of equilibria as well . in this result ( as in most of our examples ) we only show a small network ( @xmath10 links ) with no background noise , but these are both only for simplicity  it is easy to incorporate constant noise , and the small network can be repeated at sufficient distance to get examples with an arbitrarily large number of links . we next consider power control ( pc ) , where senders can choose not just whether to transmit , but at what power to transmit . it turns out that any equilibrium without power control is also an equilibrium with power control , and thus we can not hope to find an example where the best equilibrium with power control is worse than the worst equilibrium without power control ( as we did with ic ) . instead , we show that adding power control can create worse equilibria :    [ thm : pc - intro ] there exists a set of links in which there is a pure nash equilibrium with power control of value at most @xmath8 times the value of the worst no - regret behavior without power control , for some constant @xmath9 . however , for every set of links the worst no - regret behavior with power control has value that is at least a constant fraction of the value of the _ best _ no - regret behavior without power control . note that the first part of the theorem implies that not only is there a pure nash with low - value ( with power control ) , there are also mixed nash and no - regret behaviors with low value ( since any pure nash is also mixed and no - regret ) . similarly , the second part of the theorem gives a bound on the gap between the worst and the best mixed nashes , and the worst and the best pure nashes . our third set of results is on the combination of power control and interference cancellation . it turns out that the combination of the two can be quite harmful . when compared to either the vanilla setting ( no interference cancellation or power control ) or the presence of power control without interference cancellation , the combination of ic and pc acts essentially as in theorem  [ thm : pc - intro ] : pure nash equilibria are created that are worse than the previous worst no - regret behavior , but this can only be by a constant factor . on the other hand , this factor can be super - constant when compared to equilibria that only use interference cancellation . let @xmath1 be the ratio of the length of the longest link to the minimum distance between any sender and any receiver . there exists a set of links in which the worst pure nash with both pc and ic ( and thus the worst mixed nash or no - regret behavior ) has value at most @xmath11 times the value of the worst no - regret behavior with just ic . however , for every set of links the worst no - regret behavior with both pc and ic has value at least @xmath12 times the value of the best no - regret behavior with just ic . this theorem means that interference cancellation  changes the game " : if interference control were not an option then power control can only hurt the equilibria by a constant amount ( from theorem  [ thm : pc - intro ] ) , but if we assume that interference cancellation is present then adding power control can hurt us by @xmath4 . thus when deciding whether to use both power control and interference cancellation , one must be particularly careful to analyze how they act in combination . finally , we consider the effect of decreasing the sinr threshold @xmath3 ( this value will be formally described in section  [ sec : models ] ) . we show that , as with ic , there are networks in which a decrease in the sinr threshold can lead to _ every _ equilibrium being worse than even the worst equilibrium at the higher threshold , despite the capacity increasing or staying the same :    there exists a set of links and constants @xmath13 in which the best no - regret behavior under threshold @xmath14 has value at most @xmath8 times the value of the worst no - regret behavior under threshold @xmath3 , for some constant @xmath9 . however , for any set of links and any @xmath13 the value of the worst no - regret behavior under @xmath14 is at least a constant fraction of the value of the best no - regret behavior under @xmath3 . our main network constructions illustrating braess s paradox in the studied settings are summarized in fig . [ fig : nash_all ] .     schematic illustration of the main lower bounds illustrating the braess s paradox with ( a ) ic : a network in which every no - regret behavior without ic is better than any no - regret behavior solution with ic ; ( b ) pc : a network in which there exists a pure nash equilibrium with pc which is worse than any no - regret behavior with ic ; ( c ) pic : a network with a pure nash equilibrium in the pic setting which is @xmath4 worse than any no - regret behavior in the ic setting but _ without _ power control ; and ( d ) decreased sinr threshold @xmath15 : a network in which every no - regret behavior with @xmath14 has a smaller value than any no - regret behavior with higher sinr threshold @xmath3 . edge weights represent distances . , title="fig : " ]   schematic illustration of the main lower bounds illustrating the braess s paradox with ( a ) ic : a network in which every no - regret behavior without ic is better than any no - regret behavior solution with ic ; ( b ) pc : a network in which there exists a pure nash equilibrium with pc which is worse than any no - regret behavior with ic ; ( c ) pic : a network with a pure nash equilibrium in the pic setting which is @xmath4 worse than any no - regret behavior in the ic setting but _ without _ power control ; and ( d ) decreased sinr threshold @xmath15 : a network in which every no - regret behavior with @xmath14 has a smaller value than any no - regret behavior with higher sinr threshold @xmath3 . edge weights represent distances . , title="fig : " ]   schematic illustration of the main lower bounds illustrating the braess s paradox with ( a ) ic : a network in which every no - regret behavior without ic is better than any no - regret behavior solution with ic ; ( b ) pc : a network in which there exists a pure nash equilibrium with pc which is worse than any no - regret behavior with ic ; ( c ) pic : a network with a pure nash equilibrium in the pic setting which is @xmath4 worse than any no - regret behavior in the ic setting but _ without _ power control ; and ( d ) decreased sinr threshold @xmath15 : a network in which every no - regret behavior with @xmath14 has a smaller value than any no - regret behavior with higher sinr threshold @xmath3 . edge weights represent distances . , title="fig : " ]   schematic illustration of the main lower bounds illustrating the braess s paradox with ( a ) ic : a network in which every no - regret behavior without ic is better than any no - regret behavior solution with ic ; ( b ) pc : a network in which there exists a pure nash equilibrium with pc which is worse than any no - regret behavior with ic ; ( c ) pic : a network with a pure nash equilibrium in the pic setting which is @xmath4 worse than any no - regret behavior in the ic setting but _ without _ power control ; and ( d ) decreased sinr threshold @xmath15 : a network in which every no - regret behavior with @xmath14 has a smaller value than any no - regret behavior with higher sinr threshold @xmath3 . edge weights represent distances . , title="fig : " ]      the capacity of _ random _ networks was examined in the seminal paper of gupta and kumar  @xcite , who proved tight bounds in a variety of models . but only recently has there been a significant amount of work on algorithms for determining the capacity of _ arbitrary _ networks , particularly in the sinr model . this line of work began with goussevskaia , oswald , and wattenhofer  @xcite , who gave an @xmath6-approximation for the uniform power setting ( i.e.  the vanilla model we consider ) . goussevskaia , halldrson , wattenhofer , and welzl  @xcite then improved this to an @xmath5-approximation ( still under uniform powers ) , while andrews and dinitz  @xcite gave a similar @xmath6-approximation algorithm for the power control setting . this line of research was essentially completed by an @xmath5-approximation for the power control setting due to kesselheim  @xcite .    in parallel to the work on approximation algorithms , there has been some work on using game theory ( and in particular the games used in this paper ) to help design distributed approximation algorithms . this was begun by andrews and dinitz  @xcite , who gave an upper bound of @xmath16 on the price of anarchy for the basic game defined in section  [ sec : game - theory ] . but since computing the nash equilibrium of a game is ppad - complete  @xcite , we do not expect games to necessarily converge to a nash equilibrium in polynomial time . thus dinitz  @xcite strengthened the result by showing the same upper bound of @xmath16 for no - regret behavior . this gave the first distributed algorithm with a nontrivial approximation ratio , simply by having every player use a no - regret algorithm . the analysis of the same game was then improved to @xmath6 by sgeirsson and mitra  @xcite . there is very little work on interference cancellation in arbitrary networks from an algorithmic point of view , although it has been studied quite well from an information - theoretic point of view ( see e.g.  @xcite ) . recently avin et al . @xcite studied the topology of _ sinr diagrams _ under interference cancellation , which are a generalization of the sinr diagrams introduced by avin et al . @xcite and further studied by kantor et al . @xcite for the sinr model without interference cancellation . these diagrams specify the reception zones of transmitters in the sinr model , which turn out to have several interesting topological and geometric properties but have not led to a better understanding of the fundamental capacity question . we model a wireless network as a set of links @xmath17 in the plane , where each link @xmath18 represents a communication request from a sender @xmath19 to a receiver @xmath20 . the @xmath21 senders and receivers are given as points in the euclidean plane . the euclidean distance between two points @xmath22 and @xmath23 is denoted @xmath24 . the distance between sender @xmath25 and receiver @xmath26 is denoted by @xmath27 . we adopt the physical model ( sometime called the sinr model ) where the received signal strength of transmitter @xmath25 at the receiver @xmath26 decays with the distance and it is given by @xmath28 , where @xmath29 $ ] is the transmission power of sender @xmath25 and @xmath30 is the path - loss exponent . receiver @xmath26 successfully receives a message from sender @xmath31 iff @xmath32 , where @xmath33 denotes the amount of background noise and @xmath34 denotes the minimum sinr required for a message to be successfully received . the _ total interference _ that receiver @xmath26 suffers from the set of links @xmath35 is given by @xmath36 . throughout , we assume that all distances @xmath27 are normalized so that @xmath37 hence the maximal link length is @xmath1 , i.e. , @xmath38 and any received signal strength @xmath39 is bounded by @xmath40 . in the vanilla sinr model we require that @xmath41 is either @xmath42 or @xmath2 for every transmitter . this is sometimes referred to as _ uniform _ powers . when we have power control , we allow @xmath41 to be any integer in @xmath43 $ ] . interference cancellation allows receivers to cancel signals that they can decode . consider link @xmath44 . if @xmath26 can decode the signal with the largest received signal , then it can decode it and remove it . it can repeat this process until it decodes its desire message from @xmath31 , unless at some point it gets stuck and can not decode the strongest signal . formally , @xmath26 can decode @xmath25 if @xmath45 ( i.e.  it can decode @xmath25 in the presence of weaker signals ) and if it can decode @xmath46 for all links @xmath47 with @xmath48 . link @xmath44 is successful if @xmath26 can decode @xmath31 . the following key notion , which was introduced in  @xcite and extended to arbitrary powers by @xcite , plays an important role in our analysis . the _ affectance _ @xmath49 of link @xmath50 caused by another link @xmath51 with a given power assignment vector @xmath52 is defines to be @xmath53 , where @xmath54 . informally , @xmath49 indicates the amount of ( normalized ) interference that link @xmath51 causes at link @xmath50 . it is easy to verify that link @xmath50 is successful if and only if @xmath55 . when the powers of @xmath52 are the same @xmath56 for every @xmath57 , ( i.e.  uniform powers ) , we may omit it and simply write @xmath58 . for a set of links @xmath35 and a link @xmath51 , the total affectance caused by @xmath51 is @xmath59 . in the same manner , the total affectance caused by @xmath35 on the link @xmath51 is @xmath60 . we say that a set of links @xmath35 is _ @xmath3-feasible _ if @xmath61 for all @xmath62 , i.e.  every link achieves sinr above the threshold ( and is thus successful even without interference cancellation ) . it is easy to verify that @xmath35 is @xmath3-feasible if and only if @xmath63 for every @xmath62 . following @xcite , we say that a link set @xmath35 is _ amenable _ if the total affectance caused by any single link is bounded by some constant , i.e. , @xmath64 for every @xmath65 . the following basic properties of amenable sets play an important role in our analysis . @xcite [ fc : amenable ] ( a ) every feasible set @xmath35 contains a subset @xmath66 , such that @xmath67 is amenable and @xmath68 . + ( b ) for every amenable set @xmath67 that is @xmath3-feasible with uniform powers , for every other link @xmath69 , it holds that @xmath70 .      we will use a game that is essentially the same as the game of andrews and dinitz  @xcite , modified only to account for the different models we consider . each link @xmath71 is a player with @xmath72 possible strategies : broadcast at power @xmath42 , or at integer power @xmath73 . a link has utility @xmath74 if it is successful , has utility @xmath75 if it uses nonzero power but is unsuccessful , and has utility @xmath42 if it does not transmit ( i.e.  chooses power @xmath42 ) . note that if power control is not available , this game only has two strategies : power @xmath42 and power @xmath2 . let @xmath76 denote the set of possible strategies . strategy profile _ is a vector in @xmath77 , where the @xmath78th component is the strategy played by link @xmath71 . for each link @xmath71 , let @xmath79 be the function mapping strategy profiles to utility for link @xmath78 as described . given a strategy profile @xmath80 , let @xmath81 denote the profile without the @xmath78th component , and given some strategy @xmath82 let @xmath83 denote the utility of @xmath71 if it uses strategy @xmath84 and all other links use their strategies from @xmath80 . a pure nash equilibrium is a strategy profile in which no player has any incentive to deviate from their strategy . formally , @xmath85 is a pure nash equilibrium if @xmath86 for all @xmath82 and players @xmath87 . in a mixed nash equilibrium  @xcite , every player @xmath71 has a probability distribution @xmath88 over @xmath76 , and the requirement is that no player has any incentive to change their distribution to some @xmath89 . so @xmath90 \geq { \mathop{\mathbb e}}[f_i(\pi ' , a_{-i})]$ ] for all @xmath91 , where the expectation is over the random strategy profile @xmath80 drawn from the product distribution defined by the @xmath88 s , and @xmath89 is any distribution over @xmath76 .    to define no - regret behavior , suppose that the game has been played for @xmath92 rounds and let @xmath93 be the realized strategy profile in round @xmath94 . the _ history _ @xmath95 of the game is the sequence of the @xmath92 strategy profiles . the _ regret _ @xmath96 of player @xmath78 in an history @xmath97 is defined to be @xmath98 the regret of a player is intuitively the amount that it lost by not playing some fixed strategy . an algorithm used by a player is known as a _ no - regret _ algorithm if it guarantees that the regret of the player tends to @xmath42 as @xmath92 tends to infinity . there is a large amount of work on no - regret algorithms , and it turns out that many such algorithms exist ( see e.g.  @xcite ) . thus we will analyze situations where every player has regret at most @xmath99 , and since this tends to @xmath42 we will be free to assume that @xmath99 is arbitrarily small , say at most @xmath100 . clearly playing a pure or mixed nash is a no - regret algorithm ( since the fact that no one has incentive to switch to any other strategy guarantees that each player will have regret @xmath42 in the long run ) , so analyzing the worst or best history with regret at most @xmath99 is more general than analyzing the worst or best mixed or pure nash . we will call a history in which all players have regret at most @xmath99 an @xmath99-regret history . formally an history @xmath95 is an @xmath99-_regret _ history if @xmath101 for every player @xmath91 . a simple but important lemma introduced in  @xcite and used again in  @xcite relates the average number of _ attempted _ transmissions to the average number of _ successful _ transmissions . fix an @xmath99-regret history , let @xmath102 be the fraction of times in which @xmath69 successfully transmitted , and let @xmath103 be the fraction of times in which @xmath69 attempted to transmit . note that the average number of successful transmissions in a time slot is exactly @xmath104 , so it is this quantity which we will typically attempt to bound . the following lemma lets us get away with bounding the number of attempts instead . [ lem : attempts ] @xmath105  . [ [ notation ] ] notation : + + + + + + + + +    let @xmath35 be a fixed set of @xmath21 links embedded in @xmath106 . let @xmath107 denote the minimum number of successful links ( averaged over time ) in any @xmath99-regret history , and similarly let @xmath108 denote the maximum number of successful links ( averaged over time ) in any @xmath99-regret history . define @xmath109 , and @xmath110 similarly for the ic setting , @xmath111 and @xmath112 for the pc setting , and @xmath113 and @xmath114 for the setting with both pc and ic . finally , let @xmath115 , @xmath116 be for the corresponding values for the vanilla model when the sinr threshold is set to @xmath3 ( this is hidden in the previous models , but we pull it out in order to compare the effect of modifying @xmath3 ) .    while we will focus on comparing the equilibria of games utilizing different wireless technologies , much of the previous work on these games instead focuses on a single game and analyzes its equilibria with respect to opt , the maximum achievable capacity . the _ price of anarchy _ ( poa ) is the ratio of opt to the value of the worst mixed nash  @xcite , and the _ price of total anarchy _ ( pota ) is the ratio of opt to the value of the worst @xmath99-regret history  @xcite . clearly poa @xmath117 pota . while it is not our focus , we will prove some bounds on these values as corollaries of our main results . we begin by analyzing the effect on the equilibria of adding interference cancellation . we would expect that using ic would result equilibria with larger values , since the capacity of the network might go up ( and can certainly not go down ) . we show that this is not always the case : there are sets of links for which even the _ best _ @xmath99-regret history using ic is a constant factor worse than the _ worst _ @xmath99-regret history without using ic . [ thm : ic_lower ] there exists a set of links @xmath35 such that @xmath118 for some constant @xmath119 . let @xmath67 be the four link network depicted in figure  [ fig : nash_all](a ) , with @xmath120 and @xmath121 . we will assume that the threshold @xmath3 is equal to @xmath122 , the path - loss exponent @xmath123 is equal to @xmath124 , and the background noise @xmath125 ( none of these are crucial , but make the analysis simpler ) . let us first consider what happens without using interference cancellation . suppose each link has at most @xmath99-regret , and for link @xmath71 let @xmath126 denote the fraction of times at which @xmath25 attempted to transmit . it is easy to see that link @xmath74 will always be successful , since the received signal strength at @xmath127 is @xmath74 while the total interference is at most @xmath128 . since @xmath129 has at most @xmath99-regret , this implies that @xmath130 .    on the other hand , whenever @xmath131 transmits it is clear that link @xmath132 can not be successful , as its sinr is at most @xmath133 . so if @xmath134 transmitted every time it would have average utility at most @xmath135 ( since @xmath136 ) , while if it never transmitted it would have average utility @xmath42 . thus its average utility is at least @xmath137 . since it can succeed only an @xmath99 fraction of the time ( when link @xmath74 is not transmitting ) , we have that @xmath138 and thus @xmath139 . since the utility of @xmath134 is at least @xmath137 , it holds that the fraction of times at which both @xmath131 and @xmath134 are transmitting is at most @xmath140 .    now consider link @xmath141 . if links @xmath129 and @xmath132 both transmit , then @xmath141 will fail since the received sinr will be at most @xmath142 . on the other hand , as long as link @xmath132 does not transmit then @xmath141 will be successful , as it will have sinr at least @xmath143 . thus by transmitting at every time step @xmath141 would have average utility at least @xmath144 ( since @xmath145 ) , and thus we know that @xmath141 gets average utility of at least @xmath146 , and thus successfully transmits at least @xmath146 fraction of the times . @xmath147 is the same by symmetry . thus the total value of any history in which all links have regret at most @xmath99 is at least @xmath148 . let us now analyze what happens when using interference cancellation and bound @xmath149 . suppose each link has at most @xmath99-regret , and for link @xmath71 let @xmath150 denote the fraction of times at which @xmath25 attempted to transmit . as before , @xmath129 can always successfully transmit and thus does so in at least @xmath151 fraction of times . but now , by using interference cancellation it turns out that @xmath132 can also always succeed . this is because @xmath152 can first decode the transmission from @xmath131 and cancel it , leaving a remaining sinr of at least @xmath153 . thus @xmath132 will also transmit in at least @xmath151 fraction of times and hence so far @xmath154 . note that since @xmath155 , it holds that @xmath156 can not cancel @xmath131 or @xmath134 before decoding @xmath157 ( i.e. , @xmath158 ) . hence , cancellation is useless . but now at @xmath156 the strength of @xmath131 is @xmath159 , the strength of @xmath134 is @xmath160 , and the strength of @xmath157 is @xmath161 . thus @xmath156 can not decode any messages when @xmath162 , and @xmath157 are all transmitting since its sinr is at most @xmath163 , which implies that @xmath141 can only succeed on at most @xmath140 fraction of times . the link @xmath147 is the same as the link @xmath141 by symmetry . thus the total value of any history in which all links have an @xmath99-regret is at most @xmath164 . thus @xmath165 as required . it turns out that no - regret behavior with interference cancellation can not be much worse than no - regret behavior without interference cancellation  as in braess s paradox , it can only be worse by a constant factor . [ thm : nash_ic_upper ] @xmath166 for any set of links @xmath35 and some constant @xmath167 . consider an @xmath99-regret history without ic that maximizes the average number of successful links , i.e.  one that achieves @xmath108 value . let @xmath126 denote the fraction of times at which @xmath25 attempted to transmit in this history , so @xmath168 by lemma  [ lem : attempts ] . similarly , let @xmath150 denote that fraction of times at which @xmath25 attempted to transmit in an @xmath99-regret history _ with _ ic that achieves value of only @xmath169 , and so @xmath170 . note that since the best average number of successful connections in the non - ic case is @xmath108 , there must exist some set of connections @xmath171 such that @xmath172 and @xmath173 is feasible without ic . let @xmath174 and let @xmath175 . if @xmath176 then we are done , since then @xmath177 as required . so without loss of generality we will assume that @xmath178 , and thus that @xmath179 . note that @xmath180 is a subset of @xmath173 , and so it is feasible in the non - ic setting . now let @xmath181 be an amenable subset of @xmath180 . by fact [ fc : amenable](a ) , it holds that @xmath182 . fact [ fc : amenable](b ) then implies that for any link @xmath183 , its total affectance on @xmath173 is small : @xmath184 for some constant @xmath185 . thus we have that @xmath186    on the other hand , we know that the @xmath150 values correspond to the worst history in which every link has regret at most @xmath99 ( in the ic setting ) . let @xmath187 . then @xmath188 , which means the average utility of link @xmath44 is at most @xmath189 . let @xmath190 be the fraction of time @xmath31 would have succeeded had it transmitted in every round . since the average utility of the best single action is at most @xmath191 it holds that @xmath192 or the that @xmath193 . in other words , in at least @xmath194 fraction of the rounds the affectance of the other links on the link @xmath44 must be at least @xmath74 ( or else @xmath195 could succeed in those rounds even without using ic ) . thus the expected affectance ( taken over a random choice of time slot ) on @xmath44 is at least @xmath196 . summing over all @xmath197 , we get that @xmath198    combining equations  ( [ eq : ic1 ] ) and  ( [ eq : ic2 ] ) ( and switching the order of summations ) implies that @xmath199 . since @xmath200 , we get that @xmath201 as desired .    as a simple corollary , we will show that this lets us bound the price of total anarchy in the interference cancellation model ( which , as far as we know , has not previously been bounded ) . let @xmath202 denote some optimal solution without ic , i.e. , the set of transmitters forming a maximum @xmath3-feasible set , and let @xmath203 denote some optimal solution with ic . [ cor : nash_ic_approx ] for every set of links @xmath35 it holds that the price of total anarchy with ic is @xmath6 , or @xmath204 . in the power control setting , each transmitter @xmath19 either broadcasts at power @xmath42 or broadcasts at some arbitrary integral power level @xmath205 $ ] . our main claim is that braess s paradox is once again possible : there are networks in which adding power control can create worse equilibria . for illustration of such a network , [ fig : nash_all](b ) . we first observe the following relation between no - regret solutions with or without power control . [ obs : nash_pc_contain ] every no - regret solution in the uniform setting , is also a no - regret solution in the pc setting . hence , we can not expect the best no - regret solution in the pc setting to be smaller than the worst no - regret solution in the uniform setting . yet , the paradox still holds . [ thm : pmax_nash_lb ] there exists a configuration of links @xmath35 satisfying @xmath206 for some constant @xmath207 . we now prove that ( as with ic ) that the paradox can not be too bad : adding power control can not cost us more than a constant . the proof is very similar to that of thm . [ thm : nash_ic_upper ] up to some minor yet crucial modifications . [ thm : nash_pc_upper ] @xmath208 for any set of links @xmath35 and some constant @xmath167 . [ cor : pmax_price ] the price of total anarchy under the power control setting with maximum transmission energy @xmath2 is @xmath209 . in this section we consider games in the power control with ic setting where _ transmitters _ can adopt their transmission energy in the range of @xmath210 $ ] and in addition , _ receivers _ can employ interference cancelation . this setting is denote as @xmath211 ( power control+ic ) . we show that braess s paradox can once again happen and begin by comparing the pic setting to the setting of power control without ic and to the most basic setting of uniform powers . [ lemma : pic_pcunilower ] there exists a set of links @xmath35 and constant @xmath207 such that + ( a ) @xmath212 . + ( b ) @xmath213 . +    moreover , we proceed by showing that pic can hurt the network by more than a constant when comparing pic equilibria to ic equilibria . for an illustration of such a network , [ fig : nash_all](c ) . [ theorem : ic_pc_lower ] there exists a set of links @xmath35 and constant @xmath207 such that the best pure nash solution with pic is worse by a factor of @xmath4 than the worst no - regret solution with ic . there exists a set of links @xmath35 satisfying that @xmath214 .    as in the previous sections , we show that our examples are essentially tight . [ lem : nash_ic_pc_upper ] for every set of links @xmath35 it holds that there exists a constant @xmath215 such that + ( a ) @xmath216 . + ( b ) @xmath217 . + ( c ) @xmath218 .    finally , as a direct consequences of our result , we obtain a tight bound for the price of total anarchy in the pic setting . [ cor : pic_price ] for every set of links @xmath35 it holds that the price of total anarchy with pic is @xmath219 . we begin by showing that in certain cases the ability to successfully decode a message at a lower sinr threshold results in _ every _ no - regret solution having lower value than _ any _ no - regret solution at higher @xmath3 . for an illustration of such a network , [ fig : nash_all](d ) . [ thm : beta_nash_lb ] there exists a set of links @xmath35 and constants @xmath13 such that @xmath220 for some constant @xmath207 . we now show that the gap between the values of no - regret solution for different sinr threshold values is bounded by a constant . [ lem : beta_nash_lb ] for every @xmath221 and every set of links @xmath35 satisfying that @xmath222 for every @xmath62 , it holds that @xmath223 for some constant @xmath215 . in this paper we have shown that braess s paradox can strike in wireless networks in the sinr model : improving technology can result in worse performance , where we measured performance by the average number of successful connections . we considered adding power control , interference cancellation , both power control and interference cancellation , and decreasing the sinr threshold , and in all of them showed that game - theoretic equilibria can get worse with improved technology . however , in all cases we bounded the damage that could be done . there are several remaining interesting open problems . first , what other examples of wireless technology exhibit the paradox ? second , even just considering the technologies in this paper , it would be interesting to get a better understanding of when exactly the paradox occurs . can we characterize the network topologies that are susceptible ? is it most topologies , or is it rare ? what about random wireless networks ? finally , while our results are tight up to constants , it would be interesting to actually find tight constants so we know precisely how bad the paradox can be .
when comparing new wireless technologies , it is common to consider the effect that they have on the capacity of the network ( defined as the maximum number of simultaneously satisfiable links ) . 
 for example , it has been shown that giving receivers the ability to do interference cancellation , or allowing transmitters to use power control , never decreases the capacity and can in certain cases increase it by @xmath0 , where @xmath1 is the ratio of the longest link length to the smallest transmitter - receiver distance and @xmath2 is the maximum transmission power . 
 but there is no reason to expect the optimal capacity to be realized in practice , particularly since maximizing the capacity is known to be np - hard . in reality , we would expect links to behave as self - interested agents , and thus when introducing a new technology it makes more sense to compare the values reached at game - theoretic equilibria than the optimum values .    in this paper 
 we initiate this line of work by comparing various notions of equilibria ( particularly nash equilibria and no - regret behavior ) when using a supposedly  better " technology . 
 we show a version of braess s paradox for all of them : in certain networks , upgrading technology can actually make the equilibria _ worse _ , despite an increase in the capacity . 
 we construct instances where this decrease is a constant factor for power control , interference cancellation , and improvements in the sinr threshold ( @xmath3 ) , and is @xmath4 when power control is combined with interference cancellation . 
 however , we show that these examples are basically tight : the decrease is at most @xmath5 for power control , interference cancellation , and improved @xmath3 , and is at most @xmath6 when power control is combined with interference cancellation .