It is a notorious open question whether integer programs (IPs) with an integer coefficient matrix M whose subdeterminants are all bounded by a constant Δ in absolute value can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from M, one obtains a submatrix A that is the transpose of a network matrix.

Dynamic matching markets are an ubiquitous object of study with applications in health, labor, or dating. We study a model proposed by Akbarpour et al. [2020] and Anderson et al. [2017], where homogeneous agents arrive at random according to a Poisson process and possess a random compatibility with other agents as in the Erdős-Rényi model. Agents leave according to a certain departure distribution and may leave early by forming a pair with a compatible agent. If agents are not matched until the end of their sojourn time, they perish and have to leave the market unmatched.

A common theme of decision making in multi-agent systems is to assign utilities to alternatives, which individuals seek to maximize. This rationale is questionable in coalition formation where agents are affected by other members of their coalition. Based on the assumption that agents are benevolent towards other agents they like to form coalitions with, we propose loyalty in hedonic games, a binary relation dependent on agents' utilities. Given a hedonic game, we define a loyal variant where agents' utilities are defined by taking the minimum of their utility and the utilities of agents towards which they are loyal. This process can be iterated to obtain various degrees of loyalty, terminating in a locally egalitarian variant of the original game. We investigate axioms of group stability and efficiency for different degrees of loyalty. Specifically, we consider the problem of finding coalition structures in the core and of computing best coalitions, obtaining both positive and intractability results. In particular, the limit game possesses Pareto optimal coalition structures in the core.