In revenue maximization of selling a digital product in a social network, the utility of an agent is often considered to have two parts: a private valuation, and linearly additive influences from other agents. We study the incomplete information case where agents know a common distribution about others' private valuations, and make decisions simultaneously. The "rational behavior" of agents in this case is captured by the well-known Bayesian Nash equilibrium. Two challenging questions arise: how to compute an equilibrium and how to optimize a pricing strategy accordingly to maximize the revenue assuming agents follow the equilibrium? In this paper, we mainly focus on the natural model where the private valuation of each agent is sampled from a uniform distribution, which turns out to be already challenging. Our main result is a polynomial-time algorithm that can exactly compute the equilibrium and the optimal price, when pairwise influences are non-negative. If negative influences are allowed, computing any equilibrium even approximately is PPAD-hard. Our algorithm can also be used to design an FPTAS for optimizing discriminative price profile.
If the value of the product does not exhibit social influence, the seller can maximize the revenue following the optimal auction process by the seminal work of Myerson @cite_5 . Truthful auction mechanisms have also been studied for digital goods, where one can achieve constant ratio of the profit with optimal fixed price @cite_21 @cite_19 . On computing equilibria for problems that guarantees to find an equilibrium through iterative methods, most of them, for instance the famous congestion game, is proved to be PLS-hard @cite_7 .
@cite_19 @cite_5 @cite_21 @cite_7
2404718321 2021734699 1484450013 2333413293
We consider the problem of maximizing revenue in prior-free auctions for general single parameter settings. The setting is modeled by an arbitrary downward-closed set system, which captures many special cases such as single item, digital goods and single-minded combinatorial auctions. We relax the truthfulness requirement by the solution concept of Nash equilibria. Implementation by Nash equilibria is a natural and relevant framework in many applications of computer science, where auctions are run repeatedly and bidders can observe others’ strategies, but the auctioneer needs to design a mechanism in advance and cannot use any information on the bidders’ private valuations. We introduce a worst-case revenue benchmark which generalizes the second price of single item auction and the F2 benchmark, introduced by , for digital goods. We design a mechanism whose Nash equilibria obtains at least a constant factor of this benchmark and prove that no truthful mechanisms can achieve a constant approximation. We consider the problem of designing a revenue-maximizing auction for a single item, when the values of the bidders are drawn from a correlated distribution. We observe that there exists an algorithm that finds the optimal randomized mechanism that runs in time polynomial in the size of the support. We leverage this result to show that in the oracle model introduced by Ronen and Saberi [FOCS'02], there exists a polynomial time truthful in expectation mechanism that provides a (1.5+e)-approximation to the revenue achievable by an optimal truthful-in-expectation mechanism, and a polynomial time deterministic truthful mechanism that guarantees 5 3 approximation to the revenue achievable by an optimal deterministic truthful mechanism. We show that the 5 3-approximation mechanism provides the same approximation ratio also with respect to the optimal truthful-in-expectation mechanism. This shows that the performance gap between truthful-in-expectation and deterministic mechanisms is relatively small. En route, we solve an open question of Mehta and Vazirani [EC'04]. Finally, we extend some of our results to the multi-item case, and show how to compute the optimal truthful-in-expectation mechanisms for bidders with more complex valuations. Motivated by sponsored search auctions with hard budget constraints given by the advertisers, we study multi-unit auctions of a single item. An important example is a sponsored result slot for a keyword, with many units representing its inventory in a month, say. In this single-item multi-unit auction, each bidder has a private value for each unit, and a private budget which is the total amount of money she can spend in the auction. A recent impossibility result [, FOCS’08] precludes the existence of a truthful mechanism with Paretooptimal allocations in this important setting. We propose Sort-Cut, a mechanism which does the next best thing from the auctioneer’s point of view, that we term semi-truthful. While we are unable to give a complete characterization of equilibria for our mechanism, we prove that some equilibrium of the proposed mechanism optimizes the revenue over all Pareto-optimal mechanisms, and that this equilibrium is the unique one resulting from a natural rational bidding strategy (where every losing bidder bids at least her true value). Perhaps even more significantly, we show that the revenue of every equilibrium of our mechanism differs by at most the budget of one bidder from the optimum revenue (under some mild assumptions). A long-standing open question in algorithmic mechanism design is whether there exist computationally efficient truthful mechanisms for combinatorial auctions, with performance guarantees close to those possible without considerations of truthfulness. In this article, we answer this question negatively: the requirement of truthfulness can impact dramatically the ability of a mechanism to achieve a good approximation ratio for combinatorial auctions. More precisely, we show that every universally truthful randomized mechanism for combinatorial auctions with submodular valuations that approximates optimal social welfare within a factor of m1 2−e must use exponentially many value queries, where m is the number of items. Furthermore, we show that there exists a class of succinctly represented submodular valuation functions, for which the existence of a universally truthful polynomial-time mechanism that provides an m1 2−e-approximation would imply NP e RP. In contrast, ignoring truthfulness, there exist constant-factor approximation algorithms for this problem, and ignoring computational efficiency, the VCG mechanism is truthful and provides optimal social welfare. These are the first hardness results for truthful polynomial-time mechanisms for any type of combinatorial auctions, even for deterministic mechanisms. Our approach is based on a novel direct hardness technique that completely skips the notoriously hard step of characterizing truthful mechanisms. The characterization step was the main obstacle for proving impossibility results in algorithmic mechanism design so far.