Assignment valuation explained
In economics, assignment valuation is a kind of a utility function on sets of items. It was introduced by Shapley[1] and further studied by Lehmann, Lehmann and Nisan,[2] 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.[3] [4]
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:
!!x!y!zAlice: | 5 | 3 | 1 |
George: | 6 | 2 | 4.5 | |
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
- Shapley. Lloyd S.. 1962. Complements and substitutes in the opttmal assignment problem. Naval Research Logistics Quarterly. en. 9. 1. 45–48. 10.1002/nav.3800090106.
- Lehmann. Benny. Lehmann. Daniel. Nisan. Noam. 2006-05-01. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior. Mini Special Issue: Electronic Market Design. en. 55. 2. 270–296. 10.1016/j.geb.2005.02.006. 0899-8256.
- Benabbou. Nawal. Chakraborty. Mithun. Elkind. Edith. Zick. Yair. 2019-08-10. Fairness Towards Groups of Agents in the Allocation of Indivisible Items. en.
- Book: Benabbou. Nawal. Chakraborty. Mithun. Igarashi. Ayumi. Zick. Yair. Finding Fair and Efficient Allocations When Valuations Don't Add Up. Lecture Notes in Computer Science. 2020. 12283. 32–46. 10.1007/978-3-030-57980-7_3. 2003.07060. 978-3-030-57979-1. 208328700.