## 6 Data Structures and Running Time  
Each agent \(a\) (either a \(U\)-agent or a \(W\)-agent) has a preference list \(L_{a}\), which is a list of lists, _i.e._, we have a list for each tie. For each list we have access to both its first and last element. Each agent has a pointer to their position in every tie they belong to (here a \(1\)-element list is also considered a tie). Whenever \(W\)-agent \(w\) gets saturated for the first time, \(w\) goes over her whole list \(L_{w}\) and moves herself to the end of every tie she belongs to, as explained in the description of Algorithm ASBM. This operation takes \(O(|L_{w}|)\) time. Every \(W\)-agent \(w\) stores information about \(U\)-agents currently belonging to \(M(w)\) in a priority queue. \(U\)-agents belonging to \(M(w)\) who are equally good for \(w\) are kept in one list, thus the priority queue contains lists. Each such list is associated with a priority value, which is the position the \(U\)-agents on that list have on the initial list \(L_{w}\), _i.e._, the \(U\)-agents that are at the top tie of list \(L_{w}\) have priority equal to \(1\). We implement a priority queue as a balanced tree with an additional pointer to the maximum element. We will use the following operations:  
* finding the maximum element (takes \(O(1)\) time)
* deleting a given element (takes \(O(\log n)\) time, where \(n\) denotes the number of elements in a priority queue)
* inserting a given element (takes \(O(\log n)\) time)
* finding an element having a certain priority value (takes \(O(\log n)\) time). After deleting or inserting an element we update the pointer to the maximum element, which takes \(O(\log n)\) time. Each \(U\)-agent \(u\) keeps track of \(W\)-agents currently belonging to \(M(u)\) in a list. Each \(U\)-agent \(u\) has the counter of the number of unsaturated \(W\)-agents incident with him, and whenever a saturated \(W\)-agent moves herself to the end of the ties, \(U\)-agents also decrease respective counters. Therefore checking if \(u\) is subsatellitic takes constant time. Each \(W\)-agent \(w\) has a separate list \(S_{w}\) of statellitic \(U\)-agents w.r.t. \(w\) belonging to \(M(w)\). Every time \(w\) gets matched to some new \(U\)-agent \(u\) who is statellitic with respect to \(w\), she adds \(u\) to \(S_{w}\). When we want to check if \(w\) is co-satellite, we go over \(S_{w}\) and for each \(u\in S_{w}\) check if \(u\) is still satellite w.r.t. \(w\). Checking if a \(U\)-agent \(u\) is satellite w.r.t. \(w\) can be done as follows. \(W\)-agent \(w\) has a pointer to her position in a tie \(t\) on \(L_{u}\). We also have access to the first element of \(t\). If the first element of \(t\) is unsaturated, then it means that \(u\) is satellite w.r.t. \(w\). This way we can also find a satellite of a statellitic U-agent in \(M(w)\). If \(u\) is not satellite w.r.t. \(w\), we remove \(u\) from \(S_{w}\), otherwise we do an appropriate exchange. Once \(u\) is removed from \(S_{w}\), he will not be added to \(S_{w}\) again. It is so since once \(u\) has no unsaturated \(W\)-agents equally good for him as \(w\) on his list, it will stay so. Hence the overall time Algorithm ASBM spends on \(S_{w}\) is \(O(|L_{w}|)\). Each list describing a tie within the priority queue of \(U\)-agents belonging to \(M(w)\) is organized in such a way that subsatellitic \(U\)-agents proceed \(U\)-agents that are not subsatellitic. Whenever a \(U\)-agent \(u\) ceases to be subsatellitic, we move him to the end of every list in every priority queue he is in. Moving \(u\) to the end of every such list takes \(O(|M(u)|)\) time. Every \(u\) ceases to be subsatellitic at most once in the course of running the algorithm. Therefore the total time spent on moving \(U\)-agents who ceased to be subsatellitic to the ends of priority queues does not exceed \(O(m)\). This way, to see if \(w\) is co-subsatelliticw.r.t.