Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Ratio of Revenue to Welfare in Single-Parameter Mechanism Design
172
0
0.0
(
0
)
Added by
Robert Kleinberg
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
What fraction of the potential social surplus in an environment can be extracted by a revenue-maximizing monopolist? We investigate this problem in Bayesian single-parameter environments with independent private values. The precise answer to the question obviously depends on the particulars of the environment: the feasibility constraint and the distributions from which the bidders private values are sampled. Rather than solving the problem in particular special cases, our work aims to provide universal lower bounds on the revenue-to-welfare ratio that hold under the most general hypotheses that allow for non-trivial such bounds. Our results can be summarized as follows. For general feasibility constraints, the revenue-to-welfare ratio is at least a constant times the inverse-square-root of the number of agents, and this is tight up to constant factors. For downward-closed feasibility constraints, the revenue-to-welfare ratio is bounded below by a constant. Both results require the bidders distributions to satisfy hypotheses somewhat stronger than regularity; we show that the latter result cannot avoid this requirement.
rate research
Read More
In quasi-proportional auctions, each bidder receives a fraction of the allocation equal to the weight of their bid divided by the sum of weights of all bids, where each bids weight is determined by a weight function. We study the relationship between the weight function, bidders private values, number of bidders, and the sellers revenue in equilibrium. It has been shown that if one bidder has a much higher private value than the others, then a nearly flat weight function maximizes revenue. Essentially, threatening the bidder who has the highest valuation with having to share the allocation maximizes the revenue. We show that as bidder private values approach parity, steeper weight functions maximize revenue by making the quasi-proportional auction more like a winner-take-all auction. We also show that steeper weight functions maximize revenue as the number of bidders increases. For flatter weight functions, there is known to be a unique pure-strategy Nash equilibrium. We show that a pure-strategy Nash equilibrium also exists for steeper weight functions, and we give lower bounds for bids at an equilibrium. For a special case that includes the two-bidder auction, we show that the pure-strategy Nash equilibrium is unique, and we show how to compute the revenue at equilibrium. We also show that selecting a weight function based on private value ratios and number of bidders is necessary for a quasi-proportional auction to produce more revenue than a second-price auction.
We present a polynomial-time algorithm that, given samples from the unknown valuation distribution of each bidder, learns an auction that approximately maximizes the auctioneers revenue in a variety of single-parameter auction environments including matroid environments, position environments, and the public project environment. The valuation distributions may be arbitrary bounded distributions (in particular, they may be irregular, and may differ for the various bidders), thus resolving a problem left open by previous papers. The analysis uses basic tools, is performed in its entirety in value-space, and simplifies the analysis of previously known results for special cases. Furthermore, the analysis extends to certain single-parameter auction environments where precise revenue maximization is known to be intractable, such as knapsack environments.
Bike sharing systems have been widely deployed around the world in recent years. A core problem in such systems is to reposition the bikes so that the distribution of bike supply is reshaped to better match the dynamic bike demand. When the bike-sharing company or platform is able to predict the revenue of each reposition task based on historic data, an additional constraint is to cap the payment for each task below its predicted revenue. In this paper, we propose an incentive mechanism called {em TruPreTar} to incentivize users to park bicycles at locations desired by the platform toward rebalancing supply and demand. TruPreTar possesses four important economic and computational properties such as truthfulness and budget feasibility. Furthermore, we prove that even when the payment budget is tight, the total revenue still exceeds or equals the budget. Otherwise, TruPreTar achieves 2-approximation as compared to the optimal (revenue-maximizing) solution, which is close to the lower bound of at least $sqrt{2}$ that we also prove. Using an industrial dataset obtained from a large bike-sharing company, our experiments show that TruPreTar is effective in rebalancing bike supply and demand and, as a result, generates high revenue that outperforms several benchmark mechanisms.
We study equilibria of markets with $m$ heterogeneous indivisible goods and $n$ consumers with combinatorial preferences. It is well known that a competitive equilibrium is not guaranteed to exist when valuations are not gross substitutes. Given the widespread use of bundling in real-life markets, we study its role as a stabilizing and coordinating device by considering the notion of emph{competitive bundling equilibrium}: a competitive equilibrium over the market induced by partitioning the goods for sale into fixed bundles. Compared to other equilibrium concepts involving bundles, this notion has the advantage of simulatneous succinctness ($O(m)$ prices) and market clearance. Our first set of results concern welfare guarantees. We show that in markets where consumers care only about the number of goods they receive (known as multi-unit or homogeneous markets), even in the presence of complementarities, there always exists a competitive bundling equilibrium that guarantees a logarithmic fraction of the optimal welfare, and this guarantee is tight. We also establish non-trivial welfare guarantees for general markets, two-consumer markets, and markets where the consumer valuations are additive up to a fixed budget (budget-additive). Our second set of results concern revenue guarantees. Motivated by the fact that the revenue extracted in a standard competitive equilibrium may be zero (even with simple unit-demand consumers), we show that for natural subclasses of gross substitutes valuations, there always exists a competitive bundling equilibrium that extracts a logarithmic fraction of the optimal welfare, and this guarantee is tight. The notion of competitive bundling equilibrium can thus be useful even in markets which possess a standard competitive equilibrium.
We consider revenue-optimal mechanism design in the interdimensional setting, where one dimension is the value of the buyer, and one is a type that captures some auxiliary information. One setting is the FedEx Problem, for which FGKK [2016] characterize the optimal mechanism for a single agent. We ask: how far can such characterizations go? In particular, we consider single-minded agents. A seller has heterogenous items. A buyer has a value v for a specific subset of items S, and obtains value v iff he gets (at least) all the items in S. We show: 1. Deterministic mechanisms are optimal for distributions that satisfy the declining marginal revenue (DMR) property; we give an explicit construction of the optimal mechanism. 2. Without DMR, the result depends on the structure of the directed acyclic graph (DAG) representing the partial order among types. When the DAG has out-degree at most 1, we characterize the optimal mechanism a la FedEx. 3. Without DMR, when the DAG has some node with out-degree at least 2, we show that in this case the menu complexity is unbounded: for any M, there exist distributions over (v,S) pairs such that the menu complexity of the optimal mechanism is at least M. 4. For the case of 3 types, we show that for all distributions there exists an optimal mechanism of finite menu complexity. This is in contrast to 2 additive heterogenous items or which the menu complexity could be uncountable [MV07; DDT15]. In addition, we prove that optimal mechanisms for Multi-Unit Pricing (without DMR) can have unbounded menu complexity. We also propose an extension where the menu complexity of optimal mechanisms can be countable but not uncountable. Together these results establish that optimal mechanisms in interdimensional settings are both much richer than single-dimensional settings, yet also vastly more structured than multi-dimensional settings.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
