An official website of the United States government
We investigate the problem of designing differentially private (DP), revenue- maximizing single item auction. Specifically, we consider broadly applicable settings in mechanism design where agents’ valuation distributions are indepen- dent, non-identical, and can be either bounded or unbounded. Our goal is to design such auctions with pure, i.e., (ω, 0) privacy in polynomial time.
more »
« less
An Efficient epsilon-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization
We consider the black-box reduction from multi-dimensional revenue maximization to virtual welfare maximization. Cai et al. [12, 13, 14, 15] show a polynomial-time approximation-preserving re-duction, however, the mechanism produced by their reduction is only approximately Bayesian incentive compatible (ε-BIC). We provide two new polynomial time transformations that convert anyε-BICmechanism to an exactly BIC mechanism with only a negligible revenue loss. (i) Our first transformation applies to any mechanism design setting with downward-closed outcome space and only requires sample accessto the agents’ type distributions. (ii) Our second transformation applies to the fully general outcome space, removing the downward-closed assumption, but requires full access to the agents’ type distributions. Both transformations only require query access to the originalε-BIC mechanism. Otherε-BIC to BICtransformations for revenue exist in the literature but all require exponential time to run in either of the settings we consider. As an application of our transformations, we improve the reduction by Cai et al. to generate an exactly BIC mechanism.
more »
« less
- Award ID(s):
- 1942583
- PAR ID:
- 10196401
- Date Published:
- Journal Name:
- ACM-SIAM Symposium on Discrete Algorithms (SODA21)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the menu complexity of optimal and approximately-optimal auctions in the context of the ``FedEx'' problem, a so-called ``one-and-a-half-dimensional'' setting where a single bidder has both a value and a deadline for receiving an item [FGKK 16]. The menu complexity of an auction is equal to the number of distinct (allocation, price) pairs that a bidder might receive [HN 13]. We show the following when the bidder has $$n$$ possible deadlines: 1) Exponential menu complexity is necessary to be exactly optimal: There exist instances where the optimal mechanism has menu complexity $$\geq 2^n-1$$. This matches exactly the upper bound provided by Fiat et al.'s algorithm, and resolves one of their open questions [FGKK 16]. 2) Fully polynomial menu complexity is necessary and sufficient for approximation: For all instances, there exists a mechanism guaranteeing a multiplicative $$(1-\epsilon)$$-approximation to the optimal revenue with menu complexity $$O(n^{3/2}\sqrt{\frac{\min\{n/\epsilon,\ln(v_{\max})\}}{\epsilon}}) = O(n^2/\epsilon)$$, where $$v_{\max}$$ denotes the largest value in the support of integral distributions. \item There exist instances where any mechanism guaranteeing a multiplicative $(1-O(1/n^2))$-approximation to the optimal revenue requires menu complexity $$\Omega(n^2)$$. Our main technique is the polygon approximation of concave functions [Rote 91], and our results here should be of independent interest. We further show how our techniques can be used to resolve an open question of [DW 17] on the menu complexity of optimal auctions for a budget-constrained buyer.more » « less
-
We design and analyze deterministic and randomized clock auctions for single-parameter domains with downward-closed feasibility constraints, aiming to maximize the social welfare. Clock auctions have been shown to satisfy a list of compelling incentive properties making them a very practical solution for real-world applications, partly because they require very little reasoning from the participating bidders. However, the first results regarding the worst-case performance of deterministic clock auctions from a welfare maximization perspective indicated that they face obstacles even for a seemingly very simple family of instances, leading to a logarithmic inapproximability result; this inapproximability result is information-theoretic and holds even if the auction has unbounded computational power. In this paper we propose a deterministic clock auction that achieves a logarithmic approximation for any downward-closed set system, using black box access to a solver for the underlying optimization problem. This proves that our clock auction is optimal and that the aforementioned family of instances exactly captures the information limitations of deterministic clock auctions. We then move beyond deterministic auctions and design randomized clock auctions that achieve improved approximation guarantees for a generalization of this family of instances, suggesting that the earlier indications regarding the performance of clock auctions may have been overly pessimistic.more » « less
-
null (Ed.)We identify the first static credible mechanism for multi-item additive auctions that achieves a constant factor of the optimal revenue. This is one instance of a more general framework for designing two-part tariff auctions, adapting the duality framework of Cai et al [CDW16]. Given a (not necessarily incentive compatible) auction format A satisfying certain technical conditions, our framework augments the auction with a personalized entry fee for each bidder, which must be paid before the auction can be accessed. These entry fees depend only on the prior distribution of bidder types, and in particular are independent of realized bids. Our framework can be used with many common auction formats, such as simultaneous first-price, simultaneous second-price, and simultaneous all-pay auctions. If all-pay auctions are used, we prove that the resulting mechanism is credible in the sense that the auctioneer cannot benefit by deviating from the stated mechanism after observing agent bids. If second-price auctions are used, we obtain a truthful O(1)-approximate mechanism with fixed entry fees that are amenable to tuning via online learning techniques. Our results for first price and all-pay are the first revenue guarantees of non-truthful mechanisms in multi-dimensional environments; an open question in the literature [RST17].more » « less
-
Naor, Joseph; Buchbinder, Niv (Ed.)We consider the bilateral trade problem, in which two agents trade a single indivisible item. It is known that the only dominant-strategy truthful mechanism is the fixed-price mechanism: given commonly known distributions of the buyer's value B and the seller's value S, a price p is offered to both agents and trade occurs if S ≤ p ≤ B. The objective is to maximize either expected welfare or expected gains from trade . We improve the approximation ratios for several welfare maximization variants of this problem. When the agents' distributions are identical, we show that the optimal approximation ratio for welfare is . With just one prior sample from the common distribution, we show that a 3/4-approximation to welfare is achievable. When agents' distributions are not required to be identical, we show that a previously best-known (1–1/e)-approximation can be strictly improved, but 1–1/e is optimal if only the seller's distribution is known.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
