File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Welfare maximization with production costs: a primal dual approach

TitleWelfare maximization with production costs: a primal dual approach
Authors
KeywordsData Structures and Algorithms
Computer Science and Game Theory
Issue Date2015
PublisherSociety for Industrial and Applied Mathematics.
Citation
The 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA., 4-6 January 2015. In Conference Proceedings, 2015, p. 59-72 How to Cite?
AbstractWe study online combinatorial auctions with production costs proposed by Blum et al. using the online primal dual framework. In this model, buyers arrive online, and the seller can produce multiple copies of each item subject to a non-decreasing marginal cost per copy. The goal is to allocate items to maximize social welfare less total production cost. For arbitrary (strictly convex and differentiable) production cost functions, we characterize the optimal competitive ratio achievable by online mechanisms/algorithms. We show that online posted pricing mechanisms, which are incentive compatible, can achieve competitive ratios arbitrarily close to the optimal, and construct lower bound instances on which no online algorithms, not necessarily incentive compatible, can do better. Our positive results improve or match the results in several previous work, e.g., Bartal et al., Blum et al., and Buchbinder and Gonen. Our lower bounds apply to randomized algorithms and resolve an open problem by Buchbinder and Gonen.
DescriptionCP2: Session 1B
Persistent Identifierhttp://hdl.handle.net/10722/209631
ISBN

 

DC FieldValueLanguage
dc.contributor.authorHuang, Z-
dc.contributor.authorKim, A-
dc.date.accessioned2015-05-12T06:36:10Z-
dc.date.available2015-05-12T06:36:10Z-
dc.date.issued2015-
dc.identifier.citationThe 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA., 4-6 January 2015. In Conference Proceedings, 2015, p. 59-72-
dc.identifier.isbn978-1-61197-374-7-
dc.identifier.urihttp://hdl.handle.net/10722/209631-
dc.descriptionCP2: Session 1B-
dc.description.abstractWe study online combinatorial auctions with production costs proposed by Blum et al. using the online primal dual framework. In this model, buyers arrive online, and the seller can produce multiple copies of each item subject to a non-decreasing marginal cost per copy. The goal is to allocate items to maximize social welfare less total production cost. For arbitrary (strictly convex and differentiable) production cost functions, we characterize the optimal competitive ratio achievable by online mechanisms/algorithms. We show that online posted pricing mechanisms, which are incentive compatible, can achieve competitive ratios arbitrarily close to the optimal, and construct lower bound instances on which no online algorithms, not necessarily incentive compatible, can do better. Our positive results improve or match the results in several previous work, e.g., Bartal et al., Blum et al., and Buchbinder and Gonen. Our lower bounds apply to randomized algorithms and resolve an open problem by Buchbinder and Gonen.-
dc.languageeng-
dc.publisherSociety for Industrial and Applied Mathematics.-
dc.relation.ispartofProceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms-
dc.rightsProceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Copyright © Society for Industrial and Applied Mathematics.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectData Structures and Algorithms-
dc.subjectComputer Science and Game Theory-
dc.titleWelfare maximization with production costs: a primal dual approach-
dc.typeConference_Paper-
dc.identifier.emailHuang, Z: zhiyi@cs.hku.hk-
dc.identifier.authorityHuang, Z=rp01804-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1137/1.9781611973730.6-
dc.identifier.hkuros242998-
dc.identifier.hkuros243362-
dc.identifier.hkuros250459-
dc.identifier.spage59-
dc.identifier.epage72-
dc.publisher.placeUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats