|
on Economic Design |
| By: | Maxwell Allman; Itai Ashlagi; Amin Saberi; Sophie H. Yu |
| Abstract: | In many two-sided labor markets, interviews are conducted before matches are formed. An increase in the number of interviews in the market for medical residencies raised the demand for signaling mechanisms, in which applicants can send a limited number of signals to communicate interest. We study the role of signaling mechanisms in reducing the number of interviews in centralized random matching markets with post-interview shocks. For the market to clear we focus on interim stability, which extends the notion of stability to ensure that agents do not regret not interviewing with each other. A matching is almost interim stable if it is interim stable after removing a vanishingly small fraction of agents. We first study signaling mechanisms in random matching markets when agents on the short side, long side, or both sides signal their top~$d$ preferred partners. Interviews graphs are formed by including all pairs where at least one party has signaled the other. We show that when $d = \omega(1)$, short-side signaling leads to almost interim stable matchings. Long-side signaling is only effective when the market is almost balanced. Conversely, when the interview shocks are negligible and $d = o(\log n)$, both-side signaling fails to achieve almost interim stability. For larger $d \ge \Omega(\log^2 n)$, short-side signaling achieves perfect interim stability, while long-side signaling fails in imbalanced markets. We build on our findings to propose a signaling mechanism for multi-tiered random markets. Our analysis identifies conditions under which signaling mechanisms are incentive compatible. A technical contribution is the analysis of a message-passing algorithm that efficiently determines interim stability and matching outcomes by leveraging local neighborhood structures. |
| Date: | 2025–01 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2501.14159 |
| By: | Sumit Goel; Yuki Tamura |
| Abstract: | We study the classical object reallocation problem under strict preferences, with a focus on characterizing "TTC domains" -- preference domains on which the Top Trading Cycles (TTC) mechanism is the unique mechanism satisfying individual rationality, Pareto efficiency, and strategyproofness. We introduce a sufficient condition for a domain to be a TTC domain, which we call the top-two condition. This condition requires that, within any subset of objects, if two objects can each be most-preferred, they can also be the top-two most-preferred objects (in both possible orders). A weaker version of this condition, applying only to subsets of size three, is shown to be necessary. These results provide a complete characterization of TTC domains for the case of three objects, unify prior studies on specific domains such as single-peaked and single-dipped preferences, and classify several previously unexplored domains as TTC domains or not. |
| Date: | 2025–01 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2501.15422 |
| By: | Takashi Kunimoto; Rene Saran; Roberto Serrano |
| Abstract: | When the normative goals for a set of agents can be summarized in a set-valued rule and agents take actions that are rationalizable, a new theory of incentives emerges in which standard Bayesian incentive compatibility (BIC) is relaxed significantly. The paper studies the interim rationalizable implementation of social choice sets with a Cartesian product structure, a leading example thereof being ex-post efficiency. Setwise incentive compatibility (setwise IC), much weaker than BIC, is shown to be necessary for implementation. Setwise IC enforces incentives flexibly within the entire correspondence, instead of the pointwise enforcement entailed by BIC. Sufficient conditions, while based on the existence of SCFs in the correspondence that make truthful revelation a dominant strategy, are shown to be permissive to allow the implementation of ex-post efficiency in many settings where equilibrium implementation fails (e.g., bilateral trading, multidimensional signals). Furthermore, this success comes at little cost: all our mechanisms are well behaved, in the sense that best responses always exist. |
| Date: | 2025 |
| URL: | https://d.repec.org/n?u=RePEc:bro:econwp:2025-001 |
| By: | Paul Duetting; Michal Feldman; Tomasz Ponitka; Ermis Soumalias |
| Abstract: | Algorithmic contract design studies scenarios where a principal incentivizes an agent to exert effort on her behalf. In this work, we focus on settings where the agent's type is drawn from an unknown distribution, and formalize an offline learning framework for learning near-optimal contracts from sample agent types. A central tool in our analysis is the notion of pseudo-dimension from statistical learning theory. Beyond its role in establishing upper bounds on the sample complexity, pseudo-dimension measures the intrinsic complexity of a class of contracts, offering a new perspective on the tradeoffs between simplicity and optimality in contract design. Our main results provide essentially optimal tradeoffs between pseudo-dimension and representation error (defined as the loss in principal's utility) with respect to linear and bounded contracts. Using these tradeoffs, we derive sample- and time-efficient learning algorithms, and demonstrate their near-optimality by providing almost matching lower bounds on the sample complexity. Conversely, for unbounded contracts, we prove an impossibility result showing that no learning algorithm exists. Finally, we extend our techniques in three important ways. First, we provide refined pseudo-dimension and sample complexity guarantees for the combinatorial actions model, revealing a novel connection between the number of critical values and sample complexity. Second, we extend our results to menus of contracts, showing that their pseudo-dimension scales linearly with the menu size. Third, we adapt our algorithms to the online learning setting, where we show that, a polynomial number of type samples suffice to learn near-optimal bounded contracts. Combined with prior work, this establishes a formal separation between expert advice and bandit feedback for this setting. |
| Date: | 2025–01 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2501.14474 |
| By: | Deniz Kattwinkel; Justus Preusser |
| Abstract: | A surplus must be divided between a principal and an agent. Only the agent knows the surplus' true size and decides how much of it to reveal initially. Both parties can exert costly effort to conclusively prove the surplus' true size. The agent's liability is bounded by the revealed surplus. The principal is equipped with additional funds. The principal designs a mechanism that allocates the burden of proof and divides the surplus. In principal-optimal mechanisms, the principal's effort to acquire proof decreases in the revealed surplus. The agent's effort initially decreases, but then the sign of its slope alternates across five intervals. Applications include wealth taxation, corporate finance, and public procurements. |
| Date: | 2025–01 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2501.14686 |
| By: | Herings, P.J.J. (Tilburg University, Center For Economic Research); Zhou, Yu |
| Keywords: | Roommate problem; taboo equilibrium; expectational equilibrium; equilibria with minimal constraints and maximal permissions; Pareto optimality; stability |
| Date: | 2025 |
| URL: | https://d.repec.org/n?u=RePEc:tiu:tiucen:bf3f5d8c-9cd0-4b5c-89f2-02c2dfe7faf9 |