Assignment valuation

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	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:

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

References

1. 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.
2. 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.
3. 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)
4. 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.