Pricing commodities

Robert Krauthgamer; Aranyak Mehta; Atri Rudra

doi:10.1016/j.tcs.2009.10.002

Pricing commodities

Robert Krauthgamer
, Aranyak Mehta
, Atri Rudra

Department of Computer Science and Engineering

Weizmann Institute of Science
Alphabet Inc.

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

How should a seller price her goods in a market where each buyer prefers a single good among his desired goods, and will buy the cheapest such good, as long as it is within his budget? We provide efficient algorithms that compute near-optimal prices for this problem, focusing on a commodity market, where the range of buyer budgets is small. We also show that our LP rounding based technique easily extends to a different scenario, in which the buyers want to buy all the desired goods, as long as they are within budget.

Original language	English
Pages (from-to)	602-613
Number of pages	12
Journal	Theoretical Computer Science
Volume	412
Issue number	7
DOIs	https://doi.org/10.1016/j.tcs.2009.10.002
State	Published - Feb 25 2011

Keywords

Approximation algorithms
Combinatorial bidding
LP rounding
Pricing
Revenue maximization
Single-minded bidders
Unit-demand bidders

Access to Document

10.1016/j.tcs.2009.10.002

Cite this

@article{643a0477460f4d1fbea97a0ed81b1f90,

title = "Pricing commodities",

abstract = "How should a seller price her goods in a market where each buyer prefers a single good among his desired goods, and will buy the cheapest such good, as long as it is within his budget? We provide efficient algorithms that compute near-optimal prices for this problem, focusing on a commodity market, where the range of buyer budgets is small. We also show that our LP rounding based technique easily extends to a different scenario, in which the buyers want to buy all the desired goods, as long as they are within budget.",

keywords = "Approximation algorithms, Combinatorial bidding, LP rounding, Pricing, Revenue maximization, Single-minded bidders, Unit-demand bidders",

author = "Robert Krauthgamer and Aranyak Mehta and Atri Rudra",

year = "2011",

month = feb,

day = "25",

doi = "10.1016/j.tcs.2009.10.002",

language = "English",

volume = "412",

pages = "602--613",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "7",

}

TY - JOUR

T1 - Pricing commodities

AU - Krauthgamer, Robert

AU - Mehta, Aranyak

AU - Rudra, Atri

PY - 2011/2/25

Y1 - 2011/2/25

N2 - How should a seller price her goods in a market where each buyer prefers a single good among his desired goods, and will buy the cheapest such good, as long as it is within his budget? We provide efficient algorithms that compute near-optimal prices for this problem, focusing on a commodity market, where the range of buyer budgets is small. We also show that our LP rounding based technique easily extends to a different scenario, in which the buyers want to buy all the desired goods, as long as they are within budget.

AB - How should a seller price her goods in a market where each buyer prefers a single good among his desired goods, and will buy the cheapest such good, as long as it is within his budget? We provide efficient algorithms that compute near-optimal prices for this problem, focusing on a commodity market, where the range of buyer budgets is small. We also show that our LP rounding based technique easily extends to a different scenario, in which the buyers want to buy all the desired goods, as long as they are within budget.

KW - Approximation algorithms

KW - Combinatorial bidding

KW - LP rounding

KW - Pricing

KW - Revenue maximization

KW - Single-minded bidders

KW - Unit-demand bidders

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

U2 - 10.1016/j.tcs.2009.10.002

DO - 10.1016/j.tcs.2009.10.002

M3 - Article

AN - SCOPUS:78751577610

SN - 0304-3975

VL - 412

SP - 602

EP - 613

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 7

ER -

Pricing commodities

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this