Mechanism Design
In many applications, it is necessary to coordinate selfish agents in order to determine a global solution. This includes the competition for resources in which requests have to be processed in order to determine feasible resource allocations as well as scenarios in which agents are part of a system that should be optimized in a certain way.
Mechanism design offers formalisms to describe the above setting. Mechanisms simply demand an input parameter from each agent and with this data, compute a commonly known outcome function. In resource allocation, the input parameter of an agent may be modeled as the monetary valuation of being assigned a resource. In system optimization, the input parameter is a system parameter, i.e., the parameter of an agent that represent a network link or a CPU may be modeled as his speed.
Typically, an agent's valuation is private information. Therefore, a major goal in mechanism design is to create incentives for truth-telling which is achieved through payments. An even stronger aim is to prevent manipulative cooperation. Other objectives are to recover the allocation cost by these payments and to achieve a collective satisfaction by allocating resources to agents with maximum valutions.
Since theses objectives are in conflict with each other, different mechanisms provide different guarantees. There are two main approaches. The first is to auction off combinations of resources by VCG mechanisms that meet the above objectives except that there are no guarantees about cost-recovery. Furthermore, they are vulnerable if competitors cooperate with each other and jointly submit false valuations. The second approach is to use Moulin mechanisms, that prevent this manipulation but may only approximately achieve the other objectives.
Our Main Focus
We mainly focus on the problem of cost-sharing, in which a service provider offers a service to a set of agents. Given the agents' bids indicating what they are willing to pay for the service, the service provider has to decide on the set of served agents and their payments. We are interested in general possibility and impossibility results on which objectives can be achieved at the same time. Furthermore, we particularly consider the scenario, in which the service provider owns a set of parallel machines and the service corresponds to process agents' jobs.Contact
Yvonne Bleischwitz (yvonneb@upb.de)Florian Schoppmann (fschopp@upb.de)
Index A – Z | Impressum | Webmaster | Modified: 10.05.2007