Workshop Details

We consider a model of tract housing where buyers and sellers have (i) wealth constraints, and (ii) unit demand over identical indivisible objects represented by a valuation. First, we characterize the strong core. Second, we characterize the bilateral weak core, or the weak core allocations with no side-payments. Finally, when buyer wealth constraints and valuations are private information and when transfers are discrete, we introduce two families of pendulum auctions, both of which consist of obviously strategy-proof implementations of the bilateral weak core. The buyer-optimal pendulum auctions are preferred by the buyers but are inefficient when side-payments are possible, while the efficient pendulum auctions are efficient.

We explore the approximation power of deterministic obviously strategy-proof mechanisms in auctions, where the objective is welfare maximization. A trivial ascending auction on the grand bundle guarantees an approximation of min{m,n} for all valuation classes, where m is the number of items and n is the number of bidders. We focus on two classes of valuations considered “simple”: additive valuations and unit-demand valuations. For additive valuations, Bade and Gonczarowski [EC'17] have shown that exact welfare maximization is impossible. No impossibilities are known for unit-demand valuations.

We show that if bidders' valuations are additive or unit-demand, then no obviously strategy-proof mechanism gives an approximation better than min{m,n}. Thus, the aforementioned trivial ascending auction on the grand bundle is the optimal obviously strategy-proof mechanism. This illustrates a stark separation between the power of dominant-strategy and obviously strategy-proof mechanisms because for both of these classes, the dominant-strategy VCG mechanism not only optimizes the welfare exactly but is also "easy" from both a computation and communication perspective. We provide additional tight impossibility results for single-minded bidders in multi-unit auctions and combinatorial auctions.

Catering to the incentives of people with imperfect rationality requires novel paradigms in designing mechanisms and approximation algorithms. In this context, the contingent reasoning skills (or lack thereof) of agents interacting with the mechanism have emerged as a pivot to relax or strengthen the classical notion of strategyproofness. In this talk, we will discuss incentive compatibility notions in this landscape. We will focus on algorithms that can be augmented by suitable payment schemes to engineer the incentives of agents with imperfect rationality.

We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each seller's true cost for providing their service. These solutions predominantly take the form of randomized sealed-bid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways.

First, our solutions take the form of descending clock auctions, and thus satisfy a list of properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyer's valuation function is submodular over the set of services. In addition, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior work.

We propose a measure of strategic complexity for a class of strategy-proof mechanisms, which includes all strategy-proof mechanisms used in practice. Our rankings are consistent with the coarser ones implied by the solution concepts of (strong) obvious strategy-proofness (Li, 2017, Pycia and Troyan, 2023). The added flexibility of our approach allows a designer to balance a mechanism’s simplicity with other objectives. Our measure characterizes the Ausubel (2004) auction as the simplest way to implement the VCG outcome in multi-unit allocation problems with transfers, and provides novel rankings of mechanisms that implement stable outcomes in matching problems. Finally, we characterize minimally complex mechanisms for a range of settings, and formalize the intuition that some mechanisms are as simple as if they were (strongly) obviously strategy-proof. We explain how this extension can be valuable for high-stakes applications such as the FCC incentive auction.

This paper gives a theoretical model for design and analysis of mechanisms for online marketplaces where a bidding dashboard enables the bid-optimization of long-lived agents. We assume that a good allocation algorithm exists when given the true values of the agents and we develop online winner-pays-bid and all-pay mechanisms that implement the same outcome of the algorithm with the aid of a bidding dashboard. The bidding dashboards that we develop work in conjunction with the mechanism to guarantee that bidding according to the dashboard is strategically equivalent (with vanishing utility difference) to bidding truthfully in the sequential truthful implementation of the allocation algorithm. Our dashboard mechanism makes only a single call to the allocation algorithm in each stage.

List of Posters:

Optimal Matching With Multi-Dimensional Preferences, Irene Aldridge

Proximity-Based Optimal Committee Selection Mechanism, Ruth Ben-Yashar

From Independence of Clones to Composition Consistency: A Hierarchy of Barriers to Strategic Nomination, Ratip Emin Berker

Post-Match Error Mitigation for Deferred Acceptance, Abraham Gale

The Art of Two-round Voting, Qishen Han

Behavioral Study of Dashboard Mechanisms, Paula Kayongo

Computationally Simple Mechanisms, Andrew Komo

Mechanisms for Settings with Correlated Events, Chun Lau

When is it fair to assign goods sequentially? Dorsa Majdi

A Collusion-Proof Efficient Dynamic Mechanism, Alexander Rodivilov

The Power of Static Pricing for Reusable Resources, Jiaqi Shi

Clock Auctions Augmented with Unreliable Advice, Xizhi Tan

Randomized Truthful Auctions with Learning Agents, Grigoris Velegkas

Eliciting Informative Text Evaluations with Large Language Models,  Shengwei Xu

Multi-task Peer Prediction with Task-dependent Strategy, Yichi Zhang

Strategyproof Empirical Risk Minimization, Cherlin Zhu

Poster Session Abstracts

We show that achieving dominant strategy incentive compatibility often requires to choose a mechanism which severely limits what agents can observe about others’ previous moves. However, experiments and theoretical arguments suggest increasing the transparency of a mechanism’s extensive form can improve reliability of its predictions—even if it breaks the dominant strategy property.

To help resolve this dilemma, we define as-if dominant strategy mechanisms: (i) Each agent has at least one strategy that becomes dominant if the others were restricted to behave as if the mechanism was static, and (ii) all combinations of such strategies are ex-post equilibria. To behavioral agents who neglect that others may condition their behavior in sophisticated ways, the incentives of these mechanisms resemble those of a dominant strategy one.

Our framework rationalizes the auction format chosen by prominent online platforms, such as eBay. It also provides a unified explanation for experimental evidence in various settings. Further, we identify simple conditions under which as-if dominant strategy mechanisms are weak dominance solvable.

We conduct an incentivized lab experiment to test participants' ability to understand the DA matching mechanism and the strategyproofness property, conveyed in different ways. We find that while many participants can (using a novel GUI) learn DA's mechanics and calculate its outcomes, such understanding does not imply understanding of strategyproofness (as measured by specially designed tests). However, a novel menu description of strategyproofness conveys this property significantly better than other treatments. While behavioral effects are small on average, participants with levels of strategyproofness understanding above a certain threshold play the classical dominant strategy at very high rates.

We investigate whether preferences for objects received via a matching mechanism are influenced by how highly agents rank them in their reported rank order list. We hypothesize that all else equal, agents receive greater utility for the same object when they rank it higher. The addition of rankings-dependent utility implies that it may not be a dominant strategy to submit truthful preferences to a strategyproof mechanism, and that non-strategyproof mechanisms that give more agents objects they report as higher ranked may increase market welfare. We test these hypotheses with a matching experiment in a strategyproof mechanism, the random serial dictatorship, and a non-strategyproof mechanism, the Boston mechanism. A novel feature of our experimental design is that the objects allocated in the matching markets are real goods, which allows us to directly measure rankings-dependence by eliciting values for goods both inside and outside of the mechanism. The experimental results are mixed, with stronger evidence for rankings-dependence in the RSD treatment than the Boston treatment. We find no differences between the two mechanisms for the rates of truth-telling and the final welfare.