Source author record

Martin Bichler

Martin Bichler appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computer Science and Game Theory Artificial Intelligence Data Structures and Algorithms econ.TH

Catalog footprint

What is connected

5works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

Distributionally Robust Contract Design with Deferred Inspection

We study a robust contract design problem with deferred inspection, in which a principal allocates a scarce resource to an agent, observes the agent's realized outcome ex post at negligible cost, and conditions transfers on this information through rewards. The principal faces ambiguity about the agent's value distribution and seeks to maximize worst-case expected revenue subject to incentive compatibility and limited liability. In contrast to existing work on inspection mechanisms, which relies on common-prior assumptions, we adopt a distributionally robust approach based on moment information. Our main contribution is a complete characterization of the robust contract design problem with a single agent. When the ambiguity set is defined by the first moment, we identify a robustly optimal contract with a concave allocation rule and a linear payment rule. We further show that robustness does not uniquely pin down transfers: we construct a Pareto robustly optimal contract that preserves the same allocation while extracting maximal feasible payments from all types, yielding strictly higher expected revenue under non-worst-case distributions. We also derive structural results for multi-agent extensions. For ambiguity sets defined by the first $N$ moments, we show that robust optimality requires aggregate payments to be lower bounded by a multi-dimensional polynomial of degree $N$. However, unlike the single-agent case, robust multi-agent mechanisms are substantially more complex: dominant-strategy incentive compatibility becomes necessary, simple monotone mechanisms are no longer tractable, and worst-case distributions may involve correlated types or degenerate to a Dirac distribution at the mean. These results highlight a sharp contrast between robust contract design and robust multi-agent mechanism design with inspection.

preprint2021arXiv

Equilibrium Learning in Combinatorial Auctions: Computing Approximate Bayesian Nash Equilibria via Pseudogradient Dynamics

Applications of combinatorial auctions (CA) as market mechanisms are prevalent in practice, yet their Bayesian Nash equilibria (BNE) remain poorly understood. Analytical solutions are known only for a few cases where the problem can be reformulated as a tractable partial differential equation (PDE). In the general case, finding BNE is known to be computationally hard. Previous work on numerical computation of BNE in auctions has relied either on solving such PDEs explicitly, calculating pointwise best-responses in strategy space, or iteratively solving restricted subgames. In this study, we present a generic yet scalable alternative multi-agent equilibrium learning method that represents strategies as neural networks and applies policy iteration based on gradient dynamics in self-play. Most auctions are ex-post nondifferentiable, so gradients may be unavailable or misleading, and we rely on suitable pseudogradient estimates instead. Although it is well-known that gradient dynamics cannot guarantee convergence to NE in general, we observe fast and robust convergence to approximate BNE in a wide variety of auctions and present a sufficient condition for convergence

preprint2016arXiv

A Truthful Mechanism for the Generalized Assignment Problem

We propose a truthful-in-expectation, $(1-1/e)$-approximation mechanism for a strategic variant of the generalized assignment problem (GAP). In GAP, a set of items has to be optimally assigned to a set of bins without exceeding the capacity of any singular bin. In the strategic variant of the problem we study, values for assigning items to bins are the private information of bidders and the mechanism should provide bidders with incentives to truthfully report their values. The approximation ratio of the mechanism is a significant improvement over the approximation ratio of the existing truthful mechanism for GAP. The proposed mechanism comprises a novel convex optimization program as the allocation rule as well as an appropriate payment rule. To implement the convex program in polynomial time, we propose a fractional local search algorithm which approximates the optimal solution within an arbitrarily small error leading to an approximately truthful-in-expectation mechanism. The presented algorithm improves upon the existing optimization algorithms for GAP in terms of simplicity and runtime while the approximation ratio closely matches the best approximation ratio given for GAP when all inputs are publicly known.

preprint2016arXiv

Truthfulness with Value-Maximizing Bidders

In markets such as digital advertising auctions, bidders want to maximize value rather than payoff. This is different to the utility functions typically assumed in auction theory and leads to different strategies and outcomes. We refer to bidders who maximize value as value bidders. While simple single-object auction formats are truthful, standard multi-object auction formats allow for manipulation. It is straightforward to show that there cannot be a truthful and revenue-maximizing deterministic auction mechanism with value bidders and general valuations. Approximation has been used as a means to achieve truthfulness, and we study which approximation ratios we can get from truthful approximation mechanisms. We show that the approximation ratio that can be achieved with a deterministic and truthful approximation mechanism with $n$ bidders and $m$ items cannot be higher than 1/n for general valuations. For randomized approximation mechanisms there is a framework with a ratio of O(sqrt(m)). We provide better ratios for environments with restricted valuations.

preprint2014arXiv

Fast Convex Decomposition for Truthful Social Welfare Approximation

Approximating the optimal social welfare while preserving truthfulness is a well studied problem in algorithmic mechanism design. Assuming that the social welfare of a given mechanism design problem can be optimized by an integer program whose integrality gap is at most $α$, Lavi and Swamy~\cite{Lavi11} propose a general approach to designing a randomized $α$-approximation mechanism which is truthful in expectation. Their method is based on decomposing an optimal solution for the relaxed linear program into a convex combination of integer solutions. Unfortunately, Lavi and Swamy's decomposition technique relies heavily on the ellipsoid method, which is notorious for its poor practical performance. To overcome this problem, we present an alternative decomposition technique which yields an $α(1 + ε)$ approximation and only requires a quadratic number of calls to an integrality gap verifier.