The DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Algorithmic pricing via virtual valuations
Open accessAbstract
Algorithmic pricing is the computational problem that sellers (e.g.,in supermarkets) face when trying to set prices for their items to maximize their profit in the presence of a known demand. Guruswami etal. (SODA, 2005) proposed this problem and gave logarithmic approximations (in the number of consumers) for the unit-demand and single-parameter cases where there is a specific set of consumers and their valuations for bundles are known precisely. Subsequently several versions of the problem have been shown to have poly-logarithmic in approximability. This problem has direct ties to the important open question of better understanding the Bayesian optimal mechanism in multi-parameter agent settings; however, for this purpose approximation factors logarithmic in the number of agents are inadequate. It is therefore of vital interest to consider special cases where constant approximations are possible. We consider the unit-demand variant of this pricing problem. Here a consumer has a valuation for each different item and their value for aset of items is simply the maximum value they have for any item in the set. Instead of considering a set of consumers with precisely known preferences, like the prior algorithmic pricing literature, we assume that the preferences of the consumers are drawn from a distribution. This is the standard assumption in economics; furthermore, the setting of a specific set of customers with specific preferences, which is employed in all of the prior work in algorithmic pricing, is a special case of this general Bayesian pricing problem, where there is a discrete Bayesian distribution for preferences specified by picking one consumer uniformly from the given set of consumers. Notice that the distribution over the valuations for the individual items that this generates is obviously correlated. Our work complements these existing works by considering the case where the consumer's valuations for the different items are independent random variables. Our main result is a constant approximation algorithm for this problem that makes use of an interesting connection between this problem and the concept of virtual valuations from the single-parameter Bayesian optimal mechanism design literature.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Myerson, R. B. (1981) · Mathematics of Operations Research · doi:10.1287/moor.6.1.58 · Cited by 5,920
The Simple Economics of Optimal Auctions
Bulow, J., & Roberts, J. (1989) · Journal of Political Economy · doi:10.1086/261643 · Cited by 591
On profit-maximizing envy-free pricing
Guruswami, V., Hartline, J. D., Karlin, A. R., Kempe, D., Mathieu, C., & McSherry, F. (2005) · Symposium on Discrete Algorithms · doi:10.5555/1070432.1070598 · Cited by 274
Self-citationRecent Developments in the Economics of Price Discrimination
Armstrong, M. (2013) · Advances in Economics and Econometrics · doi:10.1017/cbo9781139052276.006 · Cited by 267
Price Discrimination and Competition
Stole, L. (2007) · Cited by 241
Mechanism Design via Machine Learning
Balcan, M.-F., & Blum, A. L. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.50 · Cited by 129
Combination can be hard: approximability of the unique coverage problem
Demaine, E. D., Hajiaghayi, M., Feige, U., & Salavatipour, M. R. (2006) · Symposium on Discrete Algorithms · doi:10.5555/1109557.1109577 · Cited by 88
Cited by
Simple versus optimal mechanisms
Hartline, J. D., & Roughgarden, T. (2009) · Proceedings of the 10th ACM conference on Electronic commerce · doi:10.1145/1566374.1566407 · Cited by 304
Self-citationRevenue Optimization with Approximate Bid Predictions
Medina, A. M., & Vassilvitskii, S. (2017) · arXiv · doi:10.48550/arxiv.1706.04732 · Cited by 51
Metadata
- Authors
- Chawla, S., Hartline, J. D., & Kleinberg, R.
- Venue
- Proceedings of the 8th ACM conference on Electronic commerce
- Publisher
- ACM
- Published
- 2007-06-11
- Pages
- 243-251
- OpenAlex
- W2107403260
- Cited by
- 260
- References
- 7
- FWCI
- 11.94
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Algorithmic pricing via virtual valuations. https://app.cochat.ai/papers/10.1145/1250910.1250946
- The paper
- Chawla, S., Hartline, J. D., & Kleinberg, R. (2007). Algorithmic pricing via virtual valuations. Proceedings of the 8th ACM conference on Electronic commerce. https://doi.org/10.1145/1250910.1250946
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.