BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Paul Dütting

Paul Dütting contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computer Science and Game TheoryData Structures and AlgorithmsMachine Learning

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

6 published item(s)

preprint2026arXiv

Profit Maximization in Bilateral Trade against a Smooth Adversary

Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, who wish to trade a good. We study this problem from the perspective of a profit-maximizing broker within an online learning framework, where the agents' valuations are generated by a smooth adversary. We devise a learning algorithm that guarantees a $\tilde{O}(\sqrt{T})$ regret bound, which is tight in the time horizon $T$ up to poly-logarithmic factors. This matches the minimax rate for the stochastic i.i.d. case, and is also well separated from the adversarial setting, where sublinear-regret is unattainable. By extending the strong regret guarantees from the i.i.d. case to the smooth adversary, we significantly broaden the scope of settings where such fast rate is achievable, while closing an important gap in the regret landscape of this fundamental economic problem. To overcome the challenges posed by this adversary, we leverage a continuity property of smooth instances and combines this with a hierarchical net-construction of the broker's action space, which is analyzed via algorithmic chaining. We showcase the applicability of these techniques by deriving a similarly tight $\tilde{O}(\sqrt{T})$ regret bound for a related mechanism design model: the joint ads problem.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Price Manipulability in First-Price Auctions

First-price auctions have many desirable properties, including uniquely possessing some, like credibility. However, first-price auctions are also inherently non-truthful, and non-truthfulness may result in instability and inefficiencies. Given these pros and cons, we seek to quantify the extent to which first-price auctions are susceptible to manipulation. In this work we adopt a metric that was introduced in the context of bitcoin fee design markets: the percentage change in payment that can be achieved by being strategic. We study the behavior of this metric for single-unit and $k$-unit auction environments with $n$ i.i.d. buyers, and seek conditions under which the percentage change tends to zero as $n$ grows large. To the best of our knowledge, ours is the first rigorous study of the extent to which large multi-unit first price auctions are susceptible to manipulation. We provide an almost complete picture of the conditions under which they are truthful in the large, and exhibit some surprising boundaries.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions

Prophet inequalities compare the expected performance of an online algorithm for a stochastic optimization problem to the expected optimal solution in hindsight. They are a major alternative to classic worst-case competitive analysis, of particular importance in the design and analysis of simple (posted-price) incentive compatible mechanisms with provable approximation guarantees. A central open problem in this area concerns subadditive combinatorial auctions. Here $n$ agents with subadditive valuation functions compete for the assignment of $m$ items. The goal is to find an allocation of the items that maximizes the total value of the assignment. The question is whether there exists a prophet inequality for this problem that significantly beats the best known approximation factor of $O(\log m)$. We make major progress on this question by providing an $O(\log \log m)$ prophet inequality. Our proof goes through a novel primal-dual approach. It is also constructive, resulting in an online policy that takes the form of static and anonymous item prices that can be computed in polynomial time given appropriate query access to the valuations. As an application of our approach, we construct a simple and incentive compatible mechanism based on posted prices that achieves an $O(\log \log m)$ approximation to the optimal revenue for subadditive valuations under an item-independence assumption.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Simple versus Optimal Contracts

We consider the classic principal-agent model of contract theory, in which a principal designs an outcome-dependent compensation scheme to incentivize an agent to take a costly and unobservable action. When all of the model parameters---including the full distribution over principal rewards resulting from each agent action---are known to the designer, an optimal contract can in principle be computed by linear programming. In addition to their demanding informational requirements, such optimal contracts are often complex and unintuitive, and do not resemble contracts used in practice. This paper examines contract theory through the theoretical computer science lens, with the goal of developing novel theory to explain and justify the prevalence of relatively simple contracts, such as linear (pure commission) contracts. First, we consider the case where the principal knows only the first moment of each action's reward distribution, and we prove that linear contracts are guaranteed to be worst-case optimal, ranging over all reward distributions consistent with the given moments. Second, we study linear contracts from a worst-case approximation perspective, and prove several tight parameterized approximation bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Sponsored Search, Market Equilibria, and the Hungarian Method

Matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market. Here, as in other markets of that kind, market equilibria correspond to feasible, envy free, and bidder optimal outcomes. For settings without budgets such an outcome always exists and can be computed in polynomial-time by the so-called Hungarian Method. Moreover, every mechanism that computes such an outcome is incentive compatible. We show that the Hungarian Method can be modified so that it finds a feasible, envy free, and bidder optimal outcome for settings with budgets. We also show that in settings with budgets no mechanism that computes such an outcome can be incentive compatible for all inputs. For inputs in general position, however, the presented mechanism---as any other mechanism that computes such an outcome for settings with budgets---is incentive compatible.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Simplicity-Expressiveness Tradeoffs in Mechanism Design

A fundamental result in mechanism design theory, the so-called revelation principle, asserts that for many questions concerning the existence of mechanisms with a given outcome one can restrict attention to truthful direct revelation-mechanisms. In practice, however, many mechanism use a restricted message space. This motivates the study of the tradeoffs involved in choosing simplified mechanisms, which can sometimes bring benefits in precluding bad or promoting good equilibria, and other times impose costs on welfare and revenue. We study the simplicity-expressiveness tradeoff in two representative settings, sponsored search auctions and combinatorial auctions, each being a canonical example for complete information and incomplete information analysis, respectively. We observe that the amount of information available to the agents plays an important role for the tradeoff between simplicity and expressiveness.

0 citations0 reviewsNo code linkedOpen access