A kind of economic objective function in assignment

Question

I recently thought about a concept that seems like it should come up in economics, but I don't know if there's a name for it and where people would have encountered it elsewhere: Suppose we have a population of $N$ people, and each of these people has to be assigned to one of $m$ "actions" $A_1,\dots,A_m$. The cost of a person $i$ choosing action $j$ is written as $c_i(A_j)$. Typical objectives in this problem would be to determine an assignment of actions to people (i.e. $a_{i}$ denotes the action assigned to person $i$) that minimizes either the total cost, $$\min_{a_1,\dots,a_N}\sum_{i=1}^N c_i(a_i)~~,$$or the maximum cost over all agents, $$\min_{a_1,\dots,a_N}\max_i c_i(a_i)~~,$$subject to whatever other constraints may be present (e.g. prices of each action and budget constraints on the people, etc.)

My question is: what if we take each action, look at the set of people assigned to it, and sum over these? That is, we consider the quantities $\sum_{i:a_i = A_j} c_i(a_i)$ for each $j$ and then apply some function to these. For example, following this model, you might consider the problem $$\min_{a_1,\dots,a_N} \max_j \sum_{i:a_i = j} c_i(a_i)~~$$ Is there a name for such a problem?

Answer 1

This problem in the general sense, Generalized Assignment Problem. http://en.wikipedia.org/wiki/Generalized_assignment_problem. Some approximation algorithms also be applied for solving this problem. This comes into the area of optimization problems.

If you constraint yourself to one to one matching between the task and the person. ie. A single person can not do more than work and one work has to be allotted to a single person. This problem is related to graph theory. This is popularity known as Assignment problem. This is equivalent to finding min-cost maximum matching on bipartite graphs. There exists a polynomial time algorithm to solve this problem by using maximum flow.

If you allow the problem to have a person doing multiple works at a time without any constraint, it converts into a simple greedy algorithm. But in the case where you want to impose some other conditions on it, this problem can be difficult.