We study the social welfare maximization problem in the high-multiplicity setting where agents and/or items are available in multiple types, provided that the numbers of types are small. We focus on the egalitarian and Nash social welfare maximization problems, and show that they are NP-hard even when the number of item types is a constant. Furthermore, we present two polynomial-time approximation schemes (PTAS), one for egalitarian social welfare with two item types, and one for Nash social welfare with any constant number of agent types. The first PTAS can be applied to the unrelated machine scheduling problem, thus partially solving an open question raised by Jansen and Maack in 2019. The second PTAS significantly improves upon the existing PTAS for identical agents.

We consider a rate-splitting multiple access (RSMA)-based communication and radar coexistence (CRC) system. The proposed system allows an RSMA-based communication system to share spectrum with multiple radars. Furthermore, RSMA enables flexible and powerful interference management by splitting messages into common parts and private parts to partially decode interference and partially treat interference as noise. The RSMA-based CRC system thus significantly improves spectral efficiency and quality of service (QoS) of communication users (CUs). The communication network and the radars cause interference to each other, which reduces the signal-to-interference-plus-noise ratio (SINR) of the radars as well as the data rate of the CUs. Therefore, a major problem is to maximize the sum rate of the CUs while guaranteeing their QoS requirements of data transmissions and the SINR requirements of multiple radars. To achieve these objectives, we formulate a problem that optimizes i) the common rate allocation to the CUs, transmit power of common message and transmit power of private messages of the CUs, and ii) transmit power of the radars. We propose an additive approximation scheme (AAS) which solves the problem globally. Simulation results show the improvement of the AAS compared with the sequential quadratic programming (SQP) in terms of sum rate.

Fair allocation of indivisible goods is a central topic in many AI applications. Unfortunately, the corresponding problems are known to be NP-hard for many fairness concepts, so unless P = NP, exact polynomial-time algorithms cannot exist for them. In practical applications, however, it would be highly desirable to find exact solutions as quickly as possible. This motivates the study of algorithms that—even though they only run in exponential time—are as fast as possible and exactly solve such problems. We present known complexity results for them and give a survey of important techniques for designing such algorithms, mainly focusing on four common fairness notions: max-min fairness, maximin share, maximizing Nash social welfare, and envy-freeness. We also highlight the most challenging open problems for future work.

In fair division of indivisible goods, finding an allocation that satisfies fairness and efficiency simultaneously is highly desired but computationally hard. We solve this problem approximately in polynomial time by modeling it as a bi-criteria optimization problem that can be solved efficiently by determining an approximate Pareto set of bounded size. We focus on two criteria: max-min fairness and utilitarian efficiency, and study this problem for the setting when there are only a few item types or a few agent types. We show in both cases that one can construct an approximate Pareto set in time polynomial in the input size, either by designing a dynamic programming scheme, or a linear-programming algorithm. Our techniques strengthen known methods and can be potentially applied to other notions of fairness and efficiency as well.

We study a generalized version of the load balancing problem on unrelated machines with cost constraints: Given a set of m machines (of certain types) and a set of n jobs, each job j processed on machine i requires p_{i,j} time units and incurs a cost c_{i,j}, and the goal is to find a schedule of jobs to machines, which is defined as an ordered partition of n jobs into m disjoint subsets, in such a way that some objective function of the vector of the completion times of the machines is optimized, subject to the constraint that the total costs by the schedule must be within a given budget B. Motivated by recent results from the literature, our focus is on the case when the number of machine types is a fixed constant and we develop a bi-criteria approximation scheme for the studied problem. Our result generalizes several known results for certain special cases, such as the case with identical machines, or the case with a constant number of machines with cost constraints. Building on the elegant technique recently proposed by Jansen and Maack [K. Jansen and M. Maack, 2019], we construct a more general approach that can be used to derive approximation schemes to a wider class of load balancing problems with constraints.

We define a family of rules for dividing m indivisible goods among agents, parameterized by a scoring vector and a social welfare aggregation function. We assume that agents' preferences over sets of goods are additive, but that the input is ordinal: each agent simply ranks single goods. Similarly to (positional) scoring rules in voting, a scoring vector s = (s1,...,sm) consists of m nonincreasing nonnegative weights, where siis the score of a good assigned to an agent who ranks it in position i. The global score of an allocation for an agent is the sum of the scores of the goods assigned to her. The social welfare of an allocation is the aggregation of the scores of all agents, for some aggregation function ★ such as, typically, + or min. The rule associated with s and ★ maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, separability, envy-freeness, and Pareto efficiency.