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 valuations.
Example
Suppose there are three items and two agents who value the items as follows:
| x | y | z | |
|---|---|---|---|
| Alice: | 5 | 3 | 1 |
| George: | 6 | 2 | 4.5 |
Then the assignment-valuation v corresponding to the group {Alice,George} assigns the following values:
- v ( { x } ) = 6 {\displaystyle v(\{x\})=6} - since the maximum-weight matching assigns x to George.
- v ( { y } ) = 3 {\displaystyle v(\{y\})=3} - since the maximum-weight matching assigns y to Alice.
- v ( { z } ) = 4.5 {\displaystyle v(\{z\})=4.5} - since the maximum-weight matching assigns z to George.
- v ( { x , y } ) = 9 {\displaystyle v(\{x,y\})=9} - since the maximum-weight matching assigns x to George and y to Alice.
- v ( { x , z } ) = 9.5 {\displaystyle v(\{x,z\})=9.5} - since the maximum-weight matching assigns z to George and x to Alice.
- v ( { y , z } ) = 7.5 {\displaystyle v(\{y,z\})=7.5} - since the maximum-weight matching assigns z to George and y to Alice.
- v ( { x , y , z } ) = 9.5 {\displaystyle v(\{x,y,z\})=9.5} - 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. 9 (1): 45–48. doi:10.1002/nav.3800090106. https://ideas.repec.org/a/wly/navlog/v9y1962i1p45-48.html ↩
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. 55 (2): 270–296. doi:10.1016/j.geb.2005.02.006. ISSN 0899-8256. http://www.sciencedirect.com/science/article/pii/S089982560500028X ↩
Benabbou, Nawal; Chakraborty, Mithun; Elkind, Edith; Zick, Yair (2019-08-10). "Fairness Towards Groups of Agents in the Allocation of Indivisible Items". {{cite journal}}: Cite journal requires |journal= (help) https://hal.sorbonne-universite.fr/hal-02155024 ↩
Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020). Finding Fair and Efficient Allocations When Valuations Don't Add Up. Lecture Notes in Computer Science. Vol. 12283. pp. 32–46. arXiv:2003.07060. doi:10.1007/978-3-030-57980-7_3. ISBN 978-3-030-57979-1. S2CID 208328700. 978-3-030-57979-1 ↩