On revenue maximization with sharp multi-unit demands

Ning Chen; Xiaotie Deng; Paul W. Goldberg; Jinshan Zhang

doi:10.1007/s10878-014-9817-y

On revenue maximization with sharp multi-unit demands

Ning Chen
, Xiaotie Deng
, Paul W. Goldberg
, Jinshan Zhang

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

14 Citations (Scopus)

Abstract

We consider markets consisting of a set of indivisible items, and buyers that have sharp multi-unit demand. This means that each buyer (Formula presented.) wants a specific number (Formula presented.) of items; a bundle of size less than (Formula presented.) has no value. We consider the objective of setting prices and allocations in order to maximize the total revenue of the market maker. The pricing problem with sharp multi-unit demand buyers has a number of properties that the unit-demand model does not possess, and is an important question in algorithmic pricing. We consider the problem of computing a revenue maximizing solution for two solution concepts: competitive equilibrium and envy-free pricing. For unrestricted valuations, these problems are NP-complete; we focus on a realistic special case of “correlated values” where each buyer (Formula presented.) has a valuation (Formula presented.) for item (Formula presented.) , where (Formula presented.) and (Formula presented.) are positive quantities associated with buyer (Formula presented.) and item (Formula presented.) respectively. We present a polynomial time algorithm to solve the revenue-maximizing competitive equilibrium problem. For envy-free pricing, if the demand of each buyer is bounded by a constant, a revenue maximizing solution can be found efficiently; the general demand case is shown to be NP-hard. © 2014, Springer Science+Business Media New York.

Original language	English
Pages (from-to)	1174-1205
Journal	Journal of Combinatorial Optimization
Volume	31
Issue number	3
DOIs	https://doi.org/10.1007/s10878-014-9817-y
Publication status	Published - 1 Apr 2016
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

The authors thanks anonymous referees for their constructive review comments, helping to improve the readability of the paper. Ning Chen's research was supported by the AcRF Tier 2 Grant of Singapore (No. MOE2012-T2-2-071). Xiaotie Deng was supported by Shanghai Jiaotong University with a 985 Project Grant and by an NSFC Grant No. 61173011. Paul W. Goldberg was supported by EPSRC Grant EP/G069239/1 "Efficient Decentralised Approaches in Algorithmic Game Theory" and EPSRC grant EP/K01000X/1 "Efficient Algorithms for Mechanism Design Without Monetary Transfer. Jinshan Zhang was supported by EPSRC Grant EP/K01000X/1 "Efficient Algorithms for Mechanism Design Without Monetary Transfer.

Research Keywords

Competitive equilibrium
Envy-free
Position auction
Revenue maximization
Sharp demand

Access Output

10.1007/s10878-014-9817-y

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{67b7fcdb69704d528f39800394729b25,

title = "On revenue maximization with sharp multi-unit demands",

abstract = "We consider markets consisting of a set of indivisible items, and buyers that have sharp multi-unit demand. This means that each buyer (Formula presented.) wants a specific number (Formula presented.) of items; a bundle of size less than (Formula presented.) has no value. We consider the objective of setting prices and allocations in order to maximize the total revenue of the market maker. The pricing problem with sharp multi-unit demand buyers has a number of properties that the unit-demand model does not possess, and is an important question in algorithmic pricing. We consider the problem of computing a revenue maximizing solution for two solution concepts: competitive equilibrium and envy-free pricing. For unrestricted valuations, these problems are NP-complete; we focus on a realistic special case of “correlated values” where each buyer (Formula presented.) has a valuation (Formula presented.) for item (Formula presented.) , where (Formula presented.) and (Formula presented.) are positive quantities associated with buyer (Formula presented.) and item (Formula presented.) respectively. We present a polynomial time algorithm to solve the revenue-maximizing competitive equilibrium problem. For envy-free pricing, if the demand of each buyer is bounded by a constant, a revenue maximizing solution can be found efficiently; the general demand case is shown to be NP-hard. {\textcopyright} 2014, Springer Science+Business Media New York.",

keywords = "Competitive equilibrium, Envy-free, Position auction, Revenue maximization, Sharp demand",

author = "Ning Chen and Xiaotie Deng and Goldberg, \{Paul W.\} and Jinshan Zhang",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "2016",

month = apr,

day = "1",

doi = "10.1007/s10878-014-9817-y",

language = "English",

volume = "31",

pages = "1174--1205",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - On revenue maximization with sharp multi-unit demands

AU - Chen, Ning

AU - Deng, Xiaotie

AU - Goldberg, Paul W.

AU - Zhang, Jinshan

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2016/4/1

Y1 - 2016/4/1

N2 - We consider markets consisting of a set of indivisible items, and buyers that have sharp multi-unit demand. This means that each buyer (Formula presented.) wants a specific number (Formula presented.) of items; a bundle of size less than (Formula presented.) has no value. We consider the objective of setting prices and allocations in order to maximize the total revenue of the market maker. The pricing problem with sharp multi-unit demand buyers has a number of properties that the unit-demand model does not possess, and is an important question in algorithmic pricing. We consider the problem of computing a revenue maximizing solution for two solution concepts: competitive equilibrium and envy-free pricing. For unrestricted valuations, these problems are NP-complete; we focus on a realistic special case of “correlated values” where each buyer (Formula presented.) has a valuation (Formula presented.) for item (Formula presented.) , where (Formula presented.) and (Formula presented.) are positive quantities associated with buyer (Formula presented.) and item (Formula presented.) respectively. We present a polynomial time algorithm to solve the revenue-maximizing competitive equilibrium problem. For envy-free pricing, if the demand of each buyer is bounded by a constant, a revenue maximizing solution can be found efficiently; the general demand case is shown to be NP-hard. © 2014, Springer Science+Business Media New York.

AB - We consider markets consisting of a set of indivisible items, and buyers that have sharp multi-unit demand. This means that each buyer (Formula presented.) wants a specific number (Formula presented.) of items; a bundle of size less than (Formula presented.) has no value. We consider the objective of setting prices and allocations in order to maximize the total revenue of the market maker. The pricing problem with sharp multi-unit demand buyers has a number of properties that the unit-demand model does not possess, and is an important question in algorithmic pricing. We consider the problem of computing a revenue maximizing solution for two solution concepts: competitive equilibrium and envy-free pricing. For unrestricted valuations, these problems are NP-complete; we focus on a realistic special case of “correlated values” where each buyer (Formula presented.) has a valuation (Formula presented.) for item (Formula presented.) , where (Formula presented.) and (Formula presented.) are positive quantities associated with buyer (Formula presented.) and item (Formula presented.) respectively. We present a polynomial time algorithm to solve the revenue-maximizing competitive equilibrium problem. For envy-free pricing, if the demand of each buyer is bounded by a constant, a revenue maximizing solution can be found efficiently; the general demand case is shown to be NP-hard. © 2014, Springer Science+Business Media New York.

KW - Competitive equilibrium

KW - Envy-free

KW - Position auction

KW - Revenue maximization

KW - Sharp demand

UR - https://www.scopus.com/pages/publications/84961057432

UR - https://www.scopus.com/pages/publications/84961057432#tab=impact

U2 - 10.1007/s10878-014-9817-y

DO - 10.1007/s10878-014-9817-y

M3 - RGC 21 - Publication in refereed journal

SN - 1382-6905

VL - 31

SP - 1174

EP - 1205

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 3

ER -

On revenue maximization with sharp multi-unit demands

Abstract

Bibliographical note

Funding

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this