skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Minimizing Regret with Multiple Reserves
We study the problem of computing and learning non-anonymous reserve prices to maximize revenue. We first define the M aximizing M ultiple R eserves (MMR) problem in single-parameter matroid environments, where the input is m valuation profiles v 1 ,…, v m , indexed by the same n bidders, and the goal is to compute the vector r of (non-anonymous) reserve prices that maximizes the total revenue obtained on these profiles by the VCG mechanism with reserves r . We prove that the problem is APX -hard, even in the special case of single-item environments, and give a polynomial-time 1/2-approximation algorithm for it in arbitrary matroid environments. We then consider the online no-regret learning problem and show how to exploit the special structure of the MMR problem to translate our offline approximation algorithm into an online learning algorithm that achieves asymptotically time-averaged revenue at least 1/2 times that of the best fixed reserve prices in hindsight. On the negative side, we show that, quite generally, computational hardness for the offline optimization problem translates to computational hardness for obtaining vanishing time-averaged regret. Thus, our hardness result for the MMR problem implies that computationally efficient online learning requires approximation, even in the special case of single-item auction environments.  more » « less
Award ID(s):
1929788
PAR ID:
10303831
Author(s) / Creator(s):
 ;  
Date Published:
Journal Name:
ACM Transactions on Economics and Computation
Volume:
7
Issue:
3
ISSN:
2167-8375
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Proceedings of Machine Learning Research)
    Banerjee, Arindam; Fukumizu, Kenji (Ed.)
    Numerous tasks in machine learning and artificial intelligence have been modeled as submodular maximization problems. These problems usually involve sensitive data about individuals, and in addition to maximizing the utility, privacy concerns should be considered. In this paper, we study the general framework of non-negative monotone submodular maximization subject to matroid or knapsack constraints in both offline and online settings. For the offline setting, we propose a differentially private $$(1-\frac{\kappa}{e})$$-approximation algorithm, where $$\kappa\in[0,1]$$ is the total curvature of the submodular set function, which improves upon prior works in terms of approximation guarantee and query complexity under the same privacy budget. In the online setting, we propose the first differentially private algorithm, and we specify the conditions under which the regret bound scales as $$Ø(\sqrt{T})$$, i.e., privacy could be ensured while maintaining the same regret bound as the optimal regret guarantee in the non-private setting. 
    more » « less
  2. (, Advances in neural information processing systems)
    Online pricing has been the focus of extensive research in recent years, particularly in the context of selling an item to sequentially arriving users. However, what if a provider wants to maximize revenue by selling multiple items to multiple users in each round? This presents a complex problem, as the provider must intelligently offer the items to those users who value them the most without exceeding their highest acceptable prices. In this study, we tackle this challenge by designing online algorithms that can efficiently offer and price items while learning user valuations from accept/reject feedback. We focus on three user valuation models (fixed valuations, random experiences, and random valuations) and provide algorithms with nearly-optimal revenue regret guarantees. In particular, for any market setting with N users, M items, and load L (which roughly corresponds to the maximum number of simultaneous allocations possible), our algorithms achieve regret of order O(NMloglog(LT)) under fixed valuations model, O(√NMLT) under random experiences model and O(√NMLT) under random valuations model in T rounds. 
    more » « less
  3. ; (, Socio-Economic Review)
    Abstract Although economic sociology emphasizes the role of social networks for shaping economic action, little research has examined how network governance structures affect prices in the unregulated and high-risk social context of online criminal trade. We consider how overembeddedness—a state of excessive interconnectedness among market actors—arises from endogenous trade relations to shape prices in illegal online markets with aggregate consequences for short-term gross illegal revenue. Drawing on transaction-level data on 16 847 illegal drug transactions over 14 months of trade in a ‘darknet’ drug market, we assess how repeated exchanges and closure in buyer–vendor trade networks nonlinearly influence prices and short-term gross revenue from illegal drug trade. Using a series of panel models, we find that increases in closure and repeated exchange raise prices until a threshold is reached upon which prices and gross monthly revenue begin to decline as networks become overembedded. Findings provide insight into the network determinants of prices and gross monthly revenue in illegal online drug trade and illustrate how network structure shapes prices in criminal markets, even in anonymous trade environments. 
    more » « less
  4. ; ; ; (, Economics and Computation)
    We consider the problem of a single seller repeatedly selling a single item to a single buyer (specifically, the buyer has a value drawn fresh from known distribution $$D$$ in every round). Prior work assumes that the buyer is fully rational and will perfectly reason about how their bids today affect the seller's decisions tomorrow. In this work we initiate a different direction: the buyer simply runs a no-regret learning algorithm over possible bids. We provide a fairly complete characterization of optimal auctions for the seller in this domain. Specifically: 1) If the buyer bids according to EXP3 (or any ``mean-based'' learning algorithm), then the seller can extract expected revenue arbitrarily close to the expected welfare. This auction is independent of the buyer's valuation $$D$$, but somewhat unnatural as it is sometimes in the buyer's interest to overbid. 2) There exists a learning algorithm $$\mathcal{A}$$ such that if the buyer bids according to $$\mathcal{A}$$ then the optimal strategy for the seller is simply to post the Myerson reserve for $$D$$ every round. 3) If the buyer bids according to EXP3 (or any ``mean-based'' learning algorithm), but the seller is restricted to ``natural'' auction formats where overbidding is dominated (e.g. Generalized First-Price or Generalized Second-Price), then the optimal strategy for the seller is a pay-your-bid format with decreasing reserves over time. Moreover, the seller's optimal achievable revenue is characterized by a linear program, and can be unboundedly better than the best truthful auction yet simultaneously unboundedly worse than the expected welfare. 
    more » « less
  5. ; ; ; (, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing)
    We study the revenue guarantees and approximability of item pricing. Recent work shows that with n heterogeneous items, item-pricing guarantees an O(logn) approximation to the optimal revenue achievable by any (buy-many) mechanism, even when buyers have arbitrarily combinatorial valuations. However, finding good item prices is challenging – it is known that even under unit-demand valuations, it is NP-hard to find item prices that approximate the revenue of the optimal item pricing better than O(√n). Our work provides a more fine-grained analysis of the revenue guarantees and computational complexity in terms of the number of item “categories” which may be significantly fewer than n. We assume the items are partitioned in k categories so that items within a category are totally-ordered and a buyer’s value for a bundle depends only on the best item contained from every category. We show that item-pricing guarantees an O(logk) approximation to the optimal (buy-many) revenue and provide a PTAS for computing the optimal item-pricing when k is constant. We also provide a matching lower bound showing that the problem is (strongly) NP-hard even when k=1. Our results naturally extend to the case where items are only partially ordered, in which case the revenue guarantees and computational complexity depend on the width of the partial ordering, i.e. the largest set for which no two items are comparable. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email