In
economics, assignment valuation is a kind of a
utility function on sets of items. It was introduced by
Shapley and further studied by Lehmann, Lehmann and Nisan, 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.
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 valuation
In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an ...
s.
Example
Suppose there are three items and two agents who value the items as follows:
Then the assignment-valuation ''v'' corresponding to the group assigns the following values:
*
- since the maximum-weight matching assigns x to George.
*
- since the maximum-weight matching assigns y to Alice.
*
- since the maximum-weight matching assigns z to George.
*
- since the maximum-weight matching assigns x to George and y to Alice.
*
- since the maximum-weight matching assigns z to George and x to Alice.
*
- since the maximum-weight matching assigns z to George and y to Alice.
*
- since the maximum-weight matching assigns z to George and x to Alice.
References
Utility function types