Hello, my name is Nikos Muzaykis and I'm going to present our paper titled Node MaxHets and Computer Equilibrium Linear Weighted Congestion Games. This is joint work with Imidse Fotakis,

Pardis Kandiros, Tanas Ljernais, Paneghis Pasilinakis and Satis Koulakis. A recurring problem in computer science is finding solutions to problems when the solution is somehow already guaranteed to exist. To capture the complexity of such problems, Megadot and Pathy material define the plexed class TFNP. In this class R contains all the class where a solution is somehow guaranteed

to exist and can be easily recognised. In fact, in such problems the theory of NP-completeness cannot help us, since we would be able to construct both YES and NO certificates for every NP-complete problem, meaning NP equals QNP and the subsequent polynomial hierarchy. The problems in TFNP are further categorized based on the combinatorial

principle that guarantees the existence of a solution. Since we are dealing with promised problems, it must be possible to recognize the title of a problem in polynomial time. The principles that guarantees such existence are diverse. More specifically, TFNP is divided

into the following classes. PBP captures problems where the existence is guaranteed by some sort of pin-zone-hole-collision principle. The class PPA contains problems related to the Hanseic lemma, while PPAD is at the section of these two classes and captures the difficulty of finding

bra-refix points. PLS captures the hardness of local search and finding local automa and equilibria. One of the most famous problems in TFNP is that of TAS, which is contained in PPAD and shown hard for this class. While that is one of its most celebrated results,

TFNP has done substantial active research in recent years, and researchers will find more and more connections to other selfish mathematics and computer science, and its ranks are constantly growing, with more and more complete problems or not added to it. In this talk we are going to focus on the class PLS,

where the existence is guaranteed by a proof-by-potential function. In this case, the solution required is usually a local minimizer of some potential, or can be found as a result of some local-sales algorithm, as its namesake implies.

Our problems in PLS can be equivalently viewed as a direct cycle graph where every solution corresponds to a vertex of that graph. Moreover, we require that the problem possesses some efficient neighborhood structure, so we can calculate the improving solution efficiently. An acceptable solution to our PLS problem is at least one of the things that are guaranteed

to exist in the graph. Some of the most celebrated problems contained in the PLS class include potential games, or also congestion games, as well as the local max-cut problem. Perhaps the simplest and most versatile example of PLS-complete problem is that of local max-cuts. In local max-cuts, we are given an edge-weighted graph, along with a neighborhood

improving function of flipping single vertex as long as it increases the value of the cut. In other words, we compromise, and instead of asking for the optimal cut with a known NP-hard problem, we compromise the task for a local optimum under the flip heuristic. For example, in this example, this node can change its partition and increase the cut,

and this process can repeat indefinitely, until the cut reaches its optimal value. This problem was in fact shown by Safarian and Kajkis to be PLS-complete,

meaning it is at least as hard as any other local search problem. Not only is it PLS-complete, but also its versatility and elegance has allowed multiple researchers to prove PLS-completeness based on local max-cut. It would not be a stress

to say that historically local max-cut has been to PLS, what SAT has been to NP. Another major category of problems that belong in PLS are congestion games. In a congestion game, we have a set of players and a set of resources. Players decide on a set of resources to use based on some set of strategies. Each player experiences a cost, which they want to

minimize. This cost is equal to some of the latencies they incur. For example, in the case of network congestion games, players want to traverse a graph at the same time. The more players using a net, the greater the latency they incur. In the case of network congestion

games or general congestion games, it was shown by Rosenthal that there exists a global potential function. This means that whenever a player improves his cost, there is some global quantity that increases by a commensurate amount. Effectively, this means that this

is a local search problem. To see this, one can consider the potential as the global function that each player takes third minimizing. Because of the existence of such a potential, this means that the existence of an ascolibrium is also guaranteed. It is in fact the existence

of this potential that places this problem in PLS and casts the local search problem. However, not only are congestion games contained within PLS, but they are also shown to be complete for this class, meaning they are at least as hard as any other local search optimization problem. The computation of a pure Nash equilibrium in this case was shown by Fabrik and

et al. and subsequently by Akker and et al. to be PLS hard. In the latter case, a reduction was made from MaxCAD to network congestion games in the case where players have multiple source and destinations, called a symmetric network congestion game. In the first work,

it was also shown that for the symmetric network case, a maximum flow-inspired algorithm can be employed to find a global minimizer of the potential, bypassing any sort of local search in polynomial time. A significant and important generalization of the previous model, which has been investigated a lot, is that of weighted consistent games. In this

setting, the players each have a different weight with which they contribute the latest function of each resource. To explain, each player can have their own weight, and there is a potential function on each resource or edge in a network-consistent game,

which determines based on the sum of the weights of the players using that resource, the latency of that edge. However, in this case, it is not clear that the global potential exists. In fact, for the general functions, such a potential does not necessarily

exist. However, for certain ladies, such as linear functions of the form A times X plus B, a potential can be defined. Hence, for the case of linear weight-consistent games, we can consider them again as a local search problem, just as their unweighted variant, which places them in peerless. Indeed, the potential found by Foutac Cental

