Is there a name for this Assignment definition

Question

The standard Assignment Problem asks for an optimal one-to-one assignment between agents and tasks.

Now consider the following generalization: Instead of specifying a cost of a single agent-task pair, assume that you can specify a cost of an arbitrary set of agent-task pairs. The problem is then defined by a set of constraints, where each constraint is a cost c and a set S of task-agent pairs. Meaning of a such constraint is that a cost c occurs when all pairs in S are "satisfied", and the overall cost is the sum of costs of all satisfied constraints.

Note that this problem can be encoded as Weighted Partial MAX-SAT, where hard clauses encode one-to-one assignment between agents and tasks, and each constraint is a (weighted) soft clause.

However, I am interested if this can be reduced to something simpler or if this is a known problem, but so far wasn't able to find an answer.

Thanks for your help.

Answer 1

Seems to me that the submodular welfare problem falls under your description. Have a look at http://theory.stanford.edu/~jvondrak/data/KAM_thesis.pdf chapter 4; here we assume that the utility function of subsets is submodular. In general, your problem is just the combinatorial auction problem which is hard to approximate without any assumptions on the valuation function.