Sandwich games

Authors: Ehud Lehrer Roee Teper

Publish Date: 2014/08/01

Volume: 152, Issue: 1-2, Pages: 545-557

PDF Link

Abstract

The extension of set functions or capacities in a concave fashion namely a concavification is an important issue in decision theory and combinatorics It turns out that some setfunctions cannot be properly extended if the domain is restricted to be bounded This paper examines the structure of those capacities that can be extended over a bounded domain in a concave manner We present a property termed the sandwich property that is necessary and sufficient for a capacity to be concavifiable over a bounded domain We show that when a capacity is interpreted as the product of any sub group of workers per a unit of time the sandwich property provides a linkage between optimality of time allocations and efficiencyFix a capacity v The homogeneity of e v is implied by the definition of int cav cdot dv Now fix xin Q and consider a decomposition of x sum Ssubseteq Nalpha S mathbf1 S=x Letting i= arg max iin 1ldots n x i we get that sum Ssubseteq Nalpha Sge sum Ssubseteq N iin S alpha S=x i=max x Since e vx is the minimum over all such decomposition we obtain e vxge max x square On the other hand if v has the sandwich property let f S be an affine function that dominates v S Define f in the same way as defined above By assumption there is a linear function ell that is dominating v and is dominated by f The restriction of ell to S ell S is dominating v S and is dominated by f S implying that v S has the sandwich property square Suppose that the core of v is nonempty and let sum alpha Smathbf1 S be a decomposition of mathbf1 N then by the ShapleyBondareva theorem Bondareva 4 and Shapley 14 sum alpha SvSle vN Thus the decomposition mathbf1 N of itself is optimal implying that e vmathbf1 Nle 1 and by Lemma 1 e vmathbf1 N= 1Now suppose that e vmathbf1 N= 1 It implies that any sharp decomposition of mathbf1 N sum alpha Smathbf1 S satisfies S=N whenever alpha S0 Thus the decomposition is in fact mathbf1 N itself square Let xin Q and sum alpha Smathbf1 S be its sharp decomposition Wlog alpha 12le alpha 13alpha 23 Thus we can replace alpha 12mathbf1 12+alpha 13mathbf1 13+alpha 23mathbf1 23 by 2alpha 12mathbf1 123+alpha 13alpha 12mathbf1 13+alpha 23alpha 12mathbf1 23We conclude that one may assume that in a sharp decomposition the coefficient of mathbf1 12 is 0 Furthermore based on the total balancedness of v a similar argument would imply that no two coalitions with positive coefficients in the decomposition are disjoint Thus at most one singleton has a positive coefficient and the one that has a positive coefficient if exists is included in the other coalitions whose coefficients are positiveCase 1 alpha 10 Then alpha 2=alpha 3=alpha 23=0 which means that 1in S when alpha S0 Case 2 alpha 20 Then alpha 1=alpha 3=alpha 13=0 implying that 2in S if alpha S0 Case 3 alpha 30 Similar to the previous case Finally Case 4 alpha i=0 for every iin N Since alpha 12=0 3in S whenever alpha S0 This completes the proof square Assume that any subcapacity of v has a large core This implies that v is totally balanced Thus every subcapacity of v is totally balanced and has a large core As such any subcapacity is exact Sharkey 16 implying that v is convex Biswas et al 3 By Claim 3 v has the sandwich propertysquare

Keywords: