<commit_before>\label{GASP:chapter}

In Chapters~\ref{bdoodle:chapter} and \ref{matrix:chapter}, we considered settings where an event organizer is trying to choose a date/time option at minimal cost for a group of agents given their likelihood of availability.
In this chapter we consider a different setting where the event organizer is trying to assign agents to different activities given constraints and preferences of agents. 

% \section{Introduction and Related Work}   \label{GASP:sec:Intro}

Imagine an event in which several activities are to take place concurrently. A group of agents are willing to participate and announce their activity preferences to the event organizer who is to assign agents to activities. In many settings, the agent preferences include not only which activities the agent is willing to participate in, but also the number(s) of participants in each activity that are acceptable to the agent.
For example, agents may wish to have enough participants in certain activities (such as group bus tour) to split the cost associated with it, whereas they may wish to have just few participants in activities with limited resources (such as a demo booth with a limited number of devices). 
We assume that an agent can be assigned to at most one activity (which naturally occurs when activities are run concurrently).

Given the preferences of agents, the organizer wishes to find a ``good'' assignment subject to certain rationality and/or stability conditions. 
The first condition is {\em individual rationality}: everyone who is assigned to some activity is willing to participate. In addition to individual rationality, the organizer may want to ensure that agents who are not assigned to any activity 
do not prefer to deviate from their assignment by joining an activity ({\em Nash stability}). Other concepts include {\em envy-freeness} that asserts that no unassigned agent would prefer to take the place of an assigned agent, and {\em perfection} in which all agents must be assigned.

To model this setting, in WINE'12, Darmann et al.~\cite{GASP12WINE} proposed the Group Activity Selection Problem (\GASP) and defined three solution concepts (individual rationality, stability, and perfection). 
In addition, they also provided many computational complexity results, including NP-hardness results for \GASP, even under various restrictions on agent preferences.

These hardness results essentially argue that it is hard to find an assignment that maximizes the number of participants in activities. Suppose, however, that we are satisfied if we can assign a small number $k$ out of the $n$ participants to some (up to $k$) of the $p$ activities while satisfying our rationality criteria. There is a brute-force solution: try all possible $O(p^k)$ ordered choices of up to $k$ activities, all $O(k^k)$ choices for the number of participants in each activity, and all $O(n^k)$ ordered choices of $k$ participants; then check whether the desired criterion is satisfied by the induced assignment. This brute-force solution runs in $O((pnk)^k)$ time. While this running time is polynomial for any fixed $k$, it is not very desirable. A much better running time would be one of the form $O(f(k)\cdot (p+n))$ - such a runtime would be {\em linear}, regardless of the constant $k$, and the function $f$. More generally, on input size $N$, one would like an algorithm with runtime $f(k)\cdot N^c$, where $c$ is independent of $k$. Such an algorithm is known as fixed parameter tractable (FPT), and the problems that admit such algorithms are said to be in the class FPT. Developing FPT algorithms, especially linear time ones, greatly mitigates the NP-hardness of problems as it shows that these problems are actually quite tractable for many instances.

The field of parameterized complexity strives to classify NP-hard problems on a finer scale by analyzing time complexity in terms of both the input size and an additional parameter. The FPT problems are viewed as the most tractable problems in NP (of course, all polytime problems are naturally in FPT).
There is a hierarchy of complexity classes under parameterization (called the W-hierarchy), including FPT, W[1], W[2], etc. Hierarchy theorems show that FPT is contained in W[1] which is contained in W[2], and so on (see \cite{downey2012} for more details). It is believed that FPT $\neq$ W[1] and W[2] $\neq$ W[1], so that the NP-hard parameterized problems in W[2] are believed to be harder than those in W[1] that are themselves believed to be harder than the FPT problems. Furthermore, popular hardness assumptions such as the Exponential Time Hypothesis (ETH) of Impagliazzo and Paturi~\cite{impagl} can often be used to show that particular W[1]-hard problems cannot be solved in $N^{o(k)}$ time, giving concrete runtime lower bounds.

The goal of this work is to investigate how different solution concepts and different restrictions on agent preferences influence the difficulty of \GASP.
We focus on \GASPs with the size of the solution as our parameter, i.e. the number of assigned agents, or in the case of perfection, the number of used activities. <commit_msg>(auto save via cron)<commit_after>\label{GASP:chapter}

