Abstract We study the problem of fairly partitioning a set of agents into coalitions based on the agents’ additively separable preferences, which can also be viewed as a hedonic game. We study three successively weaker solution concepts, related to envy, weakly justified envy, and justified envy. In a model in which coalitions may have any size, trivial solutions exist for these concepts, which provides a strong motivation for placing restrictions on coalition size. In this paper, we require feasible coalitions to have size three. We study the existence of partitions that are envy-free, weakly justified envy-free, and justified envy-free, and the computational complexity of finding such partitions, if they exist. We impose various restrictions on the agents’ preferences and present a complete complexity classification in terms of these restrictions.

We study the problem of finding a maximum-cardinality set of r-cliques in an undirected graph of fixed maximum degree Δ, subject to the cliques in that set being either vertex disjoint or edge disjoint. It is known for r=3 that the vertex-disjoint (edge-disjoint) problem is solvable in linear time if Δ=3 (Δ=4) but APX-hard if Δ≥4 (Δ≥5). We generalise these results to an arbitrary but fixed r≥3, and provide a complete complexity classification for both the vertex- and edge-disjoint variants in graphs of maximum degree Δ. Specifically, we show that the vertex-disjoint problem is solvable in linear time if Δ<3r/2−1, solvable in polynomial time if Δ<5r/3−1, and APX-hard if Δ≥⌈5r/3⌉−1. We also show that if r≥6 then the above implications also hold for the edge-disjoint problem. If r≤5, then the edge-disjoint problem is solvable in linear time if Δ<3r/2−1, solvable in polynomial time if Δ≤2r−2, and APX-hard if Δ>2r−2.

Previous perceptual studies on human faces have shown that specific facial features have consistent effects on perceived personality and appeal, but it remains unclear if and how findings relate to perception of virtual characters. For example, wider human faces have been found to appear more aggressive and dominant, whereas studies on virtual characters have shown opposite trends but have suffered from significant eeriness of exaggerated features. In this study, we use highly realistic virtual faces obtained from 3D scanning, as well as cartoon-rendered counterparts retaining facial proportions. We assess the effects of facial width and eye size on perceptions of appeal, trustworthiness, aggressiveness, dominance, and eeriness. Our manipulations did not affect eeriness, and we find the same perceptual trends previously reported for human faces.