Invited Session Mon.3.MA 043

Monday, 15:15 - 16:45 h, Room: MA 043

Cluster 8: Game theory [...]

Design of optimal mechanisms


Chair: Rudolf Müller



Monday, 15:15 - 15:40 h, Room: MA 043, Talk 1

Maria Polukarov
Optimal payments in dominant-strategy mechanisms for single-parameter domains

Coauthors: Nicholas R. Jennings, Victor Naroditskiy


We study dominant-strategy mechanisms in allocation domains where agents have one-dimensional types and quasi-linear utilities. Taking an allocation function as an input, we present an algorithmic technique for finding optimal payments in a class of mechanism design problems, including utilitarian and egalitarian allocation of homogeneous items with nondecreasing marginal costs.
Our results link optimality of payment functions to a geometric condition involving triangulations of polytopes. When this condition is satisfied, we constructively show the existence of an optimal payment function that is piecewise linear in agent types.



Monday, 15:45 - 16:10 h, Room: MA 043, Talk 2

Mingyu Guo
Computationally feasible automated mechanism design: General approach and a case study on budget-balanced and nearly efficient randomized mechanisms

Coauthors: Vincent Conitzer, Amy Greenwald, Nicholas Jennings, Victor Naroditskiy


In automated mechanism design, the idea is to computationally search through the space of feasible mechanisms, rather than to design them analytically by hand. Unfortunately, the most straightforward approach to automated mechanism design does not scale to large instances, because it requires searching over a very large space of possible functions. We describe an approach to automated mechanism design that is computationally feasible. Instead of optimizing over all feasible mechanisms, we carefully choose a parameterized subfamily of mechanisms. Then we optimize over mechanisms within this family, and analyze whether and to what extent the resulting mechanism is suboptimal outside the subfamily.
We demonstrate the usefulness of our approach with a case study on budget-balanced and nearly efficient mechanisms. Faltings [05] proposed the idea of excluding one agent uniformly at random from the decision and making him the residual claimant. We show that Faltings' mechanism can be generalized to a parameterized subfamily of mechanisms. In two example scenarios, by optimizing within the above subfamily, we are able to find mechanisms that are budget-balanced and nearly efficient.



Monday, 16:15 - 16:40 h, Room: MA 043, Talk 3

Konrad Mierendorff
Generalized reduced-form auctions: A network-flow approach

Coauthors: Yeon-Koo Che, Jinwoo Kim


We develop a network-flow approach for characterizing interim-allocation rules that can be implemented by ex post allocations. The network method can be used to characterize feasible interim allocations in general multi-unit auctions where agents face hierarchical capacity constraints. We apply the method to solve for an optimal multi-object auction mechanism when bidders are constrained in their capacities and budgets.


  online loans . What can cause long-term use of Canadian Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.