Strategyproofness has been the holy grail in mechanism design for decades, providing strong incentive compatibility guarantees under the assumption of perfectly rational agents. However, this assumption is questionable when agents exhibit bounded rationality. Moreover, strategyproofness often imposes strong impossibility results that prevent mechanisms from surpassing certain approximation barriers. We study this tension in budget-feasible mechanism design, where a designer wants to procure services of maximum value from agents subject to a budget constraint. Here, strategyproofness imposes approximation barriers of 2.41 and 2 for deterministic and randomized mechanisms, respectively. We investigate how much we can potentially gain under bounded rationality. We adopt the weaker notion of not obviously manipulable (NOM), which only prevents "obvious" strategic deviations. We fully resolve the achievable approximation guarantees under NOM: We derive a deterministic 2-approximate NOM mechanism under the general class of monotone subadditive valuations. We also show that this bound is tight (even for additive valuations). Additionally, we provide a simple randomized NOM mechanism that is approximately optimal. These results demonstrate a clear separation between strategyproof and NOM mechanisms. Our mechanisms use Golden Tickets and Wooden Spoons as natural design primitives, arising from our characterization of NOM mechanisms.

Online advertising systems have recently transitioned to autobidding, allowing advertisers to delegate bidding decisions to automated agents. Each advertiser directs their agent to optimize an objective function subject to return-on-investment (ROI) and budget constraints. Given their practical relevance, this shift has spurred a surge of research on the liquid welfare price of anarchy (POA) of fundamental auction formats under autobidding, most notably simultaneous first-price auctions (FPA). One of the main challenges is to understand the efficiency of FPA in the presence of heterogeneous agent types. We introduce a type-dependent smoothness framework that enables a unified analysis of the POA in such complex autobidding environments. In our approach, we derive type-dependent smoothness parameters which we carefully balance to obtain POA bounds. This balancing gives rise to a POA-revealing mathematical program, which we use to determine tight bounds on the POA of coarse correlated equilibria (CCE). Our framework is versatile enough to handle heterogeneous agent types and extends to the general class of fractionally subadditive valuations. Additionally, we develop a novel reduction technique that transforms budget-constrained agents into budget-unconstrained ones. Combining this reduction technique with our smoothness framework enables us to derive tight bounds on the POA of CCE in the general hybrid agent model with both ROI and budget constraints. Among other results, our bounds uncover an intriguing threshold phenomenon showing that the POA depends intricately on the smallest and largest agent types. We also extend our study to FPAs with reserve prices, which can be interpreted as predictions of agents’ values, to further improve efficiency guarantees.

The realm of algorithms with predictions has led to the development of several new algorithms that leverage predictions to enhance their performance guarantees. The challenge is to devise algorithms that achieve optimal approximation guarantees as the prediction quality varies from perfect (consistency) to imperfect (robustness). This framework is particularly appealing in mechanism design contexts, where predictions might convey private information about the agents. In this paper, we design strategyproof mechanisms that leverage predictions to achieve improved approximation guarantees for several variants of the Generalized Assignment Problem (GAP) in the private graph model. In this model, first introduced by Dughmi & Ghosh (2010), the set of resources that an agent is compatible with is private information. For the Bipartite Matching Problem (BMP), we give a deterministic group-strategyproof (GSP) mechanism that is (1 + 1/γ)-consistent and (1 + γ)-robust, where γ ≥ 1 is some confidence parameter. We also prove that this is best possible. Remarkably, our mechanism draws inspiration from the renowned Gale-Shapley algorithm, incorporating predictions as a crucial element. Additionally, we give a randomized mechanism that is universally GSP and improves on the guarantees in expectation. The other GAP variants that we consider all make use of a unified greedy mechanism that adds edges to the assignment according to a specific order. For a special case of Restricted Multiple Knapsack, this results in a deterministic strategyproof mechanism that is (1 + 1/γ)-consistent and (2 + γ)-robust. We then focus on two variants: Agent Size GAP (where each agent has one size) and Value Consensus GAP (where all agents have the same preference order over resources). For both variants, our universally GSP mechanisms randomize over the greedy mechanism, our mechanism for BMP and the predicted assignment, leading to (1 + 3/γ)-consistency and (3 + γ)-robustness in expectation. All our mechanisms also provide more fine-grained approximation guarantees that interpolate between the consistency and robustness guarantees, depending on some natural error measure of the prediction.