In Chapters~\ref{bdoodle:chapter} and \ref{matrix:chapter}, we considered settings where an event organizer is trying to choose a date/time option at minimal cost for a group of agents given their likelihood of availability.
In this chapter we consider a different setting where the event organizer is trying to assign agents to different activities given constraints and preferences of agents. 

% \section{Introduction and Related Work}   \label{GASP:sec:Intro}

Imagine an event in which several activities are to take place concurrently. A group of agents are willing to participate and announce their activity preferences to the event organizer who is to assign agents to activities. In many settings, the agent preferences include not only which activities the agent is willing to participate in, but also the number(s) of participants in each activity that are acceptable to the agent.
For example, agents may wish to have enough participants in certain activities (such as group bus tour) to split the cost associated with it, whereas they may wish to have just few participants in activities with limited resources (such as a demo booth with a limited number of devices). 
We assume that an agent can be assigned to at most one activity (which naturally occurs when activities are run concurrently).

Given the preferences of agents, the organizer wishes to find a ``good'' assignment subject to certain rationality and/or stability conditions. 
The first condition is {\em individual rationality}: everyone who is assigned to some activity is willing to participate. In addition to individual rationality, the organizer may want to ensure that agents who are not assigned to any activity 
do not prefer to deviate from their assignment by joining an activity ({\em Nash stability}). Other concepts include {\em envy-freeness} that asserts that no unassigned agent would prefer to take the place of an assigned agent, and {\em perfection} in which all agents must be assigned.

To model this setting, Darmann et al.~\cite{GASP12WINE} proposed the Group Activity Selection Problem (\GASP) and defined three solution concepts (individual rationality, stability, and perfection). 
In addition, they also provided many computational complexity results, including NP-hardness results for \GASP, even under various restrictions on preferences of agents. 

These hardness results essentially argue that it is hard to find an assignment that maximizes the number of participants in activities. Suppose, however, that we are satisfied if we can assign a small number $k$ out of the $n$ participants to some (up to $k$) of the $p$ activities while satisfying our rationality criteria. There is a brute-force solution: try all possible $O(p^k)$ ordered choices of up to $k$ activities, all $O(k^k)$ choices for the number of participants in each activity, and all $O(n^k)$ ordered choices of $k$ participants; then check whether the desired criterion is satisfied by the induced assignment. This brute-force solution runs in $O((pnk)^k)$ time. While this running time is polynomial for any fixed $k$, it is not very desirable. A much better running time would be one of the form $O(f(k)\cdot (p+n))$ - such a runtime would be {\em linear}, regardless of the constant $k$, and the function $f$. More generally, on input size $N$, one would like an algorithm with runtime $f(k)\cdot N^c$, where $c$ is independent of $k$. Such an algorithm is known as fixed parameter tractable (FPT), and the problems that admit such algorithms are said to be in the class FPT. Developing FPT algorithms, especially linear time ones, greatly mitigates the NP-hardness of problems as it shows that these problems are actually quite tractable for many instances.

The field of parameterized complexity strives to classify NP-hard problems on a finer scale by analyzing time complexity in terms of both the input size and an additional parameter. The FPT problems are viewed as the most tractable problems in NP (of course, all polytime problems are naturally in FPT).
There is a hierarchy of complexity classes under parameterization (called the W-hierarchy), including FPT, W[1], W[2], etc. Hierarchy theorems show that FPT is contained in W[1] which is contained in W[2], and so on (see \cite{downey2012} for more details). It is believed that FPT $\neq$ W[1] and W[2] $\neq$ W[1], so that the NP-hard parameterized problems in W[2] are believed to be harder than those in W[1] that are themselves believed to be harder than the FPT problems. Furthermore, popular hardness assumptions such as the Exponential Time Hypothesis (ETH) of Impagliazzo and Paturi~\cite{impagl} can often be used to show that particular W[1]-hard problems cannot be solved in $N^{o(k)}$ time, giving concrete runtime lower bounds.

The goal of this work is to investigate how different solution concepts and different restrictions on agent preferences influence the difficulty of \GASP.
We focus on \GASPs with the size of the solution as our parameter, i.e. the number of assigned agents, or in the case of perfection, the number of used activities. 
{'fraction_non_alphanumeric': 0.05210149138098005, 'fraction_numerical': 0.0032926593066046872, 'mean_word_length': 4.874288964732651, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '185016', 'n_tokens_mistral': 2442, 'n_tokens_neox': 2339, 'n_words': 1592}