allows us to prove that an equilibrium must exist. However, in this case, as opposed to the unweighted case, the only assessments we can make regarding its peerless complexity are only those that can

be concluded trivially. Specifically, there are many cases of unweighted consistent games where an equilibrium can be computed efficiently and very easily, while the algorithms used do not generalize for weight-consistent games.

At the same time, there are no hardener results for this special case of weight-consistent games. In this work, we aim to cover this gap by examining the exact impact of the presence of player weights on the complexity of pure Nash equilibrium.

Specifically, there are two cases we will be especially interested in. Firstly, a congestion game can become easier in the unweighted case due to a simpler topology, especially in the series-parallel case. Secondly, if the latency functions themselves are very simple, such as being identity functions.

So we are going to examine these two cases where the equilibria are very much easier than the unweighted case. In the first case of series-parallel networks, we consider this topology. If the series-parallel topology edges are allowed to be connected either in series

or in parallel, similar to a network of resistors. This topology is quite simple and it has been shown that a number of problems on series-parallel graphs can be solved in linear time. For example, series-parallel graphs can be recognized in linear time, which shows that

series-parallel is a very simple topology. Indeed, it was shown by Fotakis that in the case of a series-parallel network, a Nash equilibrium can be efficiently computed for unweighted consistent games. In fact, this can be done in polynomial time to

recruit the best response algorithm. However, in the weighted case, this algorithm cannot be extended. At the same time, there have been no PLS-hardened results covering this case showing hardness here. In this work, we aim to cover this gap and we in fact show that this problem is PLS-complete

for weighted consistent games, despite the fact that it is simple in the unweighted case. To achieve this, we reduce from local backscats. Essentially, we embed in a series-parallel weighted consistent game the structure of local backscats. The second case we are interested in concerns the case of consistent games with n delay functions. In this case, any local improving

sequence must make at most polynomial the parameter of the game steps to find. Indeed, since the potential, since there is nothing exponential either in the latencies or the players, every path must take at most polynomial steps to end.

Indeed, in such a problem, there is nothing exponential and can be easily found. However, this is not true for the weighted cases since the exponential difference in the

weights of the players can allow any such path to go on for an exponential length of time. Indeed, we show that computing natural equilibrating weights consistent in games, where there are no added delays, is PLS-complete. This case is especially interesting to us because we essentially remove any other source of hardness and focus only on the weights of the players.

Indeed, we show that this is enough to be PLS-complete. In this case, however, we cannot reduce for local backscats and instead need to define a new problem to tackle this sub-area of PLS, which we will explain shortly.

Before mentioning the details of the reductions, let us overview our results in this paper. Overall, in this table, our results concern the complexity of pure natural equilibrating consistent games. While the only result that generalised from previous work was the unweighted case for asymmetric linear delays, which was again PLS-hards in weight-consistent

games are generalisations for the unweighted case, in our work we managed to expand the boundaries of PLS-hardness through our techniques. First of all, note how series parallel topology games end up being PLS-hard while in full time for the unweighted case. In the same direction, we also find out that when removing all complexity or parameters of the

game by removing all the coefficients from the latest functions, the game becomes against PLS-complete, even if we only have weighted players. As we said, in the case of identity delays, reducing from local maxcat runs into significant difficulties. This is because

while only leaving a game with player weights, it becomes very hard to embed a typical maxcat instance in the combinatorial structure of the problem. These structures are necessarily incompatible. Indeed, the hardness of local maxcat often comes from the edge, which is the

interaction between players or nodes. To alleviate this, we define a new problem. The new problem we define is named node maxcat. Just like maxcat denotes the different interactions between players, we define local node maxcat to define the weight of its player.

In local node maxcat, instead we have a vertex-weighted rather than edge-weighted graph. Every player, or equivalently node, picks a side of the cut based on the total weight of his neighbors on each side. For example, this node prefers to flip, since the total weight of his neighbors on one side is greater. We can in fact equivalently consider

this problem on a specific instance of local maxcat by setting edge-weight equal to the product of the weights on its vertex. Notice now how the value of the cut becomes the potential of the game. This can also be viewed as a weighted potential for this game, where the

improvement that each player experiences times their weight is exactly the improvement in potential for its improvement move. This problem is much better suited for reducing

to our problem of ident delay functions. Not only is it better suited for this particular application, but also it allows more freedom in getting positive results than classic maxcat. In particular, we can show that there is an efficient algorithm

for computing one plus epsilon approximate equilibria, assuming the different vertex-weight are well-grouped in a well-defined sense, meaning that when we round the weights, if the groups that result are few enough, then we will be able to find the efficient, quickly in

polynomial time, one plus epsilon approximate equilibrium. Note that this wouldn't be possible with maxcat, since we only have edge-weights in that case instead of node-weights, which we are able to sort and order. The main result in this paper is showing that

local node-mechat is in fact PLS-complete, despite its seemingly simpler structure. With the help of this result, we are able to show the PLS-copleteness of network-consistent games with ident delays in the asymmetric case. This is an overview of our reductions in this

