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.

  • $\begingroup$ Thank you for the advice. Is it possible to delete this question from here? $\endgroup$ – Ivan Jan 20 '15 at 3:46
  • $\begingroup$ Please don't. I like interesting questions - even if I don't know the answer! $\endgroup$ – Mike Jan 20 '15 at 7:19

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.

| cite | improve this answer | |
  • $\begingroup$ I took a quick look, and I don't see an immediate connection, but will try to go into more details later. Thanks. $\endgroup$ – Ivan Jan 24 '15 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.