Combinatorial auctions with decreasing marginal utilities

DOI10.1016/j.geb.2005.02.006zbMath1125.91043OpenAlexW2962711478MaRDI QIDQ2506310

Noam Nisan, Benny Lehmann, Daniel J. Lehmann

Publication date: 28 September 2006

Published in: Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.geb.2005.02.006

zbMATH Keywords

winner determination combinatorial auctions decreasing marginal utilities

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Related Items

Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint, Computing Stable Coalitions: Approximation Algorithms for Reward Sharing, Ad Exchange: Envy-Free Auctions with Mediators, Welfare and Rationality Guarantees for the Simultaneous Multiple-Round Ascending Auction, Welfare and Revenue Guarantees for Competitive Bundling Equilibrium, On maximizing the difference between an approximately submodular function and a linear function subject to a matroid constraint, Policies for risk-aware sensor data collection by mobile agents, Iterative Auction Design for Tree Valuations, Maximizing a non-decreasing non-submodular function subject to various types of constraints, Submodular Functions: Learnability, Structure, and Optimization, Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order, Limits of Efficiency in Sequential Auctions, Quality of local equilibria in discrete exchange economies, (Almost) efficient mechanisms for bilateral trading, A mobile multi-agent sensing problem with submodular functions under a partition matroid, Repeated budgeted second price ad auction, Recognizing Coverage Functions, Matroid rank functions and discrete concavity, Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid, Auctions with interdependence and SOS: improved approximation, Near-Optimal Asymmetric Binary Matrix Partitions, Optimization with demand oracles, Gross substitutability: an algorithmic survey, An accelerated continuous greedy algorithm for maximizing strong submodular functions, Pricing multi-unit markets, Combinatorial assortment optimization, Identifying combinatorial valuations from aggregate demand, On the configuration LP for maximum budgeted allocation, Unnamed Item, Uniform price auctions: equilibria and efficiency, Near-optimal asymmetric binary matrix partitions, Optimal shill bidding in the VCG mechanism, Unnamed Item, Interactive optimization of submodular functions under matroid constraints, Theory of Principal Partitions Revisited, Recent Developments in Discrete Convex Analysis, Simultaneous auctions without complements are (almost) efficient, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, Second-price ad auctions with binary bids and markets with good competition, Limitations of VCG-based mechanisms, When Are Welfare Guarantees Robust, Valuated matroid-based algorithm for submodular welfare problem, Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs, Stability and competitive equilibria in multi-unit trading networks with discrete concave utility functions, Deterministic approximation algorithm for submodular maximization subject to a matroid constraint, Inapproximability results for combinatorial auctions with submodular utility functions, A unifying look at sequence submodularity, Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions, Maximizing a class of submodular utility functions with constraints, Time bounds for iterative auctions: a unified approach by discrete convex analysis, Buyback problem with discrete concave valuation functions, A note on solving DiDi's driver-order matching problem, Item bidding for combinatorial public projects, Optimization with uniform size queries, Online ascending auctions for gradually expiring items, Online pricing for multi-type of items, Simple combinatorial auctions with budget constraints, Maximizing a class of submodular utility functions, On complexity of single-minded auction, Permutation betting markets: singleton betting with extra information, Parametric monotone function maximization with matroid constraints, Informational limitations of ascending combinatorial auctions, Applications of discrete convex analysis to mathematical economics, Walrasian's characterization and a universal ascending auction, Coordinatewise domain scaling algorithm for M-convex function minimization, The communication requirements of efficient allocations and supporting prices, A non-extendibility certificate for submodularity and applications, Directed discrete midpoint convexity, Stability and auctions in labor markets with job security, Economic efficiency requires interaction, Side constraints and non-price attributes in markets, Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions, Geometry of gross substitutes valuations, On envy-free revenue approximation for combinatorial buyers with budgets, Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions, Approximately optimal auctions for correlated bidders, The Finite Matroid-Based Valuation Conjecture is False, Cost sharing over combinatorial domains : Complement-free cost functions and beyond, Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, Envy-Free Revenue Approximation for Asymmetric Buyers with Budgets, Non-submodular maximization on massive data streams, Worst-Case Mechanism Design via Bayesian Analysis, Item Pricing for Combinatorial Public Projects, Dynamics of Profit-Sharing Games, Algorithms as Mechanisms: The Price of Anarchy of Relax and Round, Approximation algorithms for vertex happiness, Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders, Fractionally subadditive maximization under an incremental knapsack constraint, Combinatorial auctions for electronic business, Clique partitioning with value-monotone submodular cost, An adaptive algorithm for maximization of non-submodular function with a matroid constraint, Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems, k-Submodular maximization with two kinds of constraints, Combinatorial auctions with endowment effect, Auctions with online supply, Unnamed Item, Incentive compatible mulit-unit combinatorial auctions: a primal dual approach, Tight Approximation for Unconstrained XOS Maximization, An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint, The Limitations of Optimization from Samples, Dynamic Relaxations for Online Bipartite Matching, Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations, Almost Envy-Freeness with General Valuations, Online ad allocation in bounded-degree graphs, Submodular Maximization Through the Lens of Linear Programming, Discrete Midpoint Convexity, On the Construction of Substitutes, Combinatorial reallocation mechanisms, On Fair Division under Heterogeneous Matroid Constraints, Simultaneous 2nd price item auctions with no-underbidding, Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions, Optimal Mechanism Design for Agents with DSL Strategies: The Case of Sybil Attacks in Combinatorial Auctions, Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows, Unnamed Item, Truthful randomized mechanisms for combinatorial auctions, The Complexity of Partial Function Extension for Coverage Functions, Unnamed Item, Mechanism design for perturbation stable combinatorial auctions, Approximate Modularity Revisited, Unnamed Item, Risk-free bidding in complement-free combinatorial auctions, Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints, Stability and Recovery for Independence Systems, Online Contention Resolution Schemes with Applications to Bayesian Selection Problems, Unnamed Item, Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online, Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings

Cites Work