While the classic Vickrey-Clarke-Groves mechanism ensures incentive compatibility for a static one-shot game, it does not appear to be feasible to construct a dominant truth-telling mechanism for agents that are stochastic dynamic systems. The contribution of this paper is to show that for a set of LQG agents a mechanism consisting of a sequence of layered payments over time decouples the intertemporal effect of current bids on future payoffs and ensures truth-telling of dynamic states by their agents, if system parameters are known and agents are rational. Additionally, it is shown that there is a "Scaled" VCG mechanism that simultaneously satisfies incentive compatibility, social efficiency, budget balance as well as individual rationality under a certain "market power balance" condition where no agent is too negligible or too dominant. A further desirable property is that the SVCG payments converge to the Lagrange payments, the payments corresponding to the true price in the absence of strategic considerations, as the number of agents in the market increases. For LQ but non-Gaussian agents the optimal social welfare over the class of linear control laws is achieved.
A preliminary announcement of some of these results was presented in the conference paper @cite_19 . The layered payment structure for LQG systems is mentioned there, and incentive compatibility results are presented without proofs. The present paper contains the complete proof of incentive compatibility, and further introduces the Scaled VCG mechanism for budget balance, individual rationality, and Lagrange optimality.
@cite_19
2963829287 2084685902 2046744707 2953389549
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. 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. In a STACS 2003 paper, Talwar analyzes the overpayment the VCG mechanism incurs for ensuring truthfulness in auctions. Among other results, he studies k-Set Cover (given a universe U and a collection of sets S 1 , S 2 , ? , S m , each having a cost c ( S i ) and at most k elements of U, find a minimum cost subcollection - a cover - whose union equals U) and shows that the payment of the VCG mechanism is at most k ? c ( OPT ' ) , where OPT ' is the best cover disjoint from the optimum cover OPT . The VCG mechanism requires finding an optimum cover. For k ? 3 , k-Set Cover is known to be NP-hard, and thus truthful mechanisms based on approximation algorithms are desirable. We show that the payment incurred by two mechanisms based on approximation algorithms (including the Greedy algorithm) is bounded by ( k - 1 ) c ( OPT ) + k ? c ( OPT ' ) . The same approximation algorithms have payment bounded by k ( c ( OPT ) + c ( OPT ' ) ) when applied to more general set systems, which include k-Polymatroid Cover, a problem related to Steiner Tree computations. If q is such that an element in a k-Set Cover instance appears in at most q sets, we show that the total payment based on our algorithms is bounded by q ? k 2 times the total payment of the VCG mechanism. The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions the truthful direct-revelation mechanism that maximizes social welfare is the VCG mechanism. For many valuation spaces computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that the welfare loss increases in expressiveness. All our bounds apply to equilibrium concepts that can be computed in polynomial time as well as to learning outcomes.