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.
There are also some related works aiming at achieving budget balance for VCG mechanism. @cite_18 discusses the trade-off between budget balance and efficiency of the mechanism. Cavallo @cite_16 uses domain information regarding agent valuation spaces to achieve redistribution of much of the required transfer payments back among the agents. Similarly, @cite_6 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. In @cite_20 , an enhanced (Arrow-d’Aspremont-Gerard-Varet) AGV mechanism is proposed to tackle the problem of budget balance in demand side management.
@cite_18 @cite_16 @cite_20 @cite_6
2056062533 2084685902 2541696016 203000141
Mechanisms for coordinating group decision-making among self-interested agents often employ a trusted center, capable of enforcing the prescribed outcome. Typically such mechanisms, including the ubiquitous Vickrey Clarke Groves (VCG), require significant transfer payments from agents to the center. While this is sought after in some settings, it is often an unwanted cost of implementation. We propose a modification of the VCG framework that---by using domain information regarding agent valuation spaces---is often able to achieve redistribution of much of the required transfer payments back among the agents, thus coming closer to budget-balance. The proposed mechanism is strategyproof, ex post individual rational, no-deficit, and leads to an efficient outcome; we prove that among all mechanisms with these qualities and an anonymity property it is optimally balanced, in that no mechanism ever yields greater payoff to the agents. We provide a general characterization of when strategyproof redistribution is possible, and demonstrate specifically that substantial redistribution can be achieved in allocation problems. 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. 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. The VCG mechanism is the gold standard for combinatorial auctions (CAs), and it maximizes social welfare. In contrast, the revenue-maximizing (aka optimal) CA is unknown, and designing one is NP-hard. Therefore, research on optimal CAs has progressed into special settings. Notably, Levin [1997] derived the optimal CA for complements when each agent's private type is one-dimensional. (This does not fall inside the well-studied "single-parameter environment".) We introduce a new research avenue for increasing revenue where we poke holes in the allocation space--based on the bids--and then use a welfare-maximizing allocation rule within the remaining allocation set. In this paper, the first step down this avenue, we introduce a new form of "reserve pricing" into CAs. We show that Levin's optimal revenue can be 2-approximated by using "monopoly reserve prices" to curtail the allocation set, followed by welfare-maximizing allocation and Levin's payment rule. A key lemma of potential independent interest is that the expected revenue from any truthful allocation-monotonic mechanism equals the expected virtual valuation; this generalizes Myerson's lemma [1981] from the single-parameter environment. Our mechanism is close to the gold standard and thus easier to adopt than Levin's. It also requires less information about the prior over the bidders' types, and is always more efficient. Finally, we show that the optimal revenue can be 6- approximated even if the "reserve pricing" is required to be symmetric across bidders.