Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPrior-free Dynamic Mechanism Design With Limited Liability
109
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study the problem of repeatedly auctioning off an item to one of $k$ bidders where: a) bidders have a per-round individual rationality constraint, b) bidders may leave the mechanism at any point, and c) the bidders valuations are adversarially chosen (the prior-free setting). Without these constraints, the auctioneer can run a second-price auction to sell the business and receive the second highest total value for the entire stream of items. We show that under these constraints, the auctioneer can attain a constant fraction of the sell the business benchmark, but no more than $2/e$ of this benchmark. In the course of doing so, we design mechanisms for a single bidder problem of independent interest: how should you repeatedly sell an item to a (per-round IR) buyer with adversarial valuations if you know their total value over all rounds is $V$ but not how their value changes over time? We demonstrate a mechanism that achieves revenue $V/e$ and show that this is tight.
rate research
Read More
Mechanism design has traditionally assumed that the set of participants are fixed and known to the mechanism (the market owner) in advance. However, in practice, the market owner can only directly reach a small number of participants (her neighbours). Hence the owner often needs costly promotions to recruit more participants in order to get desirable outcomes such as social welfare or revenue maximization. In this paper, we propose to incentivize existing participants to invite their neighbours to attract more participants. However, they would not invite each other if they are competitors. We discuss how to utilize the conflict of interest between the participants to incentivize them to invite each other to form larger markets. We will highlight the early solutions and open the floor for discussing the fundamental open questions in the settings of auctions, coalitional games, matching and voting.
We study Bayesian automated mechanism design in unstructured dynamic environments, where a principal repeatedly interacts with an agent, and takes actions based on the strategic agents report of the current state of the world. Both the principal and the agent can have arbitrary and potentially different valuations for the actions taken, possibly also depending on the actual state of the world. Moreover, at any time, the state of the world may evolve arbitrarily depending on the action taken by the principal. The goal is to compute an optimal mechanism which maximizes the principals utility in the face of the self-interested strategic agent. We give an efficient algorithm for computing optimal mechanisms, with or without payments, under different individual-rationality constraints, when the time horizon is constant. Our algorithm is based on a sophisticated linear program formulation, which can be customized in various ways to accommodate richer constraints. For environments with large time horizons, we show that the principals optimal utility is hard to approximate within a certain constant factor, complementing our algorithmic result. We further consider a special case of the problem where the agent is myopic, and give a refined efficient algorithm whose time complexity scales linearly in the time horizon. Moreover, we show that memoryless mechanisms do not provide a good solution for our problem, in terms of both optimality and computational tractability. These results paint a relatively complete picture for automated dynamic mechanism design in unstructured environments. Finally, we present experimental results where our algorithms are applied to synthetic dynamic environments with different characteristics, which not only serve as a proof of concept for our algorithms, but also exhibit intriguing phenomena in dynamic mechanism design.
We study contests where the designers objective is an extension of the widely studied objective of maximizing the total output: The designer gets zero marginal utility from a players output if the output of the player is very low or very high. We model this using two objective functions: binary threshold, where a players contribution to the designers utility is 1 if her output is above a certain threshold, and 0 otherwise; and linear threshold, where a players contribution is linear if her output is between a lower and an upper threshold, and becomes constant below the lower and above the upper threshold. For both of these objectives, we study (1) rank-order allocation contests that use only the ranking of the players to assign prizes and (2) general contests that may use the numerical values of the players outputs to assign prizes. We characterize the optimal contests that maximize the designers objective and indicate techniques to efficiently compute them. We also prove that for the linear threshold objective, a contest that distributes the prize equally among a fixed number of top-ranked players offers a factor-2 approximation to the optimal rank-order allocation contest.
The Competition Complexity of an auction measures how much competition is needed for the revenue of a simple auction to surpass the optimal revenue. A classic result from auction theory by Bulow and Klemperer [9], states that the Competition Complexity of VCG, in the case of n i.i.d. buyers and a single item, is 1, i.e., it is better to recruit one extra buyer and run a second price auction than to learn exactly the buyers underlying distribution and run the revenue-maximizing auction tailored to this distribution. In this paper we study the Competition Complexity of dynamic auctions. Consider the following setting: a monopolist is auctioning off m items in m consecutive stages to n interested buyers. A buyer realizes her value for item k in the beginning of stage k. We prove that the Competition Complexity of dynamic auctions is at most 3n, and at least linear in n, even when the buyers values are correlated across stages, under a monotone hazard rate assumption on the stage (marginal) distributions. We also prove results on the number of additional buyers necessary for VCG at every stage to be an {alpha}-approximation of the optimal revenue; we term this number the {alpha}-approximate Competition Complexity. As a corollary we provide the first results on prior-independent dynamic auctions. This is, to the best of our knowledge, the first non-trivial positive guarantees for simple ex-post IR dynamic auctions for correlated stages. A key step towards proving bounds on the Competition Complexity is getting a good benchmark/upper bound to the optimal revenue. To this end, we extend the recent duality framework of Cai et al. [12] to dynamic settings. As an aside to our approach we obtain a revenue non-monotonicity lemma for dynamic auctions, which may be of independent interest.
In this study, we apply reinforcement learning techniques and propose what we call reinforcement mechanism design to tackle the dynamic pricing problem in sponsored search auctions. In contrast to previous game-theoretical approaches that heavily rely on rationality and common knowledge among the bidders, we take a data-driven approach, and try to learn, over repeated interactions, the set of optimal reserve prices. We implement our approach within the current sponsored search framework of a major search engine: we first train a buyer behavior model, via a real bidding data set, that accurately predicts bids given information that bidders are aware of, including the game parameters disclosed by the search engine, as well as the bidders KPI data from previous rounds. We then put forward a reinforcement/MDP (Markov Decision Process) based algorithm that optimizes reserve prices over time, in a GSP-like auction. Our simulations demonstrate that our framework outperforms static optimization strategies including the ones that are currently in use, as well as several other dynamic ones.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
