Mechanism design | EPFL Graph Search

Mechanism design is a field in economics and game theory that takes an objectives-first approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally. Because it starts at the end of the game, then goes backwards, it is also called reverse game theory. It has broad applications, from economics and politics in such fields as market design, auction theory and social choice theory to networked-systems (internet interdomain routing, sponsored search auctions). Mechanism design studies solution concepts for a class of private-information games. Leonid Hurwicz explains that 'in a design problem, the goal function is the main "given", while the mechanism is the unknown. Therefore, the design problem is the "inverse" of traditional economic theory, which is typically devoted to the analysis of the performance of a given mechanism.' So, two distinguishing features of these games are:

that a game "designer" chooses t

Rectilinear translation four-bar flexure mechanism based on four Remote Center Compliance pivots

Charles Baur, Quentin Gubler, Simon Nessim Henein, Hubert Pierre-Marie Benoît Schneegans, Loïc Benoît Tissot-Daguette

This paper presents a novel planar four-bar linkage compliant mechanism (called 4-RCC) based on four flexure-based Remote Center of Compliance (RCC) pivots. With particular configurations and dimensions, the beam shortening of the RCC pivots can compensate the parasitic shift of the four-bar linkage over its range of motion, thereby creating a rectilinear translation mechanism. Moreover, to decrease the stiffness in the direction of the desired translation, while keeping the same magnitude of the transversal stiffnesses, a fixed-guided buckled beam with constant negative stiffness is added in parallel. This stiffness compensation greatly decreases the force to actuate the stage. This paper derives the analytical conditions required to compensate both the parasitic shift and the stiffness of the 4-RCC mechanism. A mesoscale mockup model is designed, aiming for a millimeter-scale stroke, a compensated parasitic shift and a near-zero stiffness. A finite element model (FEM) validates the mechanism design and the analytical model. Simulation results show that the design leads to a parasitic shift below 65.6 nm over a displacement range of 8 mm, and the required actuation force is reduced by 95% when the buckled beam is added. Furthermore, the residual straightness error can be minimized by advantageously adjusting the preload of the buckled beam.

euspen2022

M-DPOP: Faithful distributed implementation of efficient social choice problems

Boi Faltings, David C. Parkes, Adrian Petcu

In the efficient social choice problem, the goal is to assign values, subject to side constraints, to a set of variables to maximize the total utility across a population of agents, where each agent has private information about its utility function. In this paper we model the social choice problem as a distributed constraint optimization problem (DCOP), in which each agent can communicate with other agents that share an interest in one or more variables. Whereas existing DCOP algorithms can be easily manipulated by an agent, either by misreporting private information or deviating from the algorithm, we introduce M-DPOP, the first DCOP algorithm that provides a faithful distributed implementation for efficient social choice. This provides a concrete example of how the methods of mechanism design can be unified with those of distributed optimization. Faithfulness ensures that no agent can benefit by unilaterally deviating from any aspect of the protocol, neither information-revelation, computation, nor communication, and whatever the private information of other agents. We allow for payments by agents to a central bank, which is the only central authority that we require. To achieve faithfulness, we carefully integrate the Vickrey-Clarke-Groves (VCG) mechanism with the DPOP algorithm, such that each agent is only asked to perform computation, report information, and send messages that is in its own best interest. Determining agent i's payment requires solving the social choice problem without agent i. Here, we present a method to reuse computation performed in solving the main problem in a way that is robust against manipulation by the excluded agent. Experimental results on structured problems show that as much as 87% of the computation required for solving the marginal problems can be avoided by re-use, providing very good scalability in the number of agents. On unstructured problems, we observe a sensitivity of M-DPOP to the density of the problem, and we show that reusability decreases from almost 100% for very sparse problems to around 20% for highly connected problems. We close with a discussion of the features of DCOP that enable faithful implementations in this problem, the challenge of reusing computation from the main problem to marginal problems in other algorithms such as ADOPT and OptAPO, and the prospect of methods to avoid the welfare loss that can occur because of the transfer of payments to the bank.

2008

M-DPOP: Faithful distributed implementation of efficient social choice problems

Boi Faltings, David C. Parkes, Adrian Petcu

2008