Assignments for Congestion-Averse Agents: Seeking Competitive and Envy-Free Solutions
Authors: Jiehua Chen
Jiong Guo
Yinghui Wen
Venue: NeurIPS 2025 poster ()
Keywords: Fair resource allocation
preferences with congestion aversion
congestion games
polynomial-time algorithms
complexity analysis
Primary area: theory
TL;DR: We contribute polynomial-time algorithms to determine competitive assignments for agents with congestion aversed preferences

Abstract: We investigate congested assignment problems where agents have preferences over both resources and their associated congestion levels. These agents are \emph{averse} towards congestion, i.e., consistently preferring lower congestion for identical resources. Such scenarios are ubiquitous across domains including traffic management and school choice, where fair resource allocation is essential. We focus on the concept of \emph{competitiveness}, recently introduced by Bogomolnaia and Moulin [6], and contribute a polynomial-time algorithm that determines competitiveness, resolving their open question. Additionally, we explore two optimization variants of congested assignments by examining the problem of finding envy-free or maximally competitive assignments that guarantee a certain amount of social welfare for every agent, termed \emph{top-guarantees} [6]. While we prove that both problems are NP-hard, we develop parameterized algorithms with respect to the number of agents or resources.

Assignments for Congestion-Averse Agents: Seeking Competitive and Envy-Free Solutions
Jiehua Chen
Jiong Guo
Institute of Logic and Computation TU Wien
School of Computer Science and Technology Shandong University Qingdao, China jguoßadu. edu. cn
Austria
j jchen@ac. www.wn.wwc.....
Yinghui Wen
Digital and Intelligent Center
Shandong Institute of Information Technology Industry Development
Jinan, China
y yinghui. wen@foxmail. com
Abstract
We investigate congested assignment problems where agents have preferences over both resources and their associated congestion levels. These agents are averse towards congestion, i.e., consistently preferring lower congestion for identical resources. Such scenarios are ubiquitous across domains including traffic manage- ment and school choice, where fair resource allocation is essential. We focus on the concept of competifiveness, recently introduced by Bogomolnaia and Moulin [6], and contribute polynomial-time algorithm that determines competitiveness, re- solving their open question. Additionally, congested assignments by examining the problem finding envy-free or maxi- mally competitive assignments that guarantee certain amount of social welfare for every agent, termed oopgguarattees [6]. While we prove that both problems are NP-hard, develop parameterized algorithms with respect the number of agents or resources.
explore two optimization variants
Introduction
In the realm resource allocation and task assignment, the challenge often extends beyond mere allocation-it entails navigating the intricate balance between individual preferences and the con- gestions that other agents incur. Congested assignments epitomize this challenge and address the situation when agents number agents simultaneously assigned to the same resource, the so-called congestion level.
iingestion-aversee i.e., the preferences negatively correlated with the
Congested assignments are pertinent in numerous real-world scenarios: From urban traffic manage- ment, where drivers select routes while considering traffic congestion, to educational contexts like school choice [35] 12 or student exercise slot allocations, where students' choices are influenced by class sizes. Similarly, in cloud computing. allocating computational tasks to servers must account for server load. In each of these scenarios, assigning agent-whether driver, a student, task executor-to a resource (jointly referred to as a post) may introduce additional costs, with detrimental effects other agents. For example, the productivity in shared office space diminishes more people use it. Similarly, traffic management, drivers might opt for less crowded routes since the mental load increases significantly with even small increase in traffic. In other words, the agents' individual preference over a post inversely proportional to its congestion level.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Envy- free (EF)
Competitive (CP)
Top-guarantee (TG)
Nash stable (NS)
Non-wasteful (NW)
Figure I: Relations among the different fairness concepts under congestion-averse preferences. All
relations strict; see Lemma
The overarching task is find an optimal assignment of the agents to posts that respects agents' congestion-averse preferences. Defining 'optimal' in this setting is non-trivial. In traffic management, for example, one might aim for a Nash stable assignment (aka. Nash equilibrium 33 37) meaning that no agent prefers to deviate to another post which increases the congestion by one. Milchtaich shows that Nash stable assignments for congestion-avers aveers preferences are always attainable and any assignment can be turned Nash stable in polynomially many best-reply improvement steps. Although Nash stability may prevent systematic chaos, can be quite unfair, particularly in slot allocations, as it may induce envy among agents, meaning that an agent may prefer to take over another agent's post (albeit for the same congestion). Notice that envy-freeness also easy to achieve by simply assigning all agents to the same post, but this approach is often wasteful in the sense that there may exist an empty post which an agent prefers to his assignment.
To address the wastefulness in an envy-free assignment, Bogomolnaia and Moulin 6 propose competitiveness (CP) as solution, which ensures that no agent envious and no post is wasteful. They also introduce top- g-ggguaaanness a less demanding criterion than competitiveness, which requires every agent to be assigned to one of his top choices out of all m x n choices, with m and being the number of posts and agents, respectively, note that each choice represents post coupled with a congestion level. Top-guarantees
easy to achieve by a simple sorting algorithm (6] Proposition 1j. Furthermore, top-guarantees is necessary for ensuring Nash stability as well as competitiveness, though the latter criterion competitiveness may not always exist.
The following example illustrates the different fairness criteria and Figure depicts their relations.
Example 1. Consider two posts A= {a1, 02) and three agents V = {21, 022 13). The preferences of the agents as follows, with the second component in each tuple denoting the congestion level:
U1: (01, 1) > (a1.
(az. 1) > (a2 >
U2: (11 1) ~ (a2. 1))== (01, 2) ~ a2 2)
11:
a1
a2
11:
a1
a2
03: (01, 1) > (0) > (a2: > (a2,
U2,
U/3
11
U1,
V/3
2/2
Roughly speaking, without congestion, both i1 and V3 strictly prefer a to ag. However, while in indifferent between sharing ai with another agent and being alone at a2 (indicated by (a),2) 2) (a2, 1)), 13 will only prefer to go to d2 when d, has more than two congestions. Agent U2 is indifferent between 01 and 0g general and cares only about congestion.
There are several Nash stable assignments, c.g., I11 assigning d22 and U3 to 01, and 01 to 02i 01 will not deviate 01 since otherwise the congestion of a₃ will be increased to three and V1 prefers (a2, 1) to (a1, 3) (due to the congestion aversion assumption). and similar reasoning applies to 1/2 and U3. However, it is not envy-free (and hence not competitive) since agent 1/2 envies 11- On the other hand, assigning agent 11 and Uy to post a1, and agent 12 to post 02 (see II,) is competitive, and hence envy-free and guagguarateeed.
both V1 and va have the same preferences as U2, however, then no competitive assignments exist since at least one post a is assigned more than one agent, so either it is wasteful or another agent will envy the agent assigned to a. In this case, II, and II, are still Nash stable (and hence top- (op-guaranteed) but not envy-free or competitive anymore.
Competitiveness offers a promising resolution for congested assignments, as it ensures non- wastefulness, envy-freeness, and oopguuaanttess, thereby securing specific welfare level for all participants. Despite their appeal, the computational complexity of determining competitive assign- ments remains open, as noted by Bogomolnaia and Moulin 6 This unresolved issue leads to our core research question:
Q1: Is there an efficient way to determine whether competitive assignment exists?
2

---

Since CP may not always exist, we consider two relaxations:
02: How hard is it find a hop--uaranted and envy-free assignment?
Q3: How about oo-gguraattedd and maximally competitive assignments?
We tackle these questions by exploring the computational intricacies involved in achieving competi- tiveness, uop-guarantees, and envy-freeness in congested assignments.
Our main contributions. We resolve Q1 affirmatively by showing that determining the existence of competitive assignment is polynomial-time solvable. We also establish the NP- NP-hardness of finding oop-guaratteed and envy-free assignments (Q2), and of top- upp-uuaantteed and maximally competitive assignments (Q3).
To answer QI, we first show two key insights: (1) We can restrict our search to CP assignments where every post is non-empty; see Lemma 3 (2) We can use maximum flow to find the congestion vector of CP assignment with all posts being non-empty and derive the corresponding CP assignment (if exists) in polynomial time. For Q2 and Q3, we provide hardness reduction from the NP-complete problems EXACT COVER BY 3-SETS and CLIQUE, respectively. We complement the hardness results by providing several parameterized algorithms.
Related work. The congested assignment problem is rooted in congestion games, introduced by Rosenthal [36]. In these games, agents select subsets of resources (posts), with each resource having cost function dependent on its usage level. An agent's 'ss total cost is the sum of costs over their selected
resources. Rosenthal proved the existence of Nash equilibria, while Milchtaich [33] extended the
model with player-specific cost functions and demonstrated the same existence property. The field has evolved through both theoretical and computational perspectives
26
Recently, Bogomolnaia and Moulin [6] introduced two significant fairness concepts for congested as- signments: cop-guarantees and competitiveness. The former ensures minimum welfare guarantee for each agent, while the latter addresses a more complex balance of envy-freeness and non non-wastefulness, top-guarantees differs from the classical minimax principle in game theory: while minimax aims to minimize the maximum cost of any participant, top-guarantees establishes a hard constraint ensuring every agent achieves a certain welfare threshold. This connects our work to other assignment prob- lems utilizing the minimax principle, such as MIN-REGRET STABLE MATCHING [24] 31). which finds stable matchings that minimize the worst rank of any assigned partner. Bogomolnaia and Moulin demonstrated that -uparaaaattees is straightforward to achieve, but left the complexity of finding competitive assignments as an open question. Our primary contribution is answering this question by providing novel polynomial-tin -omee algorithm for determining competitiveness.
Congested assignment can be viewed a restricted variant of the GROUP ACTIVITY SELECTION (GAS) problem, introduced by Darmann et al. [8 19] and subsequently extended and studied by many others (30 14
27 23 21). GAS extends the congested assignment concept by allowing agents' preferences over pairs of activities and group sizes, not necessarily exhibiting aversion to larger groups. Despite its broader scope, the specific challenges of applying competitiveness or top-guarantees within GAS have not been previously addressed.
Congestion- averss preferences in congested assignment similar to the preferences of the agents in anonymous hedonic games [4], where agents form coalitions based solely on group size preferences rather than specific membership.
Congested assignment is also related to Copland's SCHOOL CHOICE WITH CLASS SIZE EXTER- NALITIES (SC-CSE) problem [12. which generalizes the classical SCHOOL CHOICE problem M. Compared to our setting, every post in SC-CSE also has a capacity bound and a preference list, which ranks all agents in strict order and the goal is to find stable assignment, i.c., an assignment without justified envies and wastefulness. Phan et al. (35 investigate a model similar to Copland. Instead of post-congestion pairs, they assume that the preferences are over pairs of posts and "resource ratio," and investigate an equilibrium notion that is specific to their model. When imposing lower and upper quotas the capacities of the posts, our problem is related to STABLE MATCHINGS WITH UPPER AND LOWER QUOTAS (SM-ULQ) [5] 25 3 9.. Since SM-ULQ is NP-hard, one could obtain the same hardness for finding a competitive assignment with lower and upper quotas.
Finally, congested assignment may be related to the SCHEDCLING TO MAXIMIZE PARTICIPATION problem [7]. where servers correspond to posts and clients agents such that each client has capacity
3

---

