A characterization of the existence of succinct linear representation of subset-valuations

Representation of valuations over multiple objects is foundational in modeling, from models of human behavior and choice to models of economic and market mechanisms. These valuations are often interrelated, and if modeling involves choice or decisions over sets of objects, an additional information for representing valuations over sets of objects may be necessary. This work provides a characterization for the existence of succinct linear representation of valuations over sets of objects, thereby indicating what structural properties are needed to ensure practical tractability of such representation, and suggesting what information would need to be elicited.

The issue of selecting or choosing a subset of available multiple objects arises naturally in many practical settings. For example, understanding a customer’s valuations over sets of objects is critical for an e-retailer’s personalized assortment and pricing decision tailored for that customer (e.g., see Chernev, 2005, Kök et al., 2015). Similarly, a seller of customizable product, from a software service to a car, needs to understand customer valuations over sets of additional options or features in order to decide on optimal bundling (e.g., see Bakos and Brynjolfsson, 1999, Hanson and Martin, 1990, Venkatesh and Kamakura, 2003). For another example, consider digital advertising markets that in real time insert targeted ads into a content shown to users. The advertiser valuation for a user depends on the user’s attributes (e.g., location, demographics, etc.) which are represented by the user’s digital imprint. This valuation is not simply an additive function, e.g., the value for a female older than 65 in New York City need not be equal to the sum of values the advertiser has for reaching a female, a New York City resident, and a person older than 65. In fact, digital advertising markets are designed to allow advertisers to express their valuations over sets of user attributes and to match each user with an advertiser in real-time by embedding the ad into the content as it is being loaded by the user (e.g., see, Abraham et al., 2020, Bergemann and Bonatti, 2015, Candogan and Pekeč, 2018, Cohen et al., 2020). Therefore, understanding preferences over subsets is a prerequisite for making meaningful decisions in creating, choosing, allocating or pricing multiple objects.

The fundamental problem of eliciting or estimating preferences over the set of all subsets is that the number of subsets could be prohibitively large irrespective of computational and communicational power of the decision-maker. For example, more than a quadrillion possible subsets can be created from 50 objects (250>1.1 quadrillion). Thus, it is not surprising that even the problem of choosing a subset of a finite set is known to be computationally unmanageable, (van Rooij, Stege, & Kadlec, 2005). This intractability in developing or utilizing fully general models for subset valuations to guide subset choice, allocation and/or pricing decisions, underscores the need for identifying settings in which a succinct, tractable representation of subset valuations is possible.

In the aforementioned assortment problem, prevailing practice has been to employ data-driven approaches and statistical estimation techniques (see, e.g., Bernstein et al., 2019, Gallego and Topaloglu, 2019), typically assuming that the assortment value is simply a linear function of the values of its individual objects. This ignores substitutabilities and complementarities among objects in the assortment and hence could yield suboptimal decisions. Some recent work (Benson, Kumar, & Tomkins, 2018), however, has extended a classical multinomial logit (MNL) model from individual item selection to subset selection, by expanding this linear valuation with additional terms corresponding to capturing synergetic impacts for a small number of subsets. Practical implementability and usefulness of this approach hinges on the ability to identify subsets and/or features driving these adjustments.

The challenge of modeling subset valuations is critical for combinatorial auctions (Cramton, Shoham, & Steinberg, 2006): market mechanisms in which sets of objects are traded. In combinatorial auctions bidders submit bids on bundles, i.e., subsets of the set of objects (instead of having to submit separate bids on single objects). Thus, every bidder needs to understand its own preferences over all possible bundles. On the other hand, the bid-taker has to choose a combinatorial auction procedure that elicits enough information about bidders’ bundle valuations, so that an optimal allocation and pricing decision can be made. Thus, an efficient elicitation of bundle valuations is a central issue of combinatorial auction design (e.g., Pekeč & Rothkopf, 2003) that has stimulated a considerable research interest (e.g., Candogan and Pekeč, 2018, Conen and Sandholm, 2001, Nisan and Segal, 2006, Parkes, 2005, Sandhom and Boutilier, 2006). For example, one of the approaches in the design and use of combinatorial auctions is to approximate bundle valuations by a simple function. The most natural candidate is the linear approximation (a.k.a. additive subset utility) that estimates the value of any bundle by the sum of the values of the individual objects in that bundle. The number of parameters in this case equals the number of objects, which is considerably smaller than the number of all bundles. The problem with such a simple approximation is that it neglects synergetic effects of bundle valuations. After all, the reason for considering creation, choice, allocation and/or pricing of bundles is to exploit potential synergies from the bundling process. However, it could be true that potential sources of synergies are limited and easily identified (several examples can be found in Rothkopf, Pekeč, & Harstad, 1998), in which case bundle valuations might be represented in a succinct and simple way, yielding a readily implementable combinatorial auction that does not suffer from computational intractability.

This note provides a necessary and sufficient condition for subset valuations (and subset utility) to be representable as a sum (or a product) of different synergetic effects. (For example, an advertiser who values reaching out to females or New York City residents or those older than 65, might put an additional value for reaching a user who has all three of these features.) More precisely, given a collection of properties that each subset could have or not have, we characterize the existence of weights, one for each such property, such that the utility of any subset is the sum of the weights corresponding to the properties that subset possesses. One special case, where only sources of synergy are binary interactions (i.e., synergetic effects are limited to pairs of objects that a subset contains) has been the topic of Fishburn and LaValle (1996). The results presented here generalize those in Fishburn and LaValle (1996). However, our main point is not that results from Fishburn and LaValle (1996) can be generalized, but it is that our generalization indicates that correctly identifying sources of synergy could yield to simple subset valuation and subset utility functions.

留言 (0)

沒有登入
gif