Figshare · 2018 · 39 citations · 23 references
ComputingComputer ScienceEconomicsAlgorithmsGame TheoryMachine LearningAlgorithmic Game TheoryApproximation AlgorithmsComplexityLearnabilityLearning ValuationsLower BoundsPolynomial Time ComplexityPolynomial-time AlgorithmsSubmodular ValuationsUpper Bounds
A core element of microeconomics and game theory is that consumers have valuation functions over bundles of goods and that these valuations functions drive their purchases. A common assumption is that these functions are subadditive meaning that the value given to a bundle is at most the sum of values on the individual items. In this paper, we provide nearly tight guarantees on the efficient learnability of subadditive valuations. We also provide nearly tight bounds for the subclass of XOS (fractionally subadditive) valuations, also widely used in the literature. We additionally leverage the structure of valuations in a number of interesting subclasses and obtain algorithms with stronger learning guarantees.
23
Yuhai Wu, Vladimir Vapnik · Technometrics · 1999 · 27K citations
Leslie G. Valiant · 1984 · 4.2K citations
Algorithm for optimal winner determination in combinatorial auctions
Tüomas Sandholm · Artificial Intelligence · 2002 · 925 citations
Business, Mathematics, Algorithms +13
Walrasian Equilibrium with Gross Substitutes
Faruk Gül, Ennio Stacchetti · Journal of Economic Theory · 1999 · 648 citations