bound for each server and will not be satisfied if that bound is exceeded. The goal is to assign clients to servers maximizing the number of "satisfied" clients.
For a comprehensive discussion on related works in congested assignments, we refer readers to the recent paper by Bogomolnaia and Moulin [6].
Structure of the paper. In Section we introduce necessary definitions and concepts for the paper, and describe an approach to determining whether competitive assignment for a given congestion vector exists. In Section 3 we present our main result, an efficient algorithm for competitive assignments. In Section 4 we show NP-hardness for top- nop-guaranteed assignments that are envy-fres or maximally competitive, respectively, and provide some parameterized algorithms for these two problems. We conclude in Section [5 for future research. Due to space constraints, the proof's of statements marked by (+) are deferred to the appendix.
Preliminaries
Given a non-negative integer 2, let [a] denote the set {I,...,,3) 2). We assume basic knowledge of parameterized complexity and refer to the textbook by Cygan et al. [33 for more details.
Let A = {ai..... 4m } denote finite set of m posts and V (e,....,,o Un a finite set of n agents T The input of CONGESTED ASSIGNMENT consists of A, V, and for each agent E V, a preference list Z. (i.e., weak order, which is transitive and complete) on the set of tuples A x [n] (i.e., ordered pairs). The weak order ž, specifies the preferences of agent over the posts and their congestions (i.e., the number of agents that will simultaneously occupy the post). We use ~ to denote the symmetric part of E. and > the asymmetric part; we neglect the subscript v if it is clear from the context which agent we refer to. The agents may be indifferent between different posts, but are averse to congestion, i.e., for each post O E A and each congestion level E [n - 1]. each agent v has d) >o (aj, d + 1). For instance, in Example [1 agent V1 (01, 2) (az, 1) means that 01 is indifferent between (a1, 2) and (02, 1). This also implies that he has (01, 1) > (ag. 2) (because of aversion of congestion), meaning that he strictly prefers being assigned to post a1 alone over to post 02 with two agents.
An assignment of agents V to posts A is partition IT = (Sa) of V where S, is the set of agents assigned to post a so that every two sets Sa and S, are mutually disjoint and USEa a S, V. The cardinality [S_] of S2 is called the congestion of post a. We say that a post a is empty if S. 0. For brevity's 's sake, we use (Ie) to refer to the post that agent is assigned to and often use II(a) to refer to the set S. of agents that are assigned to post a. We call ş (II(a)))eeA the congestion vector of partition II.
Definition (Nash stable, envy-free, top-guaranteed, and competitive assignments). Let II = (Sa)aed denote an assignment for instance (A, V, (z:)eev) of CONGESTED ASSIGNMENT.
We say that II is Nash stable (in short, NS) no agent wishes deviate another post. Formally, II is NS if for every agent E V and every post E A it holds that (a", SS.- () E. [S. 1), where a" denotes the post that agent e is assigned to.
We say that agent u envies agent o' if (b, (Ssl) >, (a, (Sal) where e is assigned to a and o' to b. Accordingly, we say that 11 is envy-free (in short, EF) if agent envies any other agent.
We say that II is wasteful if there exists an agent v and an empty post a such that e strictly prefers (a, 1) >y (a" 1Sa 1). where a" denotes the post that agent v is assigned to; otherwise II is non- wastefll (in short, NW).
We say that II is top- guaaanterd (in short, TG) if every agent v E V is assigned to post a = I[vv) such that (a, [T) is among the [V| tuples in the preference list Z.. breaking ties arbitrarily.
We say that an agent v E V is satisfied with IT if he neither envies any other agent nor prefers to move to an empty post, i.e., for every post where a" denotes the post that agent v is assigned to. Otherwise, we say that v is unsatisfied with II. Accordingly, II is competitive (in short, CP) if every agent is satisfied with II. Il is maximally competitive if it admits the fewest number of unsatisfied agents among all assignments.
A it holds that (S-, Zv (a, max([S.). 1)),
'A and V are standard notion for the set of alternatives and voters, respectively, from voting theory. We adopt them since the agents also have preferences.

---

ALGORITHM I: Determining the existence of CP assignments
Input: An instance /' (A, V. (Ee)oey).
Output: CP assignment if exists; otherwise no.
foreach 1 = max m n) to m -
Compute / = (A, V, (E+)evv) according to Construction I on input (7', k)
> Decide whether there exists CP assignment for with all posts being non-empty. A
T[a] +- 1 for all
while L. "ua"""'o ['aa] V do
> Phase 1: Deciding existence of a perfect flow
Let (G (Áuve V {s,t), E), c) be the network constructed by Construction 2 on input (I, T) Compute max flow f of (G
if f has value V then return the assignment derived from as per Definition without the l: dummy agents.
> Phase 2: find an obstruction
Find a vertex 8* E V with f(0", ))
V' < (6*)
10
repeat
à vertex in Á \ A' with (ā, E for some è V
12
A' + W {a} V' - V f(ā, 0) =1]
13
14
until no â E A \ A' exists with (ā, 6) E for some E V';
> Phase 3: update T
15
foreach à E A' do T[a] + T[a]+ +
return
17 return no
For congestion-averse preferences, we observe the following relations among the five fairness concepts: CP, EF, NS, TG, NW; Figure Note that the relation of "CP implies NS" and "NS implies TG" have already been shown by Bogomolnaia and Moulin [6. We provide proofs in the appendix for the sake of completeness.
Lemma (x). (1) CP implies EF, but the converse does not hold.
(2) CP implies NS, but the converse does hold.
(3) NS implies TG and NW, but the converse does not hold.
(4) EF incomparable NS, to TG, and NW, respectively; TG is incomparable to NW.
when searching for CP assignments, we only need to consider the first [ tuples of each preferences list. For each agent and post a, congestion of u for post a in his preference list ip such that (a, A(e, a)) is among the first V tuples, with ties broken arbitrarily; if tuple containing is among the first [V] tuples, then X(e. a) O. Further, we say that post a is acceptable to agent v if A(u, a) > 0, in other words, a, together with some congestion d, is contained one of the first [V] tuples in Z
By Lemma 2
A(v, a) refer to the maximum
The maximum congestions in Example I are: A(e;, a1) and A(U,, = 1, i [3].
Milchtaich 333 shows that NS assignments always exist. Indeed, he proves that there always exists best-reply strategy path connecting an arbitrary assignment an NS assignment, and such path can be found in polynomial time. CP assignments, however, do not always exist (see Example [ and it clear how to adapt the NS-improvement approach to determine whether CP exists. However, if the congestion levels are given, we can determine in polynomial time whether there exists CP assignment that match these levels. the following, we provide an efficient approach to finding maximally competitive assignment when congestion vector is given. The idea is to guess (by brute-forcing) the number of unsatisfied agents and determine perfect b-matching in appropriate bipartite graph between the agents and the posts.
Lemma 2 (x). Given a congestion vector á with Enc 3[a] determine the smallest number of unsatisfied agents among all assignments whose congestion vectors equal 5; the corresponding assignment can found in polynomial time.
[V,, in polynomial-time one can
5

---

3 Algorithms for CP Assignments
In this section, we present a comprehensive analysis of our approach to CP assignments. We provide an overview of the procedure (A (Algorithm [ before exploring its theoretical foundations in detail. The algorithm consists of two main nested loops. The outer loop enumerates possible values of k representing the number of empty posts in potential CP assignment. For each k, we construct an extended instance / that models the original problem with exactly &o empty posts; see line Within the inner while-loop (lines [6). we determine whether I admits CP assignment with all posts being non-empty: Starting with a congestion vector T where T
for all j E [m=]. we iteratively refine this vector by building a flow network corresponding to T, determining the maximum flow, and either deriving a CP assignment when the maximum flow value is n, or increasing some entries in T, or terminating when Z)e(m]] Tbi n, inferring no CP assignment exists where all posts are non-empty.
In the following, we provide rigorous justification for our approach. Section 3.1 establishes why we can restrict our search to assignments where every post is non-empty, while Section (.2tionnn22ddmoooee demonstrates the correctness of our maximum flow formulation for finding CP assignments with all posts being non-empty, as well as a correctness proof of Algorithm
3.1 Reducing to Determining CP Assignments with No Empty Posts
In this subsection, we show how to reduce our problem to the restricted problem of deciding a CP assignment with all posts being non-empty, ensuring line 2 in Algorithm D is correct. The basic idea is to guess the number & of empty posts (assuming CP exists) and augment the instance with k dummy agents, two auxiliary agents and two fallback posts such that any CP assignment must assign to each previously empty post a distinct dummy agent. The core of the reduction is described in Construction | below; see Appendix B.T for an example.
Construction 1 (Extended instance). Given an instance I (A, (tx)nEV) of CONGESTED ASSIGNMENT with m posts and n agents, and a number k with max(0, m- n)) S k S 1- construct a new instance (A*, V*, (E:)ev-)) as follows. Create i dummy agents U1..... Uk. two auxiliary agents P2, and 2 dummy posts b1, b2. Set V* == =V {ui...., Finally, define the preferences of the agents as follows Here, v denotes an original agent from I and Eo his original preference list, but restricted to the first tuples, E [kt], N = k + n + 2.
= Uk: P1.P2} and A = AA UU {b1, b2)-
Pl
Uz: (01, 1) ~ (02, 1) ~...~ (am; 1) > (b1,1)
a1
Qm
b1
b2
> (b), 2)
(b,, - -m);
U2
N
0
pr:
(b1, 1) > (b2, 1) > (b2, 2) > ..... - (b2, N - 1);
P1
0
...
1
N
p2:
(b2, 1) (b1, 1) > (b,, 2) >
(bi, N -5-1) 1);
P2
N
v:
(z+) > (bı, 1) > (b1,2) ..... > (br, l + 2).
c
M(u, ... A(e, am)
k + 2
0
The table above states the maximum congestion of each agent towards each post, where aj. j E [mi] and v denote the original post and agent, respectively.
To prove the correctness, we first make an observation about the extended instance.
Observation 1. Let Is = (A', V (Ei)eev.) denote the instance created by Construction 7 with A AU (b,, by) and V VU {u, i [K]] U {2).P2). Every CP assignment of I (if it exists) satisfies the following: (1) p1 is assigned to by alone, and p2 to b2 alone. (2) Every dummy u, with 1 s 2 < k is assigned some 0, E A alone. (3) Every original v; V is assigned to some original post.
Proof. Let II be a CP assignment of Is with II = (S.) A-. To show the first part of statement (.. we observe that if pi is assigned to b,, then |S,, = 1, due to the maximum congestion of p1 towards by Thus, it suffices show that pl is indeed assigned to b, Suppose, for the sake of contradiction, that p1 was assigned to by instead; note that he will not be assigned to any original post ay due to his maximum congestion towards ay. Then, by the maximum congestion of pa towards b2, agent P2 could not be assigned to by. No original agent could be assigned to b2 either, due to his maximum congestion towards b2. Hence, we would have St_, = {pil and p2 would envy P1. a contradiction to the competitiveness.
By Lemma 1 2
B
only need to consider the first + A 2 tuples in each preference list.

---

The second part of statement ① follows directly from the first part since by is the only acceptable post left for P2 and his maximum congestion towards b2 is one.
By statement ① and the maximum congestions, every dummy agent W2 can only be assigned to some original post alone, proving statement ( statements.
The last statement follows directly from the first two
Now, we show the correctness of the construction.
Lemma 3. An instance I admits a CP assignment if and only if there exists an integer k with max(0, m - n) S k S m such that the instance 1ş created by Construction ] admits a CP assignment with all posts being non-empry.
Proof. Let (A, ve)) The "only if" part is straightforward: Let II (Sa)ae denote a CP assignment of I, and let A' denote the set of empty posts under II with & |A'.. Clearly, (0, m n) S k I m 1. Consider the instance Ig created according to Construction [n (I, We claim that the following assignment II, for I& is CP where every post is non-empty.
For each E A', take a unique dummy agent τ, and assign [Tx(a) {uz); note that there exactly k = | many dummy agents.
For each non-empty post A \ A', let (a) ITa)..
Let [1.(bb) = }pi} and (62) = {p2}.
We continue show why the derived assignment II, is CP for Jg.. Since post is empty, showing competitiveness reduces to showing that no agent is envious. This clearly the case for all dummy agents including P1 and P2 since they assigned to one of their most preferred posts alone. No original agent envies any other original agent or any dummy agent since II is CP for I. No original agent E V envies p1 P2 since p1 and P2 are assigned to b and b2. II is TG for I, and b and b2 occurs at the end of =.- This shows that IT is CP for Jg. as desired.
For the "if" part, let k be an integer between max(0, - n) and m - such that the created instance I admits CP assignment H without empty post. We claim that the assignment II derived from 1lg by omitting all dummy agents and the posts p1 and p2 is CP for
We first show that II is valid assignment for By Observation I every dummy agent is assigned to some original post alone, and hence for each aj E A that is not assigned any dummy agent (i.c., uk {ui....,
[a; = (),, we have [a,,)) II, (a,); and I[(a)) 0, otherwise. This implies
that l[(a)) S V.
By Observation a valid assignment for T.
1 every original agent is assigned to original post, confirming that TI is indeed
Next, suppose, for the sake of contradiction, that II is not competitive and let and be an agent and a post, respectively, such that (a, (a)) 1)) > (a', [[('))) where a' is the post that is assigned to by II. We infer that II(a) cannot be empty since otherwise by Construction ]
and by Observation [2)) we would have that I1 (a) = {ug} for some dummy agent u2- This further implies that v envies U2 in Ig. contradiction to the competitiveness of IIg- Since II(a)
is not empty and v E II(a'), again by Construction and by Observation [ we have that II(a) (a) and I[aa)) (a'). Since N1 is an extension of Σい for each A, we obtain that (a, ITT (a)) x; (T(')) contradiction to the competitiveness of T[
3.2 Determining CP Assignments with No Empty Posts
In this subsection, we show how the while-loop in lines 16 works. As already discussed in the beginning of Section 3 by Lemma 2 we need to determine the desired congestion vector. To achieve this, we iteratively update an integer table T, which stores the congestion level for each post that a CP assignment should not fall below. Each iteration has three phases. In Phase 1 (lines 7 we construct a flow network with capacities corresponding to T and determine whether there exists perfect flow, i.e., the value of the flow equal to the number of agents. If this is the case, we derive and return the corresponding CP assignment (line 7). Otherwise, we proceed with Phase 2 (lines g (4).
where we find an obstruction (see Definition 3 containing posts whose congestion levels need to
be incremented necessarily. In Phase 3 (line 15 we update the table entries of the posts from the
7

---

obstruction. In the remainder of the subsection, we address these phases in details. We first introduce necessary concepts, starting flow networks; see Example for an illustration.
(A, V, (Zo)vev) logether with a congestion table T which has an entry 1 S T(a) S [V for each post a E A, we construct network N = (G,c), where G (Á U V u (s,t), E) is directed graph with dedicated source and target t, and c: E{G) > [[V]] is capacity function:
Construction 2 (Flow network). Given an instance
(i) For each a E A, create vertex à. Let A= E
(ii) For each v E V, create a vertex è. Let V (0 v
(iii) For each post E A, create are (s, (. from the source and set the capacity c(s, â) T(a.
(iv) For each agent U E V, crreate an are (i,t) t) to the target and set the capacity c(ê, t) 1.
(v) For each agent
V and each post a, if considers T(a)) as the most preferred tuple
among all tuples (a', T(a')), a' E A, then create an are (ā. ú) with capacity c(ā, 6) 1.
The capacity function с is c(e) = [[a ife (s. with a E A; otherwise c(c) =
Example 2. Consider the first instance in Example I and start with T = (1, 1). The flow network is
given on the right, where a label with "x y" means the corre- sponding are has capacity x and a maximum flow has value on that arc. For this network, the maximum flow value is 2. It is not a perfect flow since agent by is not assigned. This implies that no assignment with congestion vector T (1,1) 1) CP.
1:1
81
1:1
1:
22
1:1
1:0
a22
03
We need the following concepts to derive an assignment from a flow.
Definition 2 (Perfect flows and the derived assignment). Let (G, denote the network created by Construction 2 for an instance == (A, V, (2 e)evv) together with table T [[V]]]A, A flow of (G, c) is a function ʃ: F(G) + [[V]JU (0) that assigns each are value, satisfying the following: f(e) c(e) for all E E[G), and Σ B(G) f(z,)) E(za)eE(C) f(2,x) for all AUU V. The value of a flow equals the net flow into the sink v(f) E ((x))EE(G)) f(z,t) flow is called perfect if the value of f is [V| this means that with a perfect flow, every are (0, t) to the sink is saturated.
Given a perfect flow S. we derive a congested assignment for the original instance / by setting Maa) {w] [ā, 6) = 1} for each post a E A.
We also need the concept of obstructions, which are witnesses for the absence of perfect flow. This is similar to the forbidden substructure of perfect matching in Hall's marriage theorem.
Definition (Obstruction). Let (G, c) be a network with G = (Ā A
LUUU U {s, 1), F.). A pair (A', V*) with A' S Å and V C V called an obstruction for (G, c) if the following holds:
i 0 / VV:
i A' = e Á 30 E V' with (á, 0) E E(G)), i.e., A' equal to the in-neighborhood of V'; (iii) For each E A'. c(s.a) < l6 V (á. EHI
(iv) Eass c(s, a) < VV'.
A' can be seen minimal set of posts with congestions that are not enough accommodate all agents from V according the congestion table T'
Throughout the remainder of the section, by an iteration, we mean the execution of lines 5 a CP assignment is found, and lines 5 15 otherwise. For each iteration 2 1, we use T, to denote the table at the beginning of iteration 2 (L.e., at line
The correctness of the three phases is based on Lemmas 4 to 6 which we present next. Lemma guarantees that the second phase always finds some critical posts to increment their congestions.
Lemma 4 (+). Each (A', V') computed in Phase 2 in lines X 14 is an obstruction.
Lemma Jensures that increasing the table entries is safe and that the no-answer in line 16 is correct.
Note that since the capacity values are integral, we can assume without loss of generality that the flow is a also integral.
8

---

Lemma 5 (+). Assume that I admits CP assignment II with no posts being empty. Then, for each iteration 2 each obstruction (A', V') found in iteration 2, and each post E A, the following holds. If à E A', then [TT(a)] 2 [= + 1; otherwise [[T(a)] 2 T2(a).
Lemma 6 ensures that the returned assignment is CP.
Lemma (+). If an assignment returned in line then II is CP and has no empty post.
We have everything ready to show the correctness.
Theorem (+). Algorithu [ correctly decides whether an instance has CP assignment in O(m?. (n + m)? time, where m and n denote the number of posts and agents, respectively.
Proof. Let I' be an instance. By Lemma 3 we only need to show that I' is a yes instance if and only if there exists a k E (max(0, m - n), ................... m }} such that line 7 returns an assignment where every post is non-empty and is CP for the instance / constructed in line 2
This reduces to showing that lines 16 correctly decide whether I admits CP assignment with all posts being non-empty. Clearly, if line 7 returns an assignment 11, then by Lemma 11 is CP and every post is assigned at least that whenever line 16 no, I does not admit a CP assignment where every post is non-empty. Towards a contradiction, suppose that I admits a CP assignment, say II, where every post is non- empty. Since line returns no, in the second last iteration 2, we have Enea Ta|a] S [V), but after the update of some table entries the sum exceeds [V. Let Tz+1 denote the table entries at the end of iteration z. By assumption, Eae Ta+1(a] [V] and Σ [a] S [V.
agent. Hence, to show the correctness, we need to show
Since we updated some table entries, we must have found an obstruction (A', VV) in iteration according to which we made the update, By Lemma
5 we infer that for all posts
A, it holds that T2+1 [a] if à $ A'. This implies that
[[a)) 2 [2[4]+1 +1 1- -T2+1(a if â E A', and [aa 2 Ta [a]
[(a) 2 Ts+1(") [a] holds for all a E A. Then, Evea [[a]]
E LoEA Te+1 [a] [V] contradiction
to II being a valid assignment. The running time analysis is deferred to Appendix B.6
4 Two Optimization Variants
In this section, we continue with Q2 and Q3 from the introduction. Specifically, we investigate the computational complexity of finding TG assignments that are additionally either EF or maximally CP.
EF and TG assignments. We first focus on EF and TG assignments, and show that it is NP-hard to find such assignments. Let EF+ TG refer to the problem of determining whether a given instance has an EF and TG assignment. We reduce from the NP-complete EXACT COVER BY 3-SETS (X3C) problem. The input of X3C is a pair SU,S), where U = {ui,..., Wan } is finite set of 3n elements, and S is family of subsets S (Ci,..., Cm. with Cj C and [Cjl 3 for each j E [m]. The question is whether there exist an exact cover J C [m] for i.e. ||| that X3C remains NP-hard even if each element appears in exactly three subsets 22 meaning that m 3n.
n and USeJ Cj U. Note
Theorem 2 (+). EF+TG is NP-complete; hardness holds even if there are ties.
Proof. NP-containment is clear since one check in polynomial time whether given assignment
is EF and TG. Now, we focus on NP-hardness and reduce from X3C. Let = (U,S) S) denote an instance of X3C with U {ui,.... U3n and S (C2) (em) such that every element in U appears in exactly three members of S; note that m = 3n 2 3.
We create an instance I' of CONGESTED ASSIGNMENT follows. For each member Cý E S, create a set-post ay; For each element u; E U, create an element-agent e;; Create two dummy posts by and by and 4m dummy agents P1, P2. ........ P2m, Q1, 92..... 92m Let A = {az j E [m]] U {b,, by ) and V = [2; E [3n]} U {pj. qj ] E [2m]).
We describe the preferences of the agents, where the last "... denote an arbitrary but fixed order of the rest of the tuples. (a, 8, () = (a,, x) > (a. 8 + 1) > ... >> (a, 1) depict the preference list on tuples for post and congestions ranging between s and with S t.

---

The preferences of agent oj is defined as follows, where Cj. Ck. C₁ denote the three members in S
that contain u, with j < k < Uy: (a,.1) > (ax. 1) (ar, > (a,, 2) > (ax. 2) > (a.. 2) > (aj,3) > (a),3) > (at,3) 3) > (b2, 1,3
3n + 4m - 9) >
In other words, each agent f considers the three posts which correspond to the sets that contain
u, most acceptable, followed by by. He does not consider any other post acceptable.
All dummy agents P.. j E [2m], have pj: (a1.1). > .... (Am: 1) > (a1, > ...> (am: 2) x
(b1, 1, 2m + 3n) .....
Briefly put, each dummy agent pj always wants to go to a set-post with congestion one or two.
All dummy agents qj. j E [2mm] only consider b1 and by acceptable, but prefers by over by: dj: (b2, 1, 2m) > (bi, 1, 2m + 3n) > .....
Clearly, the construction can be done in polynomial time. One can verify that the constructed preferences do not contain ties. The maximum congestions of the agents are depicted the following table, where 2s is an element-agent with u, appearing in C1, C22 Cu:
Q1
02
Q3
Qm
61
b2
02
3
3
0
... 3
0
3n + 4m
9
P=
... 2
3n + 2m
0
9:
+ 2m
2m
The correctness proof is deferred to Appendix C.I
We conclude the study of EF+TG with two simple FPT algorithms. The first algorithm is based on brute-force searching all possible TG assignments while the second one on guessing the empty posts and applying Algorithm that checks whether CP assignment exists.
Theorem (+). EF+TG is FPT with respect to the number n of agents and the number m of posts, respectively.
Maximally CP assignments. Now, turn maximally CP assignments and define the decision variant MAXCP+TG: Given an instance I and a non-negative integer I, does there exists a TG assignment with at most l unsatisfied agents? We first show that MAXCP+TG is W[1]-hard wrt. the number t of unsatisfied agents; the W[1] hharddessssss is via reducing from the W[1] W[1]-complete CLIQUE problem 200.. Fortunately, when is constant, the problem can be solved in polynomial time.
Theorem 4 (x). MAXCP+TG is W[ I-hard and in XP with respect to the number of unsatisfied agents. The Whrd-hasdness holds even if there are no ties.
Using an idea similar to the one for Theorem and by applying the algorithm behind Lemma we obtain further parameterized algorithms for MAXCP+TG.
Theorem 5 (x). MAXCP+TG is FPT with respect n, and in XP with respect to m, where n and m denote the number of agents and the number of posts, respectively.
Finally, we show that finding maximally CP assignment remains W[1]-hard even if give up TG. Theorem 6 (*). Deciding whether an instance of CONGESTED ASSIGNMENT has an assignment with at most unsatisfied agents is W( W-ll-hard with respect to t.
5 Conclusion
We investigated congested assignments with congestion-averse agents, focusing on competitiveness (CP), envy-freeness (EF), and maximal competitiveness (maxCP). We devised novel network-flow- based algorithm to identify CP assignments. We then proved NP-hardness of finding an assignment that is nop-guaranteed and either EF or maxCP. We complement these hardness results with several parameterized algorithms. We also show that relaxing top- go-guaraattess does not reduce the complexity: Finding a maxCP assignment remains NP-hard.
For future research, we suggest exploring congested assignments with weighted agents 6 and scenarios where agents have varying responses to congestion. Additionally, in applications like urban traffic, exploring control management strategies, such as identifying the minimum number of posts to remove to achieve a competitive assignment, presents another intriguing avenue. Considering that our work mainly focuses on providing theoretical analysis of congested assignment complexity, empirically validating the algorithms shown in this paper could be another interesting direction.
10

---

Acknowledgement
This work was supported by the Vienna Science and Technology Fund (WWTF) [10.47379/ VRGI8012] and the National Natural Science Foundation of China (Grants No. 61772314, 61761136017 and 62072275). We would like to thank the reviewers for their helpful comments.
References
[1] A. Abdulkadiroglu and T. Sönmez. School choice: A mechanism design approach. American economic review, 93(3):729-747, 2003.
[2] H. Ackermann, H. Röglin, and B. Vöcking. On the impact of combinatorial structure on congestion games. Journal of the ACM, 15:6)22::1-2::2,, 2008
[3] H. Aziz, S. Gaspers, Z. Sun, and T. Walsh. From matching with diversity constraints matching with regional quotas. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, page 377-385, 2019. ISBN 978 1450363099
[4] C. Ballester. NP-completeness hedonic games. Games and Economic Behavior, 49(1):1-30,
2004.
[5] P. Biró, T. Fleiner, R. W. Irving, and D. Manlove. The College Admissions problem with lower and common quotas. Theoretical Computer Science, 411034-36)31133-3155, 2010.
[6] A. Bogomolnaia and H. Moulin. Fair congested assignment. Mathematics of Operation Research, pages 1-19, 2025. URL httpss///// org/ 10. 1287 /mw./moor.////// 2024. 2024.0581 0581
[7] I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, and E. Papaioannou. Scheduling to maximize participation. Theoretical Computer Science, 402: 152-155, 2008.
[8] D. Chakrabarty, A. Mehta, and V. Nagarajan. Fairness and optimality in congestion games. In Proceedings 6th ACM Conference Electronic Commerce, pages 52-57, ACM, 2005.
[9] Chen, Ganian, and T. Hamm. Stable matchings with diversity constraints: Affirmative action is beyond NP. In C. Bessiere, editor, Proceedings of the 29th International Joint Conference on Artificial Intelligence, pages 146-152, 2020.
[10] G. Christodoulou and Koutsoupias. The price of anarchy of finite congestion games. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 67-73, 2005.
[11] G. Christodoulou, M. Gairing, Y. Giannakopoulos, D. Poças, and C. Waldmann. Existence and complexity approximate equilibria weighted congestion games. Mathematics of Operations Research, 48(1):5833603 2023.
[12] A. Copland. School choice and class size externalities, 2023.
[13] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and
S. Saurabh. Parameterized Algorithus. Springer, 2015.
[14] A. Darmann. A social choice approach to ordinal group activity selection. Mathematical Social Sciences, 93:57-66. 2018.
[15] A. Darmann. Stable and pareto optimal group activity selection from ordinal preferences. International Journal of Game Theory, 47(4):1183-1209 2018.
[16] A. Darmann. Manipulability in a group activity selection problem. Social Choice and Welfare, 52(3):527-555) 2019.
[17] A. Darmann and J. Lang- Group activity selection problems. In U. Endriss, editor, Trends in computational social choice, pages 87-103. AI Access, 2017.
[18] A. Darmann, E. Elkind, S. Kurz, J. Lang. J. Schauer, and G. J. Woeginger. Group activity selection problem. In Proceedings of the 8th Workshop on Internet and Network Economics, volume 7695 of Lecture Notes in Computer Science, pages 156-169, 2012.
11

---

[19] A. Darmann, E. Elkind, S. Kurz, J. Lang, J. Schauer, and G. J. Woeginger. Group activity selection problem with approval preferences. International Journal of Game Theory, 47(3): 767-796, 2018.
[20] R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science, 141(1822:109-131, 1995.
[21] R. Ganian, S. Ordyniak, and C. S. Rahul. Group activity selection with few agent types. Algorithmica, 85(5):1111-1555) 2023.
[22] Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical computer science, 38:293-306 1985.
[23] S. Gupta, S. Roy. S. Saurabh, and M. Zehavi. Group activity selection on graphs: Parameterized analysis. In Proceedings of the 10th international symposium on algorithmic game theory, volume 10504 of Lecture Notes in Computer Science, pages 106-118, 2017.
[24] D. Gusfield. Three fast algorithms for four problems in stable marriage. SIAM J. Comput., 16 (1):111-128, 1987.
[25] K. Hamada, K. Iwama, and S. Miyazaki. The Hospitals/Residents problem with lower quotas. Algorithmica, 74(1):440-46,, 2016.
[26] A. Hayrapetyan, É. Tardos, and Wexler. The effect of collusion congestion games. In Proceedings of the 38th Annual ACM Symposium Theory of Computing, pages 89-98, 2006.
[27] A. Igarashi, D. Peters, and E. Elkind. Group activity selection on social networks. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 565-571, 2017.
[28] H. Komishi, S. Weber, and M. L. Breton. Free mobility equilibrium in local public goods economy with congestion. Research Economics, 51:19-30, 1997.
[29] B. Korte and Vygen. Combinatorial Optimization: Theory and Algorithms. Springer, 2007.
[30] H. Lee and Y. Shoham. Stable invitations. Proceedings of the 29th AAAI Conference on Artificial Intelligence, pages 965 (65-971, 2015.
[31] D. F. Manlove, R. W. Irving. K. Iwama, S. Miyazaki, and Y. Morita. Hard variants of stable marriage. Theor. Comput. Sci., 276 276(1-2):211-279, 2002.
[32] C. A. Meyers and A. S. Schulz. The complexity of welfare maximization in congestion games. Networks, 59(2):252-260, 2012.
[33] I. Milchtaich. Congestion games with player-specific payoff functions. Games & Economic Behavior, 13(27):111-122 1996.
[34] M. Milinski. An evolutionarily stable feeding strategy in sticklebacks. Ethology, 51(1):36-49 1979.
[35] W. Phan, R. Tierney, and Y. Zhou. Crowding in school choice. Technical report, Kyoto University, 2021.
[36] R. W. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65-67, 1973.
[37] Y. Shoham and K. Leyton-Brown. Multiagent Systems: Algorithmic, Gume-Theoree and Logical Foundations. Cambridge, 2012.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
We provide proofs for all stated results. They can be found in the main part or appendix.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The model studied in our paper is theoretical and abstract model. Our analysis is based on worst case analysis. There are no experiments.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
We provide proof' for all stated results. They can be found in the main part or appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. .., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibilityy may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
14

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: As mentioned, there are no experiments. But all stated results are proved in the main part or appendix.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (httpa://nips.cm cc/
public/guides httpa////uuleee/oooodaaiiiiiiilo ssiissolioyyyyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
7 cttpsscccpbbbccccc des/ (oodeSumiisse wwwiibmiisssiiii onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
As mentioned, there experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[NA]
Justification:
As mentioned, there are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
As mentioned, there are no experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Our research is theoretical and has no harm to the society or human.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We investigated fair assignment with congestion-averse agents. Fairness is a relevant property that a society would want to achieve. Hence, it could have potentially positive impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our research does not have experiments.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
As mentioned, there are experiments.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, wwwprswi thcode. com/ con/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
As mentioned, there are no experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
As mentioned, there are experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [Yes]
Justification: As mentioned, there are experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: Our research is original.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy (https: http:p/seeeaaaiisscc///oootareea for what should or should not be described.
19

---

Supplementary Material for the Paper "Assignments for Congestion-Aeers Agents:
Seeking Competitive and Envy-Free Solutions"
A Additional Material for Section 2
A.1 Proof of Lemma
Lemma (+). (1) CP implies EF, but the converse does not hold.
(2) CP implies NS, but the converse does not hold.
(3) NS implies TG and NW, but the converse does not hold.
(4) EF is incomparable to NS, to TG, and to NW, respectively; TG is incomparable to NW.
Proof. (1) Clearly, CP implies EF by definition. Now, show that the converse does not hold, let us consider Example ! Clearly assigning every agent to post a₁ EF, but it is not CP since all agents prefer (a2, 1) to (3..
(2) As already mentioned, the implication has been discussed by Bogomolnaia and Moulin [6] already. For the sake of completeness,
provide proof by showing the contra-positive.
Let II be an assignment that is not NS and let there be an agent u E V and a post a E A such that prefers (a, [a]] + 1) to (a", II(a")] II) where a" denotes the post that v is assigned to. If is empty, then clearly, II is wasteful and hence not CP. a is non- non-empty, then since every agent is averse against congestions, either.
infer that prefers (a, (Ta())) (a", [Ma" Il), and hence not CP
Now, to show that the converse does not hold, let consider Example T again. As already discussed there, 1I, is NS, but not CP.
(3) That NS implies NW follows directly from definition. That "NS implies TG" has also been shown by Bogomolnaia and Moulin [6]. Again, for the sake of completeness, we provide a proof here by showing the contra-positive. Let 1I be assignment that not TG, and let E V be an agent and a" post such that is assigned to a while (a", [I(aa) )I is not among his top-|V] choices. Let X (aa d) (a, d) >- (a", [I[(a)))) be the set consisting of all tuples that
prefers to (a", [I[(a" [[) Then, X 2 [V]. For each a E A. let 5(a) denote the largest congestion
such that (a, 8())) E X, i.e., 8(a) = (a,)ex {d} and 8(a) = if no tuple (a, d) exists in X. Then. ((a) = [ 2 [V| E.EA [[[(a)]. By assumption, we have that 8(a") < [I[(a))].
This implies that there must exist post AA {a"} such that 8(a) > [[a]]. By definition, we infer that (a, [[(a] + 1) E X, and hence (a, [[[(a) + 1) > (a", [[(a"))) witnessing that Il is not NS.
It is quite straightforward to come up with a TG and NW assignment which is not NS. Let us consider the following example.
u1: (a1, 1) (a1,2) 2) > (a2. 1)
U2: (01, 1 [02, 1) [a1. 2)
11::
41
02
43
01
02
43
U3: (03, 1) (a3, 2) > (a3.3) 3)
11
U1,
Iy is clearly TG and NW. is not NS however, since U1 prefers (a1, 2) to (a2, 1).
(4) Let consider Example [ Assigning every agent to the same post is clearly EF, but not TG and
not NW. Hence, is not NS by Statement (3). As already argued in Example II, is NS, TG, and NW, but not EF. Assigning ei and v2 to a2 and ny to aj is NW, but not TG: For 01, tuple (02, 2) is not in his top choices.
Now, let us consider the example from item. 11g is TG but not NW.
By definition, we observe the following:
Observation 2. For an arbitrary tie-breaking rule, EaE A X(u, a) = [V| holds for every v E V.
A.2 Proof of Lemma
V in polynomial-tmee one can determine the smallest number of unsatisfied agents among all assignments whose congestion vectors equal 5; the corresponding assignment can found in polynomial time.
Lemma 2 (x). Given a congestion vector 3 with EaE 5(a]
20

---

Proof. The idea is to iterate over all possible number E {0, (0.1.....,IA and check whether there exists an assignment with congestion vector á and exactly t unsatisfied agents. The later problem can be solved via determining whether a perfect b-matching exists, which can be done in polynomial time [29] Chapter 12].
Let (A, V. (Z) be an instance of CONGESTED ASSIGNMENT. check whether there exists an assignment with congestion vector á and exactly t unsatisfied agents, we construct a bipartite graph G on two disjoints and Y with X dummy agent-verlices and do is a dummy post-veriex.
{ao} and Y V (wi,..., wt), ,.,,,,,,,,,,
where the w, 's are the
We add an edge between every original post aj and every dummy agent-vertex we. and an edge between the dummy post-vertex ao and every original agent u, We also add an edge between every original post and original agent, but will delete some according to the congestion vector. In other words, the graph on X and Y is almost complete bipartite graph, except there are no edges between the dummy post ag and any dummy agent W's, E [t].
We delete from the bipartite graph the following edges: For each original agent v and each two original posts a and a', if prefers (a, max(1, s{a])) to f(a")) then we delete the edge {a', v). This is because u would be satisfied, he will never be assigned to a' since either the post is wasteful or he envies some agent that is assigned to a.
This completes the construction of the graph G. We check whether there exists perfect b-matching" for G where B|ao] blay] = s[ay] for all aj A, and bly] for all y E Y. We answer no no such matching exists. Otherwise, let M be the perfect 6-matching, and we return the following partition assignment IT. For each post a; A and agent v; V, let [Tv,,) aj if (v;, ay} M. Let V be the remaining agents that are unassigned; note that these agents are matched to by definition. As long as the congestion of some 0j E A is not equal to s(a,] ölay], pick an agent from V and assign him to aj.
For the correctness, it is straightforward that if II is an assignment with congestion vector ă and exactly i unsatisfied agents V then the following matching is perfect matching: Let M(v:) aj o E V V', and (w;) = ag if v; V". Finally, for each original post ajs it is assigned unsatisfied agents, then we pick ń distinct dummy agent-vertices and match them to aj.
If . is a perfect b-matching for G, then ag is matched with exactly i original agents V who will be the unsatisfied agents. Clearly, , the assignment II given by our algorithm above has the desired congestion vector S. We show that only the agents from V" may be unsatisfied. Consider an arbitrary agent v; (T[x:)). For a contradiction, suppose e; prefers (a,, max(1, (I(
V VV V' and post aj E (a", [[(a")) I],, where v, is assigned to a", i.e., {w;, a²) M. By the definition of I1, it follows that prefers (aj, max (1, ((a)) ))) to (r,8(a")) implying that edge {v;, a") does not exist in the constructed bipartite graph and cannot be matched under M, a contradiction.
Since checking the existence of perfect b-matching and finding such matching if it exists be done in polynomial time by reducing to finding perfect matching, the whole approach can be done in polynomial time as well. This completes the proof.
For an illustration, consider the first instance in Example and the number of unsatisfied agents be t = 0. The following bipartite graph G has perfect b- matching, indicated by the red lines.
Let the congestion vector be s (2, 1)
i1
6:
0g
01
02
02
C3
ag
0
2
1
1
1
03
Indeed, the corresponding 5-matching yields a CP assignment which is Il and it has only satisfied agents.
'A U-matching M is perfect if EcEM. nee 1 Ulu] holds for all vertices
21

---

B Additional Material for Section 3.1
B.1 Example of Construction
Let us consider the four agents with the following preference lists.
V1 (a1, 1) > (a2. 1) > (a3, 1) (a1, 2) (az, 2) >
U2,
Uy:
(az, 1) > [1. 1) > (as, 1] (Q1, 2) ~ (22, 2)
>
U4: (a1, 1) (a2, 1) 2) (az, > (az.
One can observe that if every post is non-empty, then á1 or 02 will have congestion one. If ai has congestion one, then oi has to be assigned to di alone and to 02 alone, leaving 12 and U3 to be envious. 02 has congestion one, then 12 or ity. will be envious. One can verify that assigning any two agents dj and the remaining two to d2 is competitive, leaving ag empty.
Now, let us "guess" that the number of empty post is k = For k 1, we augment the instance with one dummy agent i1 and two auxiliary agents p1 and p2. and two dummy posts b and by. Their preference lists are as follows:
U1: (41, 1) ~ (ag, 1) ~ (ag, 1) > (b1, 1) > (b1.2) > 3):
Pr: (b,, 1) > (b2, > (b2, 2)
(b2, 5):
P2: (b2, 1) > (b), 1) > (b,, 2) >
(b, 5)-
One verify that in the original instance, every CP assignment will leave ag empty, and in the augmented instance, every CP assignment will assign the dummy agent un to ag alone. The
correctness is given by Lemma 3
B.2 Example of A
Consider the first instance in Example D and let assume that we are in the case with k
1, implying that the condition Line is is satisfied, so we can start with the first iteration. In the first iteration. where T = (1.1), 1). the network and its maximum flow constructed in Phase 1 (Lines 6) have been discussed in Example 2 already. Hence, we proceed with line 7 Let the maximum flow f be as indicated in Example 2 i.e.. fā,, t) = f(ā2, t) = 1 and f(a, t) = 0. Since f does not have value [V| = 3, we proceed with Phase where we find an obstruction in Lines 8 We start with V' = {6x} and A' = (1 since 6g is the only vertex with f(0g, f) O. In the while-loop in lines 10 14
meaning that we can ignore ag and the dummy agents. Initially, T|a = T[a2]
we first find à and compute A' {-,]- J. Then, we compute V' (0g, ú in line 13 Since no further post à exists that has an arc to any agent è in V (see the figure in Example
we stop
with A' {ar} and V = {63, }. One can check that aj would stay with congestion one, then no CP assignment can exist since both ei and e3 would envy the only agent that is assigned to a We will later show that in order to have a CP assignment, is necessary to increase the congestion of every post in A'. In Phase 3. we increment T| to 2, while the other post stays with T[ag] 1. This completes the first iteration.
At line 4 since T[a + T[a2] = < V we continue with the second iteration. In the following, the tuples considered in Construction 2 are boldfaced.
01: (a1, 1) >
(a1, 2) ~ (az, 1) > (a2, 2) >
02: (ar,
(a2, 1) (a1, 2) (d2, 2)
0g (0r, 1) > (a1, 2) > (02, 1) > (02, 2) >
One can verify that among all tuples (a, a e A, tuple (a1. 2) the most preferred tuple of vi
and Ug. while (02, 1) is the most preferred tuple of 0j and U2 Hence, the network and maximum flow (highlighted with red lines) constructed in Phase are as given in Figure note that this corresponds to the bipartite graph in Appendix
In Line 6, verify that the maximum flow is a perfect flow (i.e., with value VT). Hence, we derive and return an assignment according to Definition 2 This is exactly II, from Ex
One can verify that the second instance of Example where every agent has the same preference list as 1/ will lead to the sum of the congestion entries to exceed [V] = 3 in the second iteration, certifying that the instance does not have CP assignment, matter with or without empty posts.
22

---

1:1
11
1:0
1:1
2:2
01
1:
2
1:1
1:1
022
1:1
13
Figure 2: Flow network for iteration 2 where = (2, 1). For more information, see Appendix B.2
B.3
Proof of Lemma 4
Lemma (+). Each (A', V1) computed in Phase in lines 8- is an obstruction.
Proof. Let (A', V') be the pair computed in lines 1 in some iteration z. Let (G, c) be the network with G = (Á U U {s. (s, F') and f the maximum flow computed in this iteration. We aim to show that (A', V*) satisfies the properties in Definition 3
By line f fails to have value [V], i.e. Esev f(ě, < IV.. Hence, there must be vertex d" E V with f(ö t) = 0. Let 0* be such vertex that added to V" in line 9 Then, the first part of
property is clear since 0" V' (line 9 and we only add vertices from V V'; see line 13
Property ii is also clear due to line 11
Let us consider property (ii.. Clearly, for every vertex à E A' with (á, (a) E E(G) we must have that f(s,, a) = c(s, a) as otherwise we could increase the flow by one by setting ['ss, â) f(x a)
and [(, 8*) = [("" 2) 1. By line 13 every out-neighhor i of à with f(ā, 0) 1 is added to V".
Together with 0* we obtain that c(s, a) < Hé E V' (a, 8) E E'l since f(v", = 0, as desired.
Consider an arbitrary vertex à E A' with (a, 0*) & E(G). Suppose, towards contradiction, that does not satisfy property (ii), meaning that c(x, a) 2 H V (ā. V²) E(G) We aim to show that there an "augmenting" path from zero and one, which is a witness for the flow to be not maximum.
0", with ares having flow values alternating between
Observe that in each round of this loop, we aim at finding a vertex à not already in A' that has an out-are to some agent-vertex from V", V' is initialized with V" {6*) This implies that we can find vertex in é V' \ {ō²} due which we add à in each vertex o² in V ((*) ). we can also find a vertex d' in previous round such that f(a', (²) = 1 in line 13 Let åz be the vertex from A' due to which we add ig i.e., f(āz, 0z) 1. out-arc with capacity one, due to the conservation constraint of the flow f, we infer that [(ā 0z)) = 0; recall that [ā,, 2x) = 1. Repeating the above reasoning, there must be a vertex - from V {0z} due which add á... Then, either é.- 1 6* or 6z- + 6*
Let us go through the repeat-loop in lines 10-14 14
line Further,
Since each vertex in V has only
In the former case, infer that (a, G.. åg. 8*) is an augmenting path since by assumption à has enough capacity to accommodate all incident agents, including ég. Thus, flipping the flow values along the path would increase the value of the flow:
(s,,))=(ss, ((s 1, f(ā, 0z) 1, f(āz, 0z) = ((āz, f(0",)) 1, contradiction.
In the latter case, since V is finite and vertex from V can obtain more than one positive flow, by repeating the above reasoning, we must end up with an are to 6* with zero flow; recall that i* e V Then, again obtain augmenting path P (ā, êz ag..... åg, 0o 6*). Analogously, we increase the total flow by flipping the flow values along this path, a contradiction.
It remains to show property fiv vertex â E A' and set [(ā o) 1) = 1. particular, the starting vertex 6* would have positive flow going through it, a contradiction.
This is clear since otherwise for each vertex é E V we could find
D
23

---

B.4 Proof of Lemma 5
Lemma 5 (+). Assume that I admits CP assignment II with no posts being empry. Then, for each iteration 2 2 1, each obstruction (A', V") found in iteration 2, and each post E A, the following
holds. If â E A', then [II(a)] 2 T. Ta 1; otherwise [I[{a)] 2 Ty[o].
Proof. Let us consider the first iteration and let (A', V*) be the found obstruction. Since IT does not have empty posts, the statement clearly holds for all posts a E with & A'. Let N (G, c) denote the network and f the maximum flow of N computed in the first phase. Let P = {u E V E V'} and Q = {a E A | ā E } be the set of agents and posts that correspond to the vertices in V" and A', respectively.
Suppose, for the sake of contradiction, that there exists a post a E Q with [I(()) S Ti = 1. By Definition mmp. more than c(s, a) = Ti [a] = 1 vertex from V is incident to à in G. By Construction at least two agents from P consider (a, 1) as one of the most preferred tuples.
Since [Taa] S 1, at least one agent from P is not assigned to a but considers (a, 1) as one of the most preferred tuples. Let Up P be such an agent. Then, he must be assigned to some other post ao such that (ao, [I(()))) )) is one of the most preferred tuples for to as well. This implies that since we are in the first iteration. By Construction 2 v). we infer that (āg, 8o) E(G),
[[((
and by line 11 that âo E A'.
By Definition jin. more than c(s, âg) = Ti [ao] vertex from V is incident to åg in G, and we can find another agent 81 E P that is not assigned to ag but considers (ag. 1) as one of the most preferred tuples. Again, this agent 11 will be assigned to some post a1 with (a1, 1) being one of the most preferred tuples of vn. By Construction M we infer that (01, 01) E E(G), and by line 11 that
â1 E A'. Repeating the above reasoning, we will be able to find distinct vertex à; A' for each
vertex 0; E V' such that [Ta;)) = {o That is, | 2 [V'), a contradiction to Definition Iv since [A'l = - c(s, a) < [V'| in this case.
Now, let us consider other iterations. For each x, let (A',, V') be the obstruction found in iteration 2. Note that the table entries never decrease. Hence, if the statement were incorrect, there must be an iteration = 2 2 where the statement holds in all iterations 2' S 1 but not in iteration z.
Suppose, for the sake of contradiction, that the statement is incorrect and let be the index of the first such iteration where the statement is incorrect. That is, in all iterations z' S z 1, we have that for all a' E A,
if á' E A',, then MMaa)) 2 T2-aa + 1; otherwise IIT(a)) ) 2 T [a']
but there exists a post a such that
if å E A', [[aa]] S Talo] if & A', then [I[(a) < Tz[a].
(2)
First, observe that à E A' since otherwise (Ta) 2 Ta-1ja] [a] = Tg [a] by line 15 contradiction to the assumption.
Next, we claim that [a] = [[(a)). (.))..r. l A' (i.e.. à was in the obstruction found in iteration
1), then by assumption
2 and by line 15, we infer [[a]]] > T_ T__1oa [a] + T. [a] 2 [T]]], as
desired. If å & A²- then again by assumption
and by line 15 we infer [I[(a)] 2 T Tz-1(q]
T. a 2 [.)] as desired as well.
Recall that we inferred that à E A'. Let (G, c) denote the network constructed in iteration z. By
Lemma 4 (A', V.) is obstruction for (G, c). Let E V be the starting vertex with f(0", 0.
By Definition 3 i1I more than c(s, a) = [2(a) vertices from V² exist that have a as an in-neighbor. By Construction v) more than T2 [a] = [[[(a)] agents from V consider (a, [a]) as one of the
most-preferred tuples among all (a', [a')). Hence, at least one of such agents is not assigned to by 11.
Let i E V be a vertex whose corresponding agent e considers (a, [[aa)) as one of the most preferred tuples but is assigned to some other post a' + a. Then, (ā. 6) E E To prevent from being envious (recall that no post is empty), we must have that (a', [[(a)) Z (a, [I(())).
We claim that á' E A' as well. Since (a, M(a)]) is one of the most-preferred tuples of among all (a', T2 [aa"). by previous paragraph and by congestion aversion, we infer that Tz(a') 2 ITaa)). If T3 > [I((a)), ), then by line 15 there must exists an iteration 2' [z 1] where à' E A.
24

---

and Txy [a' = [Ia)),, a contradiction to ① Hence, Ta [I[(a'), implying that (a', Ta(aa)) is
also one of the most preferred tuples of among all (a" T. [I][a"]). By Construction 2 M.. we have
(á', 6') E F. and by line 11 we have à' E A as desired.
By Definition from a'. By Construction 2 more than =(a')= [aa'a] = [[{())) agents consider (a', [I[(a))) as one of the most preferred tuples among all (p. (p.) A.
we infer that more than c(a') [=[aa] = [T((a') vertices from V have in-ares
Analogously, we can again find another vertex d' E VL such that v' considers (a', [I((a')) as one of the most preferred tuples among all (p. P E A, but is assigned to some other post a" o a' with d² E A² and Tg [a"] = [[T(a") By repeating this argument, we infer that every vertex E A has T3 [a
[[] By Definition 3 lv). we have that [V' Eaes, (ss Σaea; Ta[a]
Esen [I[ [.) So there must be vertex ja V1 such that is assigned to post with & AL. By line and Construction 2 V let E A with (á, fi) E E(G) such that (a, Talo)) most
preferred tuple of μ among all tuples (p. T=(p)) ). E A.
By our previous argument, we have that [2 [[[())] By CP, we have that (b. (T())) Z.: (o, [a)))) Since (a, T2 [2(a]) is a most preferred tuple of among all tuples (p. T=(p)), E A, we
further infer that [b]b] 2 [I(6)).
Since b & A', meaning by line 11 that (6, ()) & E(G), by Construction
we further infer that
[T(I]] < T3 [b). By line [5] there must exist an iteration z' E [2 - 1| with T2 [b] = (T(b) and T (b]
was incremented. This a contradiction (T) however.
B.5 Proof of Lemma 6
Lemma 6 (+). II is an assignment returned in line 7 then II is CP and has no empty post.
Proof. Let = be the integration and f be the perfect flow based which IT is computed in line 7 By the definition of perfectness (see Definition 2}. the value of f equals the number [V| of agents. This
means that > A [Ma) = [V. By the capacity constraints, we obtain that [V] > Caea [Ta) <
EAEA [a S [V), the last inequality holds due to the while-loop-condingg cono-coonniooonnooooooooonooooat in line 4 Hence, for
each post a E A we must have that [T(a)] = T2[a] since [[a]] & T2[4]] holds by the capacity
constraints in Construction
This implies that II(a)= # 0 since [a 2 1. Hence, to show that 1l is CP, it suffices to show that for each agent that is assigned to post a and for each post a' with a' & a it holds that (a, [[(a))) >. (a', [I) Towards a contradiction, suppose that (a', [I(a'))) > (I(a)) By the reasoning above, it follows that (a', (a')) > Tala), contradiction to Construction
B.6 Continuation of the proof of Theorem
Theorem 1 (+). Algorithm I correctly decides whether an instance has a CP assignment in O(m2. (n + m) time, where m and denote the number of posts and agents, respectively.
remains to analyze the running time. The main body of the algorithm is a for-loop (line I and has at most iterations. In each iteration k. the algorithm constructs new instance I according to Construction Note that / has O(n + m) agents and 0(m) posts, and it can be constructed in O((n + m) time since each agent has O(n + m) tuples in his preference list. Then, we continue with the big while-loop in lines 16 If we can show the while-loop run in O(m (n + m)) time, we obtain our desired running time of O(m² (n + m)²).
So, it remains to analyze the while-loop. In line initializing the table T needs O(m) time. The while-loop (lines 15) runs at most times since no table entries are ever decreased and in each iteration at least one table entry is increased by one. For each iteration, we first construct a network N = (G, c) based on (T, T); see Construction 2 The directed graph G has O(n + m) vertices and O(m - n) arcs, and each capacity value is in (n). Hence, constructing the network needs Om n) time.
25

---

Afterwards, there are three phases, The first phase (lines 5 finds a maximum flow for N and checks whether its value is [V]. Computing maximum Hlww can be done in O(m n) time and comparing two values needs constant time. Hence, the first phase needs O(m n)) time.
The second phase (lines 8 14 finds an obstruction (A', V*) by first finding vertex i with f(o", O. This can be done in ( time if we store such information when we compare the value of the flow with [V] in the first phase. Hence, the initialization of V" and A' needs ((1) time. Then, the algorithm goes to the repeat-loop in lines I0 14
To analyze the running time of this loop, we observe that there are (m n) ares between A' and and each are only needs to be checked at most once during the whole loop (line 11) Adding new vertices to V can be done in O(m n) time as well since for each newly added alternative à there are at most vertices é from V with positive flow from à to 0. Hence, the repeat-loop needs O(m n) time.
It is straightforward that the last phase (lines 15 15 runs in O(m) time. Summarizing, we obtain that the desired (m n²) time for the shop.-loop.
C Additional Material for Section 4
C.1 Correctness of the Construction in the Proof of Theorem 2
Theorem (+). EF+TG is NP-complete; hardness holds even if there are no ties.
Proof of the correctness of the construction. Correctness. It remains to show the correctness, i.c., I has an exact cover if and only if l' admits an EF and TG assignment.
For the "only if" part, let J C [m]] denote an exact cover for Then, we claim that the following assignment II is EF+TG:
For each j E J, let I[aa)) = fv u, E C,}-
For each j E [m] \ J. let ((ay)) 0.
Let (T(b)) ) = {.g | [2m]) and (T(b2) { E [2m]]-
Since each set-post contains either zero or three agents, no dummy agent envies any element-agent. The dummy agents also do not envy each other due to their preferences. Similarly, no two element- agents envy each other and no clement-agent envies any dummy agent since he does not like by or b2 more.
For "if" part, let II be an EF and TG assignment for the constructed instance. We aim at showing that the set-posts that are assigned element-agent aggentt-agents constitute an exact cover. To this end, let J {j Bu, with o, E I. We first show two claims.
Claim C.I.1. For each set-post oz it holds that [Ma))) E (0,3).
Proof. Since there are 2m dummy agents {PI. P2.......... p2m. J. but there are only m set-posts, at least one dummy agent, say Pa, is not assigned to set-post alone. Hence, for every set-post ay. it holds that [[a)) * 1 since otherwise pa would envy the agent that is assigned to aj. Since the maximum congestion for every set-post is 3. further infer that III II(a))) [ {0,2, 2,3) holds for every set set-post aj- In particular, this implies that no dummy agent P. with S 2 I 2m is assigned to a set-post alone.
Towards a contradiction, suppose that there exists a set-post aj with [T({))) & (0.3). This implies that (Ta)) = Then, every dummy agent P. with 1 S A 2m is to be assigned a set-post since otherwise he would envy the two agents that are assigned to aj. Since there exactly 2m dummy agentspi, ... P2m. this means that every set-post ag x E [m]. must have [1(x)) 2. Then, no other agent can be assigned to the set-post. However, all element-agents will envy all p 's a contradiction. This concludes the proof.
(end of the proof of Claim C.I.I ))
By Claim C.I.I we know that each set-post is assigned either zero or three agents. Next, we show that every element-agent e; assigned an acceptable set-post.
Claim C.1.2. For each element-agent v, it holds that II(x:) {ay j E [m] and u, E Cy}.
26

---

Proof. Suppose this is not true, and by TG let e denote an element- ageett that is assigned to by; note that oi does not find b acceptable. Since there are 2m dummy agents qs each with con- gestion 2m for b2, at least one of them is not assigned to by. This agent envies u, contradic- tion.
(end of the proof of Claim C.T.2 o)
Claim C.1.2 implies that J is set cover, while Claim C.1.1 implies that J| S n. Altogether conclude that an exact cover.
C.2 Proof of Theorem
Theorem (+). EF+TG is FPT with respect to the number of agents and the number m of posts, respectively.
Proof. We first consider the parameter n. Let / (A,V be an instance of CONGESTED ASSIGNMENT. Due to TG, each agent is assigned to one of his first tuples. Hence, for each agent e E V, guess (by brute-force searching) which of his first n tuples that v; is "assigned" to, i.e., (a, d). After assigning all the agents, we check in linear time whether this results in a valid assignment, i.e., if we U; "assign" (a, d), then there must be exactly agents that are guessed be "assigned" to (a, d). This check can be done in O(n² + m) time. We abandon the current guess if it does not give a valid assignment: otherwise we proceed to check EF in O(n") time.
Since there are n agents, each with n choices, the whole procedure can be done in O(n" (n² + m)) time, which an FPT time with respect n..
Now, we consider the parameter m. Let V. (Zv)vev) be an instance of CONGESTED ASSIGNMENT. We guess (by brute-force searching) the set of empty posts A' S A in the sought solution. Then, we modify the preference list 2. of each agent as follows: First, truncate 2. by removing all tuples (a, d) with ranks are higher than then, remove all tuples (a', d') with a' in A'. Denote the new preference list as Z. Let = (V, A \ A', (Ed)evv) denote the modified instance.
Since for assignments with all posts being non-empty, CP and EF are equivalent, we infer that I admits an EF and TG assignment where posts in A' are empty and the rest is non-empty if and only if 7' admits CP assignment where all posts are non-empty. The latter problem can be checked in polynomial time via lines 36 in Algorithm The running time depends on the running time the while-loop, which is m(n + m²² time. See the proof in Appendix [.66 more details. Since there are 2d subsets of empty posts to check, the overall running time is 2 m (n + m)), which an FPT time with respect to m.
Clique. The following graph problem is clom-cepee with respect to the clique size 20 We will use it to show W[l]-hardness for finding a maximally competitive assignment.
CLIQUE
Input: An undirected graph G-(U, E), an integer h 2 O. Question: Does G admit clique of size h i.e., size-h subset U" C U which induces complete subgraph?
C.3 Proof of Theorem
Theorem 4 (x), MAXCP+TG is W[ll-hard and in XP with respect to the mumber of unsatisfied agents. The -harddesss holds even if there are no ties.
Proof. We first show the W[r]-hardness by providing parameterized reduction from the CLIQUE problem.
Let 7 (G (U, h) denote an instance of CLIQUE with U [ur, Llan and E fel,..., We create a MAXCP+TG instance I' = (A, V, (2w)eev t) as follows. Let t + h(h - 1). We will show that the agents corresponding to the vertices and edges of a size-h clique the only unsatisfied agents.
For each vertex u; E U, create a vertex-post 0;, a vertex-agent ws, and copies of w. denoted as पł with E [/- 1].
27

---

For each edge E E with et {u;, uz}, create an edge-post by and three edge-agents ej, Ety, and ey.
Create L dummy agents "1,""" IL with L = (U - 2) + (10) - h 1) + (h(h - 1) - 1) +
...
(LE) - (0) (t++)))
Create five auxiliary posts do, do, bo. y, co. Post y shall accommodate all L dummy agents, while co is a "blocker" making sure that agents are assigned to the desired posts.
Let V- = W U
U W.
ep E E, e = {us, ujHt U {z; U {hg | leg- E E} U {ao, do, bo co). where W {wo E U} and
fer
E [L]], and
M,EU
A = {a:
E EUJ
W {
= E [M).
We state the preferences of the agents, restricted to the first n tuples. Here, (a, s, = (a, > (a. + 1) > ... > (a, t) depicts the preference list on tuples for post a and congestions ranging between and Note that we also briefly explain the main purpose of these preferences in italicized text.
Preferences.
The dummy agent v; with i E [T.] has the following preference list:
24: (01. 1, - 2) > (a2, 1, h - 2) > > (aprz) 1. h - 2) > (ao. 1. 1.| h 1h-1) 1)
11 (-
(oo, 1, 1) 1)) (bo. 1. E
(v 1, > (co, 1, + (t + 1) -T))
The dummy agents shall ensure some minimum number of agents assigned to each post (except by and y): At least h - 1, |U| - h, b(h-1), 1), and [E| - (*) agents are to be assigned to a,(i E [UUI], au, ag and by, respectively. The reason is that since at least t++ dummy agents are to be assigned to y or co. they would envy the agents assigned to post if its congestion is less than or equal to the maximun congestion of 24 that post, which is not possible for a yes instance. Indeed, the dummy agents can only be assigned to y.
-he vertex-agent wi with E [[UT]] has the following preference list:
we: (oo, 1, h 1) > (a., 1, 1- 2) > (ao. |0| - h) > (a,, h - 1) (at, h) (co, 1, (U1).
We will show that exactly |U] h vertex-agents we are assigned to ag- Consequently, there remain vertex-agents v, that are assigned to a. They shall correspond to the clique-vertices if G admit size-h clique.
For each i E [[U]], all copy-agents w with E [h - 1] of the vertex-agent Wi have the same preference list:
W (āo, 1)
1) -)
1) > (ão, h(h 1)) 1, +h 1)). (ai, 1
The copy-agents shall ensure that all wi E [h 1h-11, 11. are jointly assigned to either âo or 0g- If they are assigned a, then no other agent (including wx) can be assigned to a, This corresponds to the case that the vertex us is not in the clique.
The edge-agents ex, et and el with
{wi, uj} have the following preference lists:
h
h
h1
e:: (bo, 1, [F
2 1) (be, 1) (bo, |F]
(be, (co. 1, ((F)
2).
2
et: (be, 1) > (bc, 2) > (a;, 1, > (co. 1, h 2).
ef: (be, > (bz, 2) > (a,, h2 > (co, 1. 2).
Note that et can only be assigned be or by- and et (resp. et) only to a, (resp. ag) or be- If ef is assigned by and does not envy other agents, then no other agent can be assigned to be as otherwise least |E| - (2) + agents must be assigned to by. which is impossible due to rop-guarantees Therefore, e is assigned to be, then et and ef have to be assigned to as and aj. respectively. We will show that e; cannot be unsatisfied. and having et and ea assigned to a, and aj, respectively, corresponds to having the edge et in a size-h clique.
The maximum congestions of the agents are depicted in Table
Correctness. Clearly, the construction can be done in polynomial time and no agent has ties in his preference list. remains to show the correctness, i.e., 7 has a clique of size h if and only I' admits a TG assignment with t h + h(h 1) agents being unsatisfied.
28

---

11
bg
W1
h
[0
[
10
h
[
[
h
0
he(h
1)
0
7 4 +
0
1
0
h(h
1)
0
n 422 +
0
0
h
h(h
1)
0
h- +
0
0
0
2
[E]
(2)
([E) - (2) -2
h
h
0
0
h
2
0
11 h 2
22
h-
h-
10
A(h 1)
n (1 + 1) 2L
Table 1: Maximum congestions of the agents constructed for Theorem 4 For an illustration,
assume that et = 4113
The "only if" part. Let C C U denote an h-clique for J. Let EC C E denote the edge set associated with C, i.e., EC fee- {us, mj} ui " E C). Then, we claim that the following assignment II is a TG assignment with /. unsatisfied agents.
For each i, C, assign w; to ag and assign wi with 2 [h- 1] to uo For each u, & C, assign wi with z E [h 1 to as, and assign w; to ag.
For each e, = {ws, uz} } E E assign ef to as ef to aj. and ež to be.
For each eg {u,, Uz} & EC, assign eţ and el to be, and ež to bu- Assign 32 to with 2 E [Z].
Clearly, II is TG with the following congestion vector.
Observation 3. 11 TG and satisfies the following.
(1) [[([]]] |0| - h, [m[)) = 1a(h 1), [bbo)] [E| (2) and [M())] = L. (ii) For each u; E: C, it holds that I1(a;) {w;, wf
2 I
For each u, E U \ C, it holds that [[T())) = {ūr 2 E [h 1]}
(ili) For each eg E E, ifee E then [I[(br]
otherwise [[bb))] 1
Let = (wyl u, E C)UUEe ee E E with e (u,, uy ]. Note that [V*| 1. We aim to show that all agents except those from V" are satisfied. By the above observation, is straightforward that every dummy agent xg is satisfied, every agent that does not correspond to the clique vertices is sat- isfied, and the copies üf of all vertex-agents are also satisfied. It remains to consider the edge-agents that are not in V'. Let E E with e, = {u,, }. Clearly, ef & EC, then the two edge-agents ej and of are satisfied since they are assigned to their most preferred post. Agent ez with eg & F is also sat- isfied since he is assigned to bn with congestion E (*) which is better than (be, 2). If e E E then agent ez is satisfied since he is assigned to by alone which is better than (bo, |E] - (t) ). Hence, only the agents in V are unsatisfied. Since [V' t, this concludes the proof for the "only if" direction.
The "if" part. Let II be a TG assignment with at most unsatistied agents. We aim to show that the following vertex subset C is a size-h clique: {u, [[{) > h). Before we show this, we observe the following regarding the congestions and assignments of the posts.
Claim C.3.1. (1) [I(())] = =IU| - h, [I(āa)] = h(h - 1), and [[bb)] = |E| - (*)
(2) For each uy E U, it holds that [TT(a,) E (h- 1,
(3) For each ez E, it holds that [1I(b2)] 2.
(4) I((a)) C [w; u, E U}, 1l(āo) C {wf i [ E [h - 1]}, and 11(b)) S {ee | le E E}.
(5) All edge-agents E (ej | E E E} are satisfied.
Proof. We show the first two statements together by considering the dummy agents.
Since II TG and the maximum congestion of dummy for ap, āu, by. and with i E [[0]] are ( -1, and h h-2, respectively, we infer by simple calculation that there |U| 1, hah-hhhhh 1) 1, EE|
29

---

are more than & dummy agents who are assigned to y co. Since II does not have more than t unsatis- fied agents, this further implies that there least one satisfied dummy agent z; who is assigned to y or co. By his preferences, every tuple that he prefers to (y. L + 1) must have congestion that exceeds his maximum durable congestion. This implies that [[])] > |U| - h. [TT 2 h(h - 1), and
[I[(b)) 2 E| (")) for [[a,)]] 2 h-1. Since no agent allows more than the aforementioned conges- I = ht
tions (except for (z), we further infer that [Too)) = - a))
([1h-11,, 1), and [TT()))] = |
(2) For as, since the maximum congestion of any agent for a; is h. we infer that / - 1- S [1[(a)) - h.
Statement is straightforward by observing the maximum congestion of any agent towards by is two.
The first part of statement (4) follows from the fact that the only agents that have (au, |0] h) in their top n choices are the vertex- Similarly, we can show that the other parts of statement also correct.
To show statement
let us analyze which agents are unsatisfied. To this end, de- fine W = {w; E W|] wy & II(a))). By statements ① and (4), we infer that [W"| h.
Further, every agent uy in W' is unsatisfied since by statement 2 that [I((a)]] 2 h - 1, any agent not assigned to do will envy those that are assigned to ag. This implies that at most 2(x) agents other than V can be unsatisfied.
By statement (2) partition the posts {a+ u, E U} into A, and A with A = {a= u, E U A [aa))] = h 1} and A2 = {a, u, E U A [aa)] h}. Note that by the cop-guarantees. every post a; from A2 can only be assigned vertex-agents w; or edge-agent ot for some edge e E E with u, E eg. However, this implies that every agent assigned to post a, A2 is unsatisfied since wa prefers (an, |U| h)) to (a,, h - 1) and every edge-agent et (with u; E ex) prefers (b,, 2) to (as, h);
recall by statements (1) and 3 that (ao) = |U| - h and [[bb)) < 2. This further implies that |A2| S h since / - h h(h 1) = h22 can be unsatisfied.
By statement ( we have that [11( h(h - 1). Since every vertex-agent has h 1 copies. there are at least h vertices each of which has a copy-agent assigned to ãg- Since every copy-agent ej corresponding to vertex u; prefers (a,, h 1) to (āo, h(h - 1)), it follows that at least / |Aa] copy-agents will be unsatisfied, namely those whose corresponding vertex-post. has congestion h 1.
Since at most h vertex-post ag the number of edge-agents ej that have be assigned to some vertex-post a, is at least
and at most (IU) h 1) copy-agents can be assigned to any
A1 (h - 1) + |42) - h (h + (UU) - () 1)) h(h - 1) - (h -A21).
Observe that each edge-agent ef that is assigned to some vertex-post a; is unsatisfied. This implics that at least h(h- 1) (h- - [A2]) edge-agents are unsatisfied. Together with the h - |Agl unsatisfied copy-agents, no more other agent can be unsatisfied. In other words, every edge-agent oj must be (end of the proof of Claim C.3.1 ()
satisfied, as desired.
Now, we are ready to show that C is a clique of size h. We first show that C has size h. Define
W' = [w; [Tw;;) j on)- By the preferences of the vertex-agents and by Claim C.3.1 D.. |W h
and every vertex-agent in W is unsatisfied. By Claim C.3.1 and by the maximum congestions of the agents towards by, we infer that (bb)) consists of exactly ('El-(") edge-agents ez, l E [[E]]
By Claim C.3.1 every remaining edge-agent eū that is not assigned to by must be assigned the corresponding edge-post by alone. This implies that the remaining two edge-agents ej and e² with e, = ( } are not assigned to by and hence unsatisfied; they both envy e7. Define E" = f 11(e;) bb): be). Then, [b'| = h(h-hhhh 1) and it yields h(h-1) unsatisfied edge-agents by Claim C.3. Together with the h unsatisfied vertex-as aagents in W we infer that every copy-agent uf is sanssied. In particular, it means that for each copy-agent úf that assigned to âo must hold that [[(a)) = h. Recall that there are at least h vertices u, each of which has copy- assigned to āg. This further implies that there are least h vertex-posts that each have congestion h, that is [C] = h.
It remains to show that C is clique. Let E" = fer of E Ma;;) for some i, E C} be the set consisting of all edges whose corresponding edge-agents are assigned to some vertex-post. Clearly, | (4) since C h; note that the equality holds only if C induces clique. Towards contradiction, suppose that C. contains two vertices u, and uj that are not adjacent with each other.
This implies that |E"| (t) Let consider each edge el E E and let e {u, uz} } with i < j.
30

---

By definition, at least one of the two edge-agents ej and e/ is assigned to a; and he is unsatisfied. We claim that both edge-agents are unsatisfied. Without loss of generality, assume that I[(e)) = and is unsatisfied. If e is assigned to vertex-post O, cu, then he is unsatisfied as well. Otherwise, of is assigned to post by alone, making ej unsatisfied which is not possible according to Claim C.3.
Hence, both et and ez are satisfied. Since there can be only h(h 1) unsatisfied edge-agents, we conclude that E² (2) desired.
Now, we turn to the XP result. The ideas to guess the unsatisfied agents and the posts that they assigned to, and replace them with dummies and run Algorithm I for the reduced instance. More precisely, we guess who are the unsatisfied agents O(n') time; denoting the set of unsatisfied agents as V* {ef ..i....... vi For each V*, we further guess which posts they are assigned to in O(m²) with a being the post that 2i will assigned to and z E [t].
time, denoted as A {ai....,
........ oj
Then we create dummy agents P = {p= ps: (a;,1) >-..>> n) >
E [t] and set their preference list as We replace the agents V with the dummies and use Algorithm to solve the resulting instance. If Algorithm reeurns no on the current guess, we proceed with the next guess; otherwise, TT be CP assignment returned by Algorithm [ is straightforward that replacing each dummy P. with o in the assignment yields a TG assignment with at most t unsatisfied agents.
The overall running time is On''m²).
C.4 Proof of Theorem
Theorem 5 (x). MAXCP+TG is FPT with respect and in XP with respect m, where and m denote the number of agents and the number of posts, respectively.
Proof sketch. Parameter We first guess subset V of unsatisfied agents. Afterwards, similarly to Theorem 3 we guess for each satisfied agent V \ V' one of his first n tuples and check whether the V V guesses yield valid assignment Ny and store the number of unsatisfied agents. Finally, we select one valid IT with fewest unsatisfied agents. The whole approach can be done FPT time wrt.
Parameter m: For the XP-algorithm, we guess the congestion vector with øī.] E {O...., n) and Σs and use the algorithm behind Lemma 2 to determine the minimum number of unsatisfied agents. The overall running time is n (m + n 011), which is XP wrt. m.
C.5 Proof of Theorem
Theorem 6 (+). Deciding whether an instance of CONGESTED ASSIGNMENT has an assignment with at most unsatisfied agents is W[1] I-ard with respect to t.
Proof. We reduce from the W[1]-complete problem CLIQUE; the definition can be found ahead of Appendix C.3
Let I = (G = h), denote an instance of CLIQUE with = {ui,... un and E {ei,..., Cmh being the vertex set and edge set, respectively. Without loss of generality, we as- sume that á 3h ( and m > 2h 2(h) the problem remains W[r]-hard in this case.
The idea is to construct an instance I' = (A, V, (Ee)eev) of CONGESTED ASSIGNMENT such that the unsatisfied agents correspond the vertices and edges of a size-h clique. We set the number of unsatisfied agents to 2h + (?), and let and R two very large numbers such that L > and
R > (L + 2) (ñ + m) + h. For the sake of brevity, let N (L + 2) (ñ m)) + 2R, and we will create exactly N agents.
Posts and agents.
For each vertex u; U, create one vertex-post o; and + vertex-agents wi, Pis př. (L]. For each edge e, E E, create one edge-post by and L + 2 edge-agents et, fē. E [L. 1). Create 2R dummy agents Z2, Uz. [R).
Create 3 auxiliary posts ag, bo, and cp.
31

---

Let A = {a; E [+]] B= Bb: | = (w;
i [n] P
2 E [L].i E [i]], Ft {fz 2 X (z=
2
R I. and Y (y= ZE [R]] Then,
we set A = AU BU U (ao, co), and V = WUPU U PUEU U RUXUY, In total, we
fE[m]
have created + r + posts and N agents.
Preferences. For two numbers s, E [N] and post E A, let (a, = (a. (a, ++, 1) > > (a, t) depict the preference list on tuples for post a and congestions ranging between s and t. The notation "* * ** refers to an arbitrary but congestion-averse preferences of the tuples that are not explicitly mentioned.
(i) For each vertex u4 E U, the vertex-agents wA E W, Pr E P. and pt E Pi, E [L], have the following preference lists:
wy: (,0,1, 1, h)
h) > (a,, + > (co 1, N) > *** (60, 1, (ao, f h h+1,N,, Ps: (, L +)) > (do, 1 - h) > (a;, + 2) > (co, 1,) > **** (l,, 1, NN > (0o, á + 1,
p/: (a., 1,,11, > (co, N) ***> (bo, 1, N) (ao. N).
(ii) For each edge et E E, the edge-agents ez, f7 2 E [L + 1], have the following preference lists, where we assume Eg = {u, uz}:
ee: (60, 1, m (1) > (be, 1, > (co. N, > + *** > (bo. m
+ +1, > (a0, N,,
2
f: (be, 1, > (a;, 1, I+ 1) > 1, 1, 1) > (be, L +2 > (co, 1, N) > ****
(bo, 1, > (ao: N)-
(iii) The preference lists of the dummy agent v2= X and y/2 E Y are as follows:
zz: (a0, 1, h 1) > (a1, L) > (, L) > (co, 1, 2R) (a1, L + +1, .... >
(as, L + N) > (co, 2R + +1, 1, N) > >+**> (bo. 1, N) > (ao, á h, > (co.
11
yz (bo, 1,
- 1) > (b1, 13 > ... (bm 1, L) > (co. 1, N) ****
2
11 N) > (ao: 1, N).
(bb m
This completes the construction of the instance I', which can clearly be done in polynomial time.
Note that it is also a parameterized reduction since the parameter / = 2h + (b) is polynomial function in h. It remains to show the correctness, i.c., I has size-h clique if and only if I' has an assignment with most i unsatisfied agents.
For the "only if" part, let U be a clique of size h. We construct the following assignment and show that it has most t unsatisfied agents.
(1) For each vertex u, E U, assign all agents from P. (p:} to a, Additionally assign w; to a ", E U"; otherwise assign Wi; to ag-
(2) For each edge e, E F,, assign all agents from Fg to by. Additionally assign eg to by if eg S U",
i.c., both its endpoints are in U'; otherwise assign eg to bo-
(3) Assign all agents from X Y to co-
C To see who is unsatisfied, let W = fw; E W w; E [(a))), P' = (p: E P. E [(a)), and
E' = fer E E ee l[bb))). We claim that all agents but those from WUPP' U' are satisfied.
In the following, we say that a post a is the most preferred post for agent if every tuple that is contains post other than a is less preferred than (a,, [[a)])- Further, tuple (a, d) is most preferred feashile tuple for agent g if every tuple (a', d') that is preferred to (ar, d) has congestion [T(a')] > d'.
Clearly, every agent in X U is satisfied since (co, 2R) is his most preferred feasible tuple. Every agent in U P.) U (W \ W') U (P PP) (E \ E") is satisfied since he is assigned to his most sE[A] preferred post. Every agent fi Fe is also satisfied since either he is assigned to his most preferred
32

---

post (if eg is not "clique" edge) or [[(a:)] = = =
= + so (be, L ++2) 2) remains his most preferred feasible tuple. This concludes the proof for the "only if" direction.
For the "if" direction, let IT denote an assignment with at most & unsatisfied agents. Before we construct clique, let us analyze the preferences and IT would look like.
Claim C.5.1. satisfies the following.
(1) [[(a))] = á h and [I1(bo)] m
(2) Every agent from W that is not assigned to on is unsatisfied and every agent from E that is not assigned to by is unsatisfied.
(3) For each a; E A we have that (I))):) ) 2 L+ and each by E B we have that [II(br)] 2 L+1.
(4) It holds that [I[() < 2R.
(5) For each a; E A we have that [[T():)) < L 2 for each by E B we have that [T( S L
Proof. Statement (T]: The lower bounds are straightforward since all agents from W U X prefer (oo. á - h 1) to any other tuple that does not contain ag: If [II(ao)] | < á h would hold, then more than |W U UX| (ft h) > R agents will be unsatisfied, which is not possible since R > (L+ + 2)- (f + m) t. Similar reasoning shows that [I[(b)) 2 m (+) by considering the preferences of EUX Y. Now, we show the upper bounds. Suppose, for the sake of contradiction, that [Ma) > â h. Then, since no agent considers (ao, ú h 1) more valuable than any other tuple that does not contain dg. all agents assigned to dg are unsatisfied. Since we can assume that â >> 3/2 + (2) it follows that more than t agents will be unsatisfied, contradiction. Similarly, since we have just shown that [I()) I â - h, from the remaining possible tuples, no agent considers (bo, m ( more valuable than any tuple that does not contain bo (except (ag, á - h + =), 2 1, which is excluded). Consequently, by the fact that r 2h + 2()). infer that [II(bo)] S mn as otherwise all agents assigned to bn are unsatisfied the number of which exceeds L.
Statement 2 This statement follows directly from the previous statement and from the preferences of the agents in W E.E.
Statement 3): We show the lower bound by iterating through all i [n]. By Statement I every agent X U Pi [pr} prefers (a1, I.) to every other tuple that does not contain a1 (excluding ag). Hence, ((1) 2 L++1 1 as otherwise more than R - T. > l. agents from X are not assigned to and
will unsatisfied. By applying the above reasoning for the next i 2, we infer that [T();)) 2 L+1
holds for all E [r]. Similarly, we infer that [11(6b)] > L + holds for every & E [m...
Statement : Suppose this is not true, i.c., [I()) 2 2R + Then, by Statements I 2 and by the bound f 2/ + (t), at most h agents from V \ (W E) can be unsatisfied. By construction, every agent in X that is assigned to co will be unsatisfied since he prefers (a1, L 1) to (co. 2R 1).
Hence, at most h agents from X can be assigned to co. This means that at least 2R + 1 h agents
from W UP U PUUUU U FYUY need be assigned to cg- This is not possible however
+E(A)
(E(M)
since R > 2)) (A + m) + h and |Y| = R.
Statement 55 Let E [m]. The statement follows directly from the fact that every agent
prefers (cg, 2R) to (a,, L + 3) and [T(())) < 2R (see Claim I [Ma)))] > I + 2 would hold, then all agents assigned to d; are unsatisfied, the number which exceed / since >>> 2t.
(end of the proof of Claim C.5.1 o)
The next statement is about the structure of the agents assigned to A U B.
Claim C.5.2. Lei A' = (ar E A: [aa))) = L L+ 2} and B' = {br E B: [1bb))) = + 2). Then, II satisfies the following.
(1) [A + BB| 2 h +
(k)
()
(2) For each post ag E A', at least two agents in I[a,)) are unsatisfied; for each post be E B', at
least one agent in I[(be) is unsatisfied.
(3) |A'l < h and B'| > (h)-
(4) For each post be B' it holds that [[(a:)] = [I(aa)) = L + where ct {Wi, Uz].
33

---

Proof. Statement ① This can be shown by simple calculation. By Claim C.5. and 4 at least
(I+ 2). (ń rh) (á h) (m
(L++1 1). (á + m) h + (2) agents are assigned to the each post in B is assigned either + L. + agents. That is, least h of the post A B are each assigned L + agents, confirming that [A + B
posts of A U By Claim C.5.1 and 5
2 h (2)
Statement 2 For each post a, E A', since [TT(a))) I. + and |P,| L, at least two agents in [[a))) are not from P., i.e. [I{(;;) Pil 2 2 We claim that the agents in II(a:) \ Pt are unsatisfied prefers (ao, á
by considering the preferences of all agents except P:: Every agent from W
h) to (a,, L + 2). Every agent from E prefers (bp, m - (2) ) to (a,, L + 2). Every agent from
(UEMM) Pt) (Uee(m) Fe) X U prefers (co. 21) to (a;, + 2). Since [II(ao)] á h,
[II(b)) m (*), and [I(co)] s 2R (see Claim C.5.1 1 and 4). we infer that every agent in Il(;)) P. is unsatisfied.
Similarly, for each post by E B', since [IT(b:)] = + 2 and Fr = L + at least one agent in lIbb)) is not from Fr. We claim that the agents in II(bb) F3 are unsatisfied by considering the preferences of all agents except P:: Every agent from W P (Ule(a) P.) U (UPeMI))) Fe) U X UY prefers (co, 2R) (be, L + 2). Every agent from E prefers (bo, m (*) to (be, L + 2). Again, since [11(bb) = m (2) and [I((co)] S 2R (see Claim C.5.1 and we infer that every agent in (1b;)) Fg is unsatisfied.
Statement 3 Statement 2 implies that at least 2|A4|| + [B'] agents are unsatisfied. By the upper bound that S 2h- + (%) and by Statement I infer that [A'] < h, and hence [B'] > (7)
Statement Suppose, towards a contradiction, that (T:)) [[a=:]= * L 2. Then, by Claim C.5.1 3 and ( it follows that [Ta)))) I. 1. We claim that every agent assigned to by is unsatisfied. Let us consider an arbitrary agent E [T(bb). Clearly, if E WUPUUsaMM) PUUUUUUUUF ((ee)UF)) then he is unsatisfied since he prefers (co, 2f) to (be, 2). If ez, then he is unsatisfied since he prefers (bp, m (2) to (+,, 2), while if q Fs, then he is unsatisfied since he prefers (a;, + 1) to (be, L + 2) as well. This concludes the proof that every agent in I1(b²) is unsatisfied, implying that more than 21 agents unsatisfied, a contradiction.
By an analogous reasoning, we can show that [I[(a)) = L L+2 2. (end of the proof of Claim C.5.2
Now, we are ready show the existence of size-h clique. By Claim C.5.2 B). B' corresponds to at least (t) edges. Hence, there are at least vertices incident to any edge corresponding B' For each vertex a; that is "incident" to any edge-post in B', we know by Claim C.5.2 4h that its corresponding vertex-post a; must be assigned + posts. By Claim C.5.2 there are at most such vertex-posts. Hence, there are exactly h vertex-posts that are each assigned 2 agents, and this is possible if and only if they form a size-h clique.
34


Reviews:
[{"review_id": "ZTAQNpqCeF", "reviewer": "Reviewer_US9b", "summary": "This paper studies congested assignment problems in game theory and shows a poly-time algorithm that determines whether there is a competitive assignment (resolving an open question of Bogomolnaia and Moulin). The paper also shows that finding envy-free or maximally competitive assignments is NP-hard, but shows parameterized algorithms for these problems with respect to the number of agents or resources.", "questions": "- Are there any immediate practical applications of the algorithms proposed?\n- Could you empirically validate these algorithms?\n- How would you introduce and motivate this work to audiences outside of algorithmic game theory? What is the significance of this work to other areas of CS/theory?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Well written paper that resolves a recent open question with a nice reduction to network flow\n- Shows that finding other kinds of assignments that may be natural to think about for this problem is NP-hard\n- Shows FPT algorithms for these NP-hard problems\n- Nice related work section that places this work in context\n- The problem itself (assigning agents to resources, with cost functions associated with each resource depending on the number of agents assigned) feels natural, hopefully indicating that this work could have broader consequences. The notion of a competitive assignment also seems natural, and it is quite interesting that competitive assignments can be found in polynomial time, while other kinds of assignments that one may want (Envy free, top guaranteed) are NP-hard.\n\nWeaknesses:\n- Could elaborate on some practical applications of the proposed algorithms -- it would be nice to indicate some real-world settings where this problem could be applied, and where the algorithm proposed may be relevant. Some suggestion is made that this could be applied to settings like urban traffic -- expanding on this, and perhaps presenting some initial experiments could significantly strengthen the work.\n- It would also be interesting to elaborate on further potential consequences of this work to nearby areas -- for example, should one expect this dichotomy between the polynomial time computability of competitive assignments and NP-hardness of envy-free and top-guaranteed assignments to be a broader phenomenon outside of just this particular setting? What are the technical challenges involved in generalizing the results here to the weighted agents setting? \n\nOverall I am impressed with the clarity of the work and technical results. However, I am not an expert in game theory, and have very little to no experience in the area. I am also skeptical of the practical applicability of the results, which seems like a downside for a conference like NeurIPS.", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your helpful comments! Below we address the questions raised:\n\n* Are there any immediate practical applications of the algorithms proposed?\n\nAnswer: The algorithm can be used for school/class allocation: Assigning students to classes or schools while considering class size (congestion) is critical for fairness. The algorithm can check whether there is an allocation where no student is envious of others' assignments and no classroom is unnecessarily empty. Another example is server task allocation: distributing computational tasks across servers to avoid overloading (congestion) can be optimized using these algorithms, preferences of task are based on both the distance and the congestion of the servers. Our algorithm can determine whether there is an assignment of the tasks to the servers such that no task would be envious or switch to an idle server.\n\n* Could you empirically validate these algorithms?\n\nAnswer: Yes, our polynomial-time competitiveness algorithm is based on network flow and can be implemented straightforwardly. The parameterized algorithms are also directly implementable using simple brute forcing. While our paper focuses on providing theoretical analysis of congested assignment complexity, we believe empirical validation would be a valuable and interesting direction for future work, which we will add to our conclusion. Thank you for this suggestion.\n\n* How would you introduce and motivate this work to audiences outside of algorithmic game theory? What is the significance of this work to other areas of CS/theory?\n\nAnswer:  *Motivation outside AGT*: Congested assignment problems appear in traffic management and school choice, where agents care about both resource quality and congestion levels. This connects to multi-agent systems and operations research.\n\n*Significance to other CS/theory areas*: Our polynomial-time algorithm are directly implementable for resource allocation or school choice problems with congestion-averse agents. The parameterized algorithms are based on brute force searching and simple to implement as well."}, {"review_id": "PqefvGnRWy", "reviewer": "Reviewer_3HLj", "summary": "This paper studies *congested assignment problems* involving agents with preferences not only over resources (posts) but also over the congestion levels of those resources. The agents are assumed to be *congestion-averse*, meaning they prefer fewer co-users on the same resource. The study focuses on various fairness criteria, particularly **competitiveness (CP)**, **envy-freeness (EF)**, **Nash stability (NS)**, **top-guarantees (TG)**, and **Non-wasteful (NW)**, where CP implies EF and NS, and NS implies TG and NW.\n\nThe primary contributions are:\n- A **polynomial-time algorithm** to decide whether a *competitive assignment* exists, resolving an open problem posed by Bogomolnaia and Moulin (2025).\n- Proofs that finding assignments that are both **top-guaranteed** and **envy-free**, or **top-guaranteed** and **maximally competitive**, is **NP-hard**.\n- Development of **parameterized algorithms** for the aforementioned NP-hard problems, focusing on parameters like the number of agents, posts, or unsatisfied agents.\n\nIn short, this work gives both theoretical insights and algorithmic contributions for fair resource allocation under congestion-averse preferences.", "questions": "I would like to double-check my understanding of the concepts presented in the paper:\n\n1. If an assignment satisfies **envy-freeness (EF)** and **non-wastefulness (NW)**, does it satisfy **competitiveness (CP)**?\n\n2. If the answer to (1) is yes, would it be reasonable/meaningful to consider the combination of **Nash stability (NS)** and **maximal competitiveness** as an alternative objective?\n\n3. Are there any immediate implications or known results connecting these fairness concepts (EF, NW, CP, NS, etc.) with **Pareto optimality** within this model? (No need for new results—just existing ones or trivial ones, if any.)", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Although the work is not groundbreaking, it addresses a natural and well-motivated model, and successfully resolves several important problems in this domain. The paper is clearly written and easy to follow. I do not identify any significant weaknesses. A minor point is that the central concept builds upon ideas introduced in prior work.", "was_revised": true, "final_justification": "While this work does not break new ground, it examines a well-defined and meaningful model in fair allocation, solving an important open problem. The authors have fully addressed all raised concerns. Consequently, I believe the current score accurately reflects the paper's contribution.", "rebuttal": "Thanks for your helpful comments. Below we address the three questions raised by you:\n\n1. If an assignment satisfies envy-freeness (EF) and non-wastefulness (NW), does it satisfy competitiveness (CP)?\n\nAnswer: Yes.\n\n2. If the answer to (1) is yes, would it be reasonable/meaningful to consider the combination of Nash stability (NS) and maximal competitiveness as an alternative objective?\n\nAnswer: Yes, it is an interesting combination to be studied. We conjecture that determining a Nash stable assignment with minimum number of unsatisfied agents is NP-hard, by adapting our reduction for Theorem 4 since NS implies TG. \n\n3. Are there any immediate implications or known results connecting these fairness concepts (EF, NW, CP, NS, etc.) with Pareto optimality within this model? (No need for new results—just existing ones or trivial ones, if any.)\n\nAnswer: Yes, the paper by B&M (Proposition 3) shows that CP implies weak Pareto optimality.\nMoreover, if the preferences do not have ties or if the CP assignment does not have  empty posts, then CP implies Pareto optimality."}, {"review_id": "XjJMJwEbKv", "reviewer": "Reviewer_ZYLc", "summary": "This paper considers post assignment problems with congestion: A is a set of posts (e.g., job postings), and V is a set of agents. Each agent can be assigned to one post, a post may consist of many agents, and the number of agents at a post is the congestion. Agents have preferences over the tuples A x [n], or, posts combined with the congestion at that post.\n\nThey discuss a number of desirable properties in the general area of fairness or stability: Nash stability (NS, no agent should desire to deviate from their post), non-wastefulness (NW, no agent should desire to deviate to an empty post), envy-freeness (EF, no agent should desire to swap with another), top-guarantee (TG, any agent must receive one of their top tuple assignments), and competitiveness (CP, non-wastefulness and envy-freeness). These properties have been previously studied, and it is known that CP=>NS and NS=>TG.\n\nPROPERTIES\nThey show a number of nice properties useful in their main algorithm, but these results stand on their own: CP => EF and NS, but the reverses (respectively) aren't true, NS => TG+NW but the reverse isn't true. Additionally a number of these properties are incomparable.\n\nMAIN ALGORITHM\nTheir main result closes an open question posed by a very paper in the field: is competitiveness P-time solvable? They describe a rather involved algorithm which does so. The main algorithm consists of two main nested loops. In the outer loop, they iteratively check all values k denoting the number of empty posts.\n\nFor a given k, they attempt to compute a competitive assignment. They first reduce the instance with k empty posts to an instance with no empty posts (and show that solutions to these two instances correspond to each other). Given such an instance, they then iterate (in the inner loop) over a sequence of guessed congestion vectors, which bounds the congestion at any post. At first, the vector is highly constrained: each post can only have 1 assigned agent.\n\nGiven a fixed congestion vector, first they check to see if an assignment can be made satisfying the vector. If so, that is a valid solution and they are done. Otherwise, they identify a number of congestion constraints implied by the vector that are necessarily too weak. This is determined using a max flow technique and reasoning similar to Hall's theorem. These congestion bounds are increased by 1, and the loop continues. We stop when the congestions sum to above the number of agents present - e.g., it's impossible to find a solution. This completes the algorithm.\n\nHARDNESS\nThey show that a simultaneously EF+TG solution is NP-complete but also FPT wrt either n or m.  Finding the max CP solution that is also TG is W[1]-hard wrt t, in XP wrt t and m, and FPT wrt n. Deciding if there exists an assignment with at most t unsatisfied agents is W[1]-hard wrt t. Not much detail is given beyond this in the main body of the paper.", "questions": "1. On line 275, should the capacities be T[a] not T[1]?\n\n2. Could you add a proof of Observation 1? I'm pretty sure it's correct, but observations should be immediately obvious. I'm not sure I would even call this an observation, or more of a small lemma.\n\n3. How novel are your results on page 7? You mention they are similar to Hall's theorem - does this not surmount to a b-matching version of Hall's theorem? I'm sure that's already been studied, though I don't know the citation off-hand.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "STRENGTHS: The paper is generally well-written and easy to follow. The technical results are advanced and require a combination of techniques. New results are provided on both the hardness and algorithmic side of the problem, which involve closing an existing open question in literature.\n\nWEAKNESSES: Multiple of the results are under-explained, likely due to space. However I really would have liked more than a list of theorem statements at the end of the paper for much of the hardness section. I think it is more important to give a high-level understanding of all components of the paper than to squeeze in what proofs (or components of proofs) you can fit at the detriment of explanation. It is difficult to get any sense of where these results come from, let alone check for correctness.", "was_revised": true, "final_justification": "The authors have addressed my concerns and I believe this is a solid paper.", "rebuttal": "Thanks for your helpful comments, which we will carefully incooperate in our final version. Below we address the three questions raised by you:\n\n1. On line 275, should the capacities be T[a] not T[1]?\n\nAnswer: Yes, thanks for spotting this. We will fix it in the final version.\n\n2. Could you add a proof of Observation 1? I'm pretty sure it's correct, but observations should be immediately obvious. I'm not sure I would even call this an observation, or more of a small lemma.\n\nAnswer: The proof of Observation 1 can be found in the Supplementary Material (**neurips_2025-congested-app.pdf**: Page 14). \n\n3. How novel are your results on page 7? You mention they are similar to Hall's theorem - does this not surmount to a b-matching version of Hall's theorem? I'm sure that's already been studied, though I don't know the citation off-hand.\n\nAnswer: The whole idea of reducing to network flow and showing that iteratively incrementing the congestion levels of the posts in the found obstruction is correct—these are novel contributions from us. The idea of finding an obstruction if there's no perfect flow/perfect b-matching is a standard technique. However, our obstruction (Definition 3) is slightly different from the standard one for perfect b-matching since we do not require every vertex b-value to be saturated, only the vertices corresponding to the agents."}, {"review_id": "eO70GQGWlS", "reviewer": "Reviewer_Fjvw", "summary": "This paper studies the congestion assignment problem. There are $m$ posts and $n$ agents, and the task is to assign each agent to exactly one post. The congestion of a post is defined as the number of agents assigned to it. Each agent will express a (not necessarily strict) ordinal preference over all (post, congestion) pairs, and the goal is to find a fair and efficient assignment.\n\nThe main result of this paper gives a polynomial-time algorithm for deciding whether a competitive (CP) assignment exists. In particular, an assignment satisfies CP if each agent neither envies another agent nor wants to be assigned to an empty post, and CP implies several fairness and efficiency notions to justify it as a desirable solution concept. This addresses an open question raised in prior work, which only shows that a CP assignment may not exist.\n\nThis paper also studies the hardness of deciding the existence of assignments satisfying properties implied by CP, such as envy-freeness (EF), top-guarantees (TG), and maximal competitiveness (MaxCP). It shows that deciding the existence of an EF and TG assignment is NP-complete, and finding a MaxCP assignment is W[1]-hard. The paper also complements these negative results by providing several fixed parameter tractable algorithms.", "questions": "1. Does Theorem 6 directly imply Theorem 4? If yes, then Theorem 4 seems redundant here.\n\n2. What are the challenges of generalizing Algorithm 1 to the weighted case where the congestion of a post is the total weights of the agents assigned to it?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper studies an interesting and well-motivating problem, witnessed by a large volume of literature on the congestion assignment problem and its variants. Also, the solution concept focused by this paper, competitiveness (CP), is arguably prominent as it directly implies several fairness and efficiency properties, and hence it is important to enhance our understanding on it. The proofs in the paper are correct to the extent that I checked.\n\nIt appears as a surprise to me that the existence of a CP assignment can be verified efficiently since the same task tends to be computationally intractable for many other solution concepts, as also supported by the negative results in this paper. The algorithm is also non-trivial: it exploits the observation that one can reduce the task to verifying the existence of a CP assignment where all posts are non-empty, and then it gradually adjusts the congestion vector in search of the desired assignment. I believe this result will be of great interest to the community.\n\nWhile I can see that the authors have done a considerable amount of work on improving the writing, and I really appreciate their effort, there is still room for improvement (see the following comments). Overall, this is an interesting and solid paper, and I would support its acceptance, provided the presentation will be improved.\n\nDetailed comments:\n- Line 44: \"$n$ and $m$\" -> \"$n \\times m$\".\n- Line 46: Given that the sorting algorithm is quite easy to state, it would be better to briefly describe it, say, in the footnote.\n- Line 47: Briefly define in the footnote what Borda utilities are.\n- Line 75 Q2: The existence of TG and EF assignments is not guaranteed, so phrasing the question as \"finding a TG and EF assignment\" is confusing.\n- Line 75 Q3: Maximal CP has not been defined up to this point.\n- Line 83: In my first read, I misunderstood being filled as being full instead of being non-empty. It would be better to either explain the definition of being filled here or change \"filled\" to \"non-empty\".\n- Line 120-123: The claim on the hardness for finding a CP assignment with lower and upper quotas deserves further elabotation, say, in the appendix, since the connection does not seem very straightforward.\n- Line 172: \"satisfied\" -> \"unsatisfied\".\n- Line 213: Typo \"Section Subsection\".\n- Line 247: The statement here seems to conflict with (iii) in Construction 2.\n- Line 280: When defining $f$ to be an integral function, it would be better to explain that this is without loss of generality since the capacities of the graph are all integral.\n- Line 282: \"$(x, t)$\" -> \"$(x, t) \\in E(G)$\".\n- Line 331: As mentioned above, stating \"it is NP-hard to find such assignments\" is inappropriate since the existence of such assignments is not guaranteed.", "was_revised": true, "final_justification": "My concerns are fully addressed. I think this paper has made considerable contributions and deserves to be published.", "rebuttal": "Thanks for your helpful and detailed comments. Below we address the two questions raised by you and would like to discuss one comment that we're not sure:\n\n1. Does Theorem 6 directly imply Theorem 4? If yes, then Theorem 4 seems redundant here.\n\nAnswer: Thanks for the heads up. Yes, the proof of Theorem 6 can also be used to show Theorem 4 since the constructed assignment in the forward direction is also TG. We opt to keep Theorem 4 since the construction in the proof is simpler and it might help to understand the proof of Theorem 6 better. \n\n2. What are the challenges of generalizing Algorithm 1 to the weighted case where the congestion of a post is the total weights of the agents assigned to it?\n\nAnswer: The main challenge is that we need to find another way to compute a prefect flow. In the weighted setting, an agent with weight more than one need to occupy more space (increase the congestion by more than one). However, our algorithm treat all agents equally, which may result in an agent being assigned to different posts, e.g., an agent with weight 3 is assigned to post a with weight 2 and post b with weight 1. Indeed, for preferences with ties and agents with weights, we conjecture that the CP assignment is NP-hard to determine. \n\n* “Line 247: The statement here seems to conflict with (iii) in Construction 2.” \n\nResponse: We cannot understand this comment since the statement in Line 247 is for Lemma 3 which shows why reducing to determining CP assignments with **no** empty posts is correct, while Construction 2 is about the construction of a flow network in the step where we are searching for a CP assignment with *no* empty posts already."}]

Author rebuttal:

Meta-review: After discussion the reviewers all found this paper satisfactory with no major outstanding issues, although perhaps some room to improve the presentation.  On this positive side, there is a consensus that the paper makes solid technical contributions in resolving an open question in the theory of fair division and is of a quality suitable for publication.  On the negative side, the topic addressed in relatively specific within the context of fair division and the paper doesn't break any substantial new ground.
Decision: Accept (poster)