Are Gross Substitutes a Substitute for Submodular Valuations?

An analysis of approximations for maximizing submodular set functions—i

George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher · 1978

Earlier work this paper cites.

Job matching, coalition formation, and gross substitutes

Alexander S Kelso Jr and Vincent P Crawford · 1982

Earlier work this paper cites.

Rewarding maps: On greedy optimization of set functions

A. Dress and W. Terhalle · 1995

Earlier work this paper cites.

Convexity and steinitz’s exchange property

Kazuo Murota · 1996

Earlier work this paper cites.

Walrasian equilibrium with gross substitutes

Faruk Gul and Ennio Stacchetti · 1999

Earlier work this paper cites.

A combinatorial strongly polynomial algorithm for minimizing submodular functions

Satoru Iwata, Lisa Fleischer, and Satoru Fujishige · 2001

Earlier work this paper cites.

Ascending auctions with package bidding

Lawrence M Ausubel and Paul R Milgrom · 2002

Earlier work this paper cites.

Verifying gross substitutability

Hans Reijnierse, Jos Potters, and Anita Gellekom · 2002

Earlier work this paper cites.

Combinatorial auctions with decreasing marginal utilities

Benny Lehmann, Daniel Lehmann, and Noam Nisan · 2006

Earlier work this paper cites.

The communication requirements of efficient allocations and supporting prices

Noam Nisan and Ilya Segal · 2006

Earlier work this paper cites.

Two randomized mechanisms for combinatorial auctions

Shahar Dobzinski · 2007

Cited alongside, same era.

Operations on m-convex functions on jump systems

Yusuke Kobayashi, Kazuo Murota, and Ken’ichiro Tanaka · 2007

Cited alongside, same era.

Optimal approximation for the submodular welfare problem in the value oracle model

Original

Jan Vondrák · 2008

Cited alongside, same era.

On maximizing welfare when utility functions are subadditive

Uriel Feige · 2009

Cited alongside, same era.

Approximating submodular functions everywhere

Michel X Goemans, Nicholas JA Harvey, Satoru Iwata, and Vahab Mirrokni · 2009

Cited alongside, same era.

Approximation algorithms for combinatorial auctions with complement-free bidders

Shahar Dobzinski, Noam Nisan, and Michael Schapira · 2010

Matroid rank functions and discrete concavity

Akiyoshi Shioura · 2012

Later among the works it cites.

Simultaneous auctions are (almost) efficient

Michal Feldman, Hu Fu, Nick Gravin, and Brendan Lucier · 2013

Later among the works it cites.

Representation, approximation and learning of submodular functions using low-rank decision trees

Vitaly Feldman, Pravesh Kothari, and Jan Vondrák · 2013

Later among the works it cites.

Gross substitutes and endowed assignment valuations

Michael Ostrovsky and Renato Paes Leme · 2015

Later among the works it cites.

Gross substitutability: An algorithmic survey

Renato Paes Leme · 2017

Later among the works it cites.

On the construction of substitutes

Eric Balkanski and Renato Paes Leme · 2018

Later among the works it cites.