Approximation algorithms for combinatorial auctions with complement-free bidders

DOI10.1287/MOOR.1090.0436zbMATH Open1216.68338OpenAlexW2104334470MaRDI QIDQ3169079FDOQ3169079

Authors: Shahar Dobzinski, Noam Nisan, Michael Schapira 

Publication date: 27 April 2011

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.1090.0436

Recommendations

• Approximation algorithms for combinatorial auctions with complement-free bidders
• Approximation Algorithms for k-Duplicates Combinatorial Auctions with Subadditive Bidders
• Inapproximability results for combinatorial auctions with submodular utility functions
• Bayesian combinatorial auctions
• Combinatorial auctions with decreasing marginal utilities

zbMATH Keywords

combinatorial auctionstruthfulness

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25)

Cited In (44)

• Title not available (Why is that?)
• Combinatorial auctions with interdependent valuations: SOS to the rescue
• Inapproximability results for combinatorial auctions with submodular utility functions
• Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem
• A generic truthful mechanism for combinatorial auctions
• Oblivious Medians Via Online Bidding
• On the computational power of demand queries
• When are welfare guarantees robust?
• On the complexity of computing an equilibrium in combinatorial auctions
• Bayesian combinatorial auctions
• Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions
• On the efficiency of the proportional allocation mechanism for divisible resources
• A simple and approximately optimal mechanism for a buyer with complements
• Online submodular welfare maximization: greedy beats 1/2 in random order
• Envy-free revenue approximation for asymmetric buyers with budgets
• An Experimental Study of the Misdirection Algorithm for Combinatorial Auctions
• Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs
• On envy-free revenue approximation for combinatorial buyers with budgets
• An Efficient Winner Approximation for a Series of Combinatorial Auctions
• On bidding algorithms for a distributed combinatorial auction
• On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources
• Approximating Nash social welfare under binary XOS and binary subadditive valuations
• Learning in auctions: regret is hard, envy is easy
• On simultaneous two-player combinatorial auctions
• Approximation algorithms for a winner determination problem of single-item multi-unit auctions
• Lower bounds for approximating graph parameters via communication complexity
• A new approximation guarantee for monotone submodular function maximization via discrete convexity
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows
• Prophet secretary for combinatorial auctions and matroids
• Welfare maximization with friends-of-friends network externalities
• Combinatorial auctions with decreasing marginal utilities
• Computing stable coalitions: approximation algorithms for reward sharing
• Approximating Nash social welfare by matching and local search
• Sketching valuation functions
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Combinatorial auctions with conflict-based externalities
• Approximation Algorithms for k-Duplicates Combinatorial Auctions with Subadditive Bidders
• Worst-case mechanism design via Bayesian analysis
• Communication complexity of discrete fair division
• Bayesian optimal knapsack procurement
• Setting lower bounds on truthfulness
• Two-stage submodular maximization under knapsack and matroid constraints
• Maximize liquid welfare in combinatorial auctions with monotone valuations
• A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation

This page was built for publication: Approximation algorithms for combinatorial auctions with complement-free bidders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3169079)