## 5 Distributed Algorithms for the Many-to-Many Maximum Weighted Matching Problem
### Lid _Algorithm_  
The simple greedy algorithm we are proposing is fully distributed and operates by choosing the locally heaviest edges in every node's neighborhood, generalizing the one-to-one matching algorithm by [PERSON] [8].  
In the beginning, each node \(i\) reports to each neighboring node, \(j\), only \(j\)'s relative rank in \(i\)'s preference list, in the form of \(\Delta\overline{S}_{i}^{j}\), \(\Delta\overline{S}_{j}^{i}\) exchange between \(i\) and \(j\), and they both compute the weight \(w(i,j)\) of their connecting edge. This ensures the flexibility of the ranking metric each node uses (it does not need to reveal the metric) at the cost of only local communication between nodes. Every node keeps these newly formed weights of its adjacent edges in a _weight list_, which is then used during the algorithm's execution to determine the desirability of a neighboring node. Note that these weight lists do not replace the individual preference lists of the nodes: they are auxiliary lists that are used in a similar way (to determine desirability), but only during the algorithm's execution, _i.e._, not for measuring the final satisfaction.  
The _Local Information-based Distributed_ (LID) algorithm (_cf._ Algorithm 1 for pseudocode) uses, at each node \(i\), four sets (\(U_{i},P_{i},A_{i},K_{i}\)) and a function (\(topRanked(\cdot)\)) and sends two kinds of messages (PROP and REJ):  
* A node \(i\) sends PROP messages to propose to its heaviest-weight neighbors the establishment of a connection with them. If an asked node also sends a PROP message to node \(i\), then the connection is established (_locked_ or _selected_); note that this will happen at both endpoints. Set \(P_{i}\) keeps the neighbors to which node \(i\) proposed with a PROP message; \(A_{i}\) keeps the neighbors which approached node \(i\) with a PROP message; \(K_{i}\) keeps the locked neighbors, and \(U_{i}\) the neighbors that did not send any message to node \(i\) or were not contacted yet. The algorithm terminates when \(U_{i}=\emptyset\).
* A node sends a REJ message when it has locked as many neighbors as it could. When a node receives a REJ message, it sends a new PROP message to the next unproposed neighbor.
* The \(topRanked(\cdot)\) function returns the top ranked node of its set argument, according to the weight list of the calling node. In Algorithm 1, this means that PROP messages are sent to neighbors in decreasing ranking order and there are at most \(b_{i}\) such unanswered messages originating from \(i\) at any time. A new PROP message is sent only if a previously asked node has explicitly declined.
* When the algorithm finishes in a node \(i\) the connected neighbors can be found in set \(K_{i}\).  
```
\(K_{i}=\emptyset;A_{i}=\emptyset;P_{i}=\emptyset;U_{i}=\Gamma_{i}\) while\(|P_{i}|<b_{i}\)do\(P_{i}\gets P_{i}\)\(\cup\)topRanked(\(U_{i}\backslash P_{i}\)) forall the \(v\in P_{i}\)do send(PROP,\(v\)) while\(U_{i}\
eq\emptyset\)do receive(m,\(u\)): ifm = PROPthen\(A_{i}\gets A_{i}\cup u\) ifm = REJthen\(U_{i}\gets U_{i}\backslash u\) if\(u\in P_{i}\)then\(P_{i}\gets P_{i}\backslash u\) \(v\leftarrow\)topRanked(\(U_{i}\backslash P_{i}\)) \(P_{i}\gets P_{i}\)\(\cup\)\(v\) send(PROP,\(v\)) if\(\exists v\in(P_{i}\backslash K_{i})\cap A_{i}\)then\(U_{i}\gets U_{i}\backslash v\) \(A_{i}\gets A_{i}\backslash v\) \(K_{i}\gets K_{i}\cup v\) if\(P_{i}\backslash K_{i}=\emptyset\)thenforall the \(v\in U_{i}\)do send(REJ,\(v\)) \(U_{i}\leftarrow\emptyset\)
```  
**Algorithm 1** LID: Local Information-based Distributed algorithm for many-to-many maximum weighted matchings, run on node \(i\)