paper. A goal, recall, that PLS-completeness of series-parallel networks is obtained by classical reduction from maxcat. PLS-completeness of congestion games, where only the players are weight, however, requires a more delicate approach. PLS-completeness in this case is obtained by a novel problem, local node-maxcat. The PLS-completeness of

local node-maxcat itself is obtained from a problem caught secretly, which we'll explore shortly. Again, reducing from local-maxcat would not be appropriate, since we cannot embed local-maxcat in local-node-maxcat. Circuit flip was one of the first problems

shown to be PLS-complete by Johnson, Pademir and Akakis. An instance of circuit flip consists of a given feedback-free Boolean circuit composed of NOR gates, with m input bits and n output bits. Possible solutions are the binary inputs to the circuit, while neighboring solutions are obtained by flipping a single input bit each time. The output of

a circuit is considered as the value that we are trying to optimize. Hence, given such a circuit, we are looking for an input value of bits, so that flipping any single bit will not decrease or decrease the output value, depending on whether we want max-circuit-flip or bin-circuit-flip. Let us say a few words about the circuit-flip to maxcat

reduction, and highlight some of the technical difficulties involved with this reduction. To start with, we built an existing machinery and previous work by Safran and Akakis, carrying Safran and Telstra and Deutschner. Specifically, we constructed a vertex-rate graph composed of certain subgraph edges, whose role we explain shortly.

Here is a high-level depiction for our construction. Essentially, we have two copies of the same subgraph gadget, who have the following roles. They each take m input bits and output the two following sets of bits. In the first set, they output the value of the circuit

flip problem we are trying to reduce. In the second set of bits, they are outputting the next neighboring solution to that circuit-flip problem. The two circuits alternate in their

function, constantly giving each other the output of the other. The working principle behind this construction is that this circuit will take turns improving the solution found by the other gadget until the solution cannot be further improved, which means we will have found a local optimum. Hence, a local optimum of this vertex-rate graph

will give us a local optimum for the local load bucket instance, for the circuit-flip instance. Let us dive a bit deeper into the intricacies of the proof. A key concept related to proof showing PLS hardness of such problems is of the bias that the node is experiencing,

assuming a configuration where no node is able to make some improving move. How much he would gain by making this move is called his bias towards the specific value. For example, the red back node here would gain 43 by changing his partition. Conversely, if the node would be unwilling to make this improving move,

in total he would lose by making it. This is what we call his bias to remain that position. For example, the node who waits 60 here has bias 43 to remain that position. Proofs related to circuit-flip usually rely on a prototype created by Shafri and

Kakis on a conceptual level. This gadget has certain nodes named input, output, and control. The control nodes have the property, depending on their value, of controlling the mode in which this gadget is operating. There are two modes. In the first mode, compute mode,

the output node is biased to take the NOR value of the input node. In the right mode, the two input nodes have no bias. Essentially, the circuit will go from right mode to take the new input into compute mode to compute the new output. In existing circuit-flip reductions,

this gadget can be operated simply by setting appropriate edge weights. The problem here in our case is that we need to manipulate possibly very heavy vertices, such as the input nodes, when they have no bias from the gadget, especially when it's on the right mode. To achieve this with only vertex weights, we have to use the following

construction. Essentially, the goal is to have a vertex with moderate weight and moderate bias dominate the vertex with high weight but zero bias, such as the input vertices of the Shafri and Kakis gadget. The insight behind this construction is that we can trace bias for weights along the length of the subgraph, effectively allowing us to move the very heavy

nodes of the NOR gadgets without having to resort to even heavier vertices, similar to using a lever. Note here that this gadget is unidirectional and cannot possibly be used to emulate completely an edge in a maxcat instance. If that were the case, then we

wouldn't need to bother with circuit-flipping. Another important technical issue in this reduction is concerning the implementation of comparison error detection. Recall that we have two gadgets that alternatively take each other's output as their input. The difficulty

here is while the circuit with the higher output value must be the one to give its output the other circuit, we must take care to ensure that it's actually outputting the correct value. In the edge-weighted case, this is achieved by giving the edges related to error detection a much higher weight and hence priority. In our case, however, each output bit must have a similar weight as the node corresponding to its correctness. The solution here is to

analyse the functionality of the comparison more carefully and not to actually ensure the correctness of every lower bit, as long as we have a strict inequality in a higher order bit. For example, in this case where we have a strict inequality in a higher order bit,

for example one higher than zero, we don't need to compare the rest of the lower order bits, even if they're incorrect. In summary, in this presentation we highlight how PLS heart can arise even in very simple settings when we add weights to player. We also provide a very simple problem one can use to reason about problems in this setting. Open directions include

exploring further the simple structure of local load max-cut and whether it can be used to give further results even though it's also PLS complete. Moreover, it is also interesting to consider whether our techniques can be extended for symmetric

delay games. Specifically, this problem is where both of our conditions coincide. For example, what happens in series parallel and identity delay games?