Assignment valuation

In economics, assignment valuation is a kind of a utility function on sets of items. It was introduced by Shapley{{Cite journal|last=Shapley|first=Lloyd S.|date=1962|title=Complements and substitutes in the opttmal assignment problem|url=https://ideas.repec.org/a/wly/navlog/v9y1962i1p45-48.html|journal=Naval Research Logistics Quarterly|language=en|volume=9|issue=1|pages=45–48|doi=10.1002/nav.3800090106|url-access=subscription}} and further studied by Lehmann, Lehmann and Nisan,{{Cite journal|last1=Lehmann|first1=Benny|last2=Lehmann|first2=Daniel|last3=Nisan|first3=Noam|date=2006-05-01|title=Combinatorial auctions with decreasing marginal utilities|url=http://www.sciencedirect.com/science/article/pii/S089982560500028X|journal=Games and Economic Behavior|series=Mini Special Issue: Electronic Market Design|language=en|volume=55|issue=2|pages=270–296|doi=10.1016/j.geb.2005.02.006|issn=0899-8256|url-access=subscription}} who use the term OXS valuation (not to be confused with XOS valuation). Fair item allocation in this setting was studied by Benabbou, Chakraborty, Elkind, Zick and Igarashi.{{Cite journal|last1=Benabbou|first1=Nawal|last2=Chakraborty|first2=Mithun|last3=Elkind|first3=Edith|last4=Zick|first4=Yair|date=2019-08-10|title=Fairness Towards Groups of Agents in the Allocation of Indivisible Items|url=https://hal.sorbonne-universite.fr/hal-02155024|language=en}}{{cite book|last1=Benabbou|first1=Nawal|last2=Chakraborty|first2=Mithun|last3=Igarashi|first3=Ayumi|last4=Zick|first4=Yair|title=Finding Fair and Efficient Allocations When Valuations Don't Add Up|series=Lecture Notes in Computer Science|year=2020|volume=12283|pages=32–46|doi=10.1007/978-3-030-57980-7_3|arxiv=2003.07060|isbn=978-3-030-57979-1|s2cid=208328700}}

Assignment valuations correspond to preferences of groups. In each group, there are several individuals; each individual attributes a certain numeric value to each item. The assignment-valuation of the group to a set of items S is the value of the maximum weight matching of the items in S to the individuals in the group.

The assignment valuations are a subset of the submodular valuations.

Example

Suppose there are three items and two agents who value the items as follows:

class="wikitable"

Alice:

George:

|4.5

Then the assignment-valuation v corresponding to the group {Alice,George} assigns the following values:

$v(\{x\}) = 6$ - since the maximum-weight matching assigns x to George.
$v(\{y\}) = 3$ - since the maximum-weight matching assigns y to Alice.
$v(\{z\}) = 4.5$ - since the maximum-weight matching assigns z to George.
$v(\{x,y\}) = 9$ - since the maximum-weight matching assigns x to George and y to Alice.
$v(\{x,z\}) = 9.5$ - since the maximum-weight matching assigns z to George and x to Alice.
$v(\{y,z\}) = 7.5$ - since the maximum-weight matching assigns z to George and y to Alice.
$v(\{x, y,z\}) = 9.5$ - since the maximum-weight matching assigns z to George and x to Alice.

References

Category:Utility function types