<p>Seems to me that the submodular welfare problem falls under your description. Have a look at <a href="http://theory.stanford.edu/~jvondrak/data/KAM_thesis.pdf" rel="nofollow">http://theory.stanford.edu/~jvondrak/data/KAM_thesis.pdf</a> 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.</p>

CC BY-SA 3.0
2015-01-24T06:27:33.540Z
I took a quick look, and I don't see an immediate connection, but will try to go into more details later. Thanks.
Ivan
CC BY-SA 3.0
2015-01-20T16:54:15.490Z
2015-01-20T16:54:15.490Z
Marek Adamczyk
<p>The standard <a href="http://en.wikipedia.org/wiki/Assignment_problem" rel="nofollow">Assignment Problem</a> asks for an optimal one-to-one assignment between agents and tasks.</p>

<p>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 <code>c</code> and a set <code>S</code> of task-agent pairs. Meaning of a such constraint is that a cost <code>c</code> occurs when all pairs in <code>S</code> are "<em>satisfied</em>", and the overall cost is the sum of costs of all satisfied constraints.</p>

<p>Note that this problem can be encoded as <a href="http://en.wikipedia.org/wiki/Maximum_satisfiability_problem#Related_problems" rel="nofollow">Weighted Partial MAX-SAT</a>, where hard clauses encode one-to-one assignment between agents and tasks, and each constraint is a (weighted) soft clause.</p>

<p>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.</p>

<p>Thanks for your help.</p>

<ds.algorithms><optimization><sat>
Is there a name for this Assignment definition
Ivan
# Is there a name for this Assignment definition

(Asked by: username_0 on 2015-01-19)

The standard [Assignment Problem](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Maximum_satisfiability_problem#Related_problems), 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.

**Tags:** ds.algorithms, optimization, sat


---

## 1 answers

### Answer by username_1 on 2015-01-20. Score: 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.

> **Comments:**
> **username_0**: I took a quick look, and I don't see an immediate connection, but will try to go into more details later. Thanks.  

---

