File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/1.9781611973730.6
- Scopus: eid_2-s2.0-84938269814
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Welfare maximization with production costs: a primal dual approach
Title | Welfare maximization with production costs: a primal dual approach |
---|---|
Authors | |
Keywords | Data Structures and Algorithms Computer Science and Game Theory |
Issue Date | 2015 |
Publisher | Society 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? |
Abstract | We 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. |
Description | CP2: Session 1B |
Persistent Identifier | http://hdl.handle.net/10722/209631 |
ISBN |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Huang, Z | - |
dc.contributor.author | Kim, A | - |
dc.date.accessioned | 2015-05-12T06:36:10Z | - |
dc.date.available | 2015-05-12T06:36:10Z | - |
dc.date.issued | 2015 | - |
dc.identifier.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 | - |
dc.identifier.isbn | 978-1-61197-374-7 | - |
dc.identifier.uri | http://hdl.handle.net/10722/209631 | - |
dc.description | CP2: Session 1B | - |
dc.description.abstract | We 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.language | eng | - |
dc.publisher | Society for Industrial and Applied Mathematics. | - |
dc.relation.ispartof | Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | - |
dc.rights | © 2015 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms in 2015, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.subject | Data Structures and Algorithms | - |
dc.subject | Computer Science and Game Theory | - |
dc.title | Welfare maximization with production costs: a primal dual approach | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Huang, Z: zhiyi@cs.hku.hk | - |
dc.identifier.authority | Huang, Z=rp01804 | - |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.1137/1.9781611973730.6 | - |
dc.identifier.scopus | eid_2-s2.0-84938269814 | - |
dc.identifier.hkuros | 242998 | - |
dc.identifier.hkuros | 243362 | - |
dc.identifier.hkuros | 250459 | - |
dc.identifier.spage | 59 | - |
dc.identifier.epage | 72 | - |
dc.publisher.place | United States | - |