The classic Vickrey-Clarke-Groves (VCG) mechanism ensures incentive compatibility, i.e., that truth-telling of all agents is a dominant strategy, for a static one-shot game. However, in a dynamic environment that unfolds over time, the agents' intertemporal payoffs depend on the expected future controls and payments, and a direct extension of the VCG mechanism is not sufficient to guarantee incentive compatibility. In fact, it does not appear to be feasible to construct mechanisms that ensure the dominance of dynamic truth-telling for agents comprised of general stochastic dynamic systems. The contribution of this paper is to show that such a dynamic stochastic extension does exist for the special case of Linear-Quadratic-Gaussian (LQG) agents with a careful construction of a sequence of layered payments over time. For a set of LQG agents, we propose a modified layered version of the VCG mechanism for payments that decouples the intertemporal effect of current bids on future payoffs, and prove that truth-telling of dynamic states forms a dominant strategy if system parameters are known and agents are rational. An important example of a problem needing such optimal dynamic coordination of stochastic agents arises in power systems where an Independent System Operator (ISO) has to ensure balance of generation and consumption at all time instants, while ensuring social optimality. The challenge is to determine a bidding scheme between all agents and the ISO that maximizes social welfare, while taking into account the stochastic dynamic models of agents, since renewable energy resources such as solar wind are stochastic and dynamic in nature, as are consumptions by loads which are influenced by factors such as local temperatures and thermal inertias of facilities.
In recent years, several papers have been written with the aim of exploring issues arising in dynamic mechanism design. In order to achieve ex post incentive compatibility, Bergemann and Valimaki @cite_15 propose a generalization of the VCG mechanism based on the marginal contribution of each agent and show that ex post participation constraints are satisfied under some conditions. Athey and Segal @cite_11 consider a similar model and focus on budget balance of the mechanism. @cite_6 derives first-order conditions under which incentive compatibility is guaranteed by generalizing Mirrlees's @cite_12 envelope formula of static mechanisms. @cite_16 considers a dynamic Markovian model and derives a sequence of Groves-like payments which achieves Markov perfect equilibrium. Bapna and Weber @cite_2 solves a sequential allocation problem by formulating it as a multi-armed bandit problem. Parkes and Singh @cite_13 and Friedman and Parkes @cite_1 consider an environment with randomly arriving and departing agents and propose a delayed'' VCG mechanism to guarantee interim incentive compatibility. @cite_5 and @cite_14 characterize the optimal infinite-horizon mechanism for an agent modeled as a Markov process, with Besanko considering a linear AR(1) process over a continuum of states, and Battaglini focusing on a two-state Markov chain.
@cite_14 @cite_1 @cite_6 @cite_2 @cite_5 @cite_15 @cite_16 @cite_13 @cite_12 @cite_11
2130359158 2963829287 2541696016 2084685902
We study mechanism design in dynamic quasilinear environments where private information arrives over time and decisions are made over multiple periods. We make three contributions. First, we provide a necessary condition for incentive compatibility that takes the form of an envelope formula for the derivative of an agent's equilibrium expected payoff with respect to his current type. It combines the familiar marginal effect of types on payoffs with novel marginal effects of the current type on future ones that are captured by “impulse response functions.” The formula yields an expression for dynamic virtual surplus that is instrumental to the design of optimal mechanisms and to the study of distortions under such mechanisms. Second, we characterize the transfers that satisfy the envelope formula and establish a sense in which they are pinned down by the allocation rule (“revenue equivalence”). Third, we characterize perfect Bayesian equilibrium‐implementable allocation rules in Markov environments, which yields tractable sufficient conditions that facilitate novel applications. We illustrate the results by applying them to the design of optimal mechanisms for the sale of experience goods (“bandit auctions”). The classic Vickrey-Clarke-Groves (VCG) mechanism ensures incentive compatibility, i.e., that truth-telling of all agents is a dominant strategy, for a static one-shot game. However, in a dynamic environment that unfolds over time, the agents' intertemporal payoffs depend on the expected future controls and payments, and a direct extension of the VCG mechanism is not sufficient to guarantee incentive compatibility. In fact, it does not appear to be feasible to construct mechanisms that ensure the dominance of dynamic truth-telling for agents comprised of general stochastic dynamic systems. The contribution of this paper is to show that such a dynamic stochastic extension does exist for the special case of Linear-Quadratic-Gaussian (LQG) agents with a careful construction of a sequence of layered payments over time. We propose a layered version of a modified VCG mechanism for payments that decouples the intertemporal effect of current bids on future payoffs, and prove that truth-telling of dynamic states forms a dominant strategy if system parameters are known and agents are rational. An important example of a problem needing such optimal dynamic coordination of stochastic agents arises in power systems where an Independent System Operator (ISO) has to ensure balance of generation and consumption at all time instants, while ensuring social optimality (maximization of the sum of the utilities of all agents). Addressing strategic behavior is critical as the price-taking assumption on market participants may not hold in an electricity market. Agents, can lie or otherwise game the bidding system. The challenge is to determine a bidding scheme between all agents and the ISO that maximizes social welfare, while taking into account the stochastic dynamic models of agents, since renewable energy resources such as solar wind are stochastic and dynamic in nature, as are consumptions by loads which are influenced by factors such as local temperatures and thermal inertias of facilities. This paper is about allocation of an infinitely divisible good to several rational and strategic agents. The allocation is done by a social planner who has limited information because the agents’ valuation functions are taken to be private information known only to the respective agents. We allow only a scalar signal, called a bid, from each agent to the social planner. Yang and Hajek [Yang, S., Hajek, B., 2007. “VCG-Kelly mechanisms for allocation of divisible goods: Adapting VCG mechanisms to one-dimensional signals”, IEEE Journal on Selected Areas in Communications 25 (6), 1237–1243.] and Johari and Tsitsiklis [Johari, R., Tsitsiklis, J. N., 2009. “Efficiency of scalar-parameterized mechanisms”, Operations Research 57 (4), 823–839.] proposed a scalar strategy Vickrey–Clarke–Groves (SSVCG) mechanism with efficient Nash equilibria. We consider a setting where the social planner desires minimal budget surplus. Example situations include fair sharing of Internet resources and auctioning of certain public goods where revenue maximization is not a consideration. Under the SSVCG framework, we propose a mechanism that is efficient and comes close to budget balance by returning much of the payments back to the agents in the form of rebates. We identify a design criterion for almost budget balance, impose feasibility and voluntary participation constraints, simplify the constraints, and arrive at a convex optimization problem to identify the parameters of the rebate functions. The convex optimization problem has a linear objective function and a continuum of linear constraints. We propose a solution method that involves a finite number of constraints, and identify the number of samples sufficient for a good approximation. We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, which is closely related to Nash bargaining and the competitive equilibrium, is known to be not implementable in a truthful fashion, which has been its main drawback. To alleviate this issue, we propose a new mechanism, which we call the Partial Allocation mechanism, that discards a carefully chosen fraction of the allocated resources in order to incentivize the agents to be truthful in reporting their valuations. This mechanism introduces a way to implement interesting truthful outcomes in settings where monetary payments are not an option. For a multi-dimensional domain with an arbitrary number of agents and items, and for the very large class of homogeneous valuation functions, we prove that our mechanism provides every agent with at least a 1 e ≈ 0.368 fraction of her Proportionally Fair valuation. To the best of our knowledge, this is the first result that gives a constant factor approximation to every agent for the Proportionally Fair solution. To complement this result, we show that no truthful mechanism can guarantee more than 0.5 approximation, even for the restricted class of additive linear valuations. In addition to this, we uncover a connection between the Partial Allocation mechanism and VCG-based mechanism design. We also ask whether better approximation ratios are possible in more restricted settings. In particular, motivated by the massive privatization auction in the Czech republic in the early 90s we provide another mechanism for additive linear valuations that works really well when all the items are highly demanded.