Search

Transaction Fee Mechanism Design studies auctions run by untrusted miners for transaction inclusion in a blockchain. Under previously-considered desiderata, an auction is considered `good' if, informally-speaking, each party (i.e., the miner, the users, and coalitions of both miners and users) has no incentive to deviate from the fixed and pre-determined protocol. In this paper, we propose a novel desideratum for transaction fee mechanisms. We say that a TFM is off-chain influence proof when the miner cannot achieve additional revenue by running a separate auction off-chain. While the previously-highlighted EIP-1559 is the gold-standard according to prior desiderata, we show that it does not satisfy off-chain influence proofness. Intuitively, this holds because a Bayesian revenue-maximizing miner can strictly increase profits by persuasively threatening to censor any bids that do not transfer a tip directly to the miner off-chain. On the other hand, we reconsider the Cryptographic (multi-party computation assisted) Second Price Auction mechanism, which is technically not `simple for miners' according to previous desiderata (since miners may wish to set a reserve by fabricating bids). We show that, in a slightly different model where the miner is allowed to set the reserve directly, this auction satisfies simplicity for users and miners, and off-chain influence proofness. Finally, we prove a strong impossibility result: no mechanism satisfies all previously-considered properties along with off-chain influence proofness, even with unlimited supply, and even after soliciting input from the miner.

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 study the communication complexity of truthful combinatorial auctions, and in particular the case where valuations are either subadditive or single-minded, which we denote with $\mathsf{SubAdd}\cup\mathsf{SingleM}$. We show that for three bidders with valuations in $\mathsf{SubAdd}\cup\mathsf{SingleM}$, any deterministic truthful mechanism that achieves at least a $0.366$-approximation requires $\exp(m)$ communication. In contrast, a natural extension of [Fei09] yields a non-truthful $\mathrm{poly}(m)$-communication protocol that achieves a $\frac{1}{2}$-approximation, demonstrating a gap between the power of truthful mechanisms and non-truthful protocols for this problem. Our approach follows the taxation complexity framework laid out in [Dob16b], but applies this framework in a setting not encompassed by the techniques used in past work. In particular, the only successful prior application of this framework uses a reduction to simultaneous protocols which only applies for two bidders [AKSW20], whereas our three-player lower bounds are stronger than what can possibly arise from a two-player construction (since a trivial truthful auction guarantees a $\frac{1}{2}$-approximation for two players).

Stable matchings are a cornerstone of market design, with numerous practical deployments backed by a rich, theoretically-tractable structure. However, in school-choice problems, stable matchings are not Pareto optimal for the students. Priority-neutral matchings, introduced by Reny (AER, 2022), generalizes the set of stable matchings by allowing for certain priority violations, and there is always a Pareto optimal priority-neutral matching. Moreover, like stable matchings, the set of priority-neutral matchings forms a lattice. We study the structure of the priority-neutral lattice. Unfortunately, we show that much of the simplicity of the stable matching lattice does not hold for the priority-neutral lattice. In particular, we show that the priority-neutral lattice need not be distributive. Moreover, we show that the greatest lower bound of two matchings in the priority-neutral lattice need not be their student-by-student minimum, answering an open question. This show that many widely-used properties of stable matchings fail for priority-neutral matchings; in particular, the set of priority-neutral matchings cannot be represented by via a partial ordering on a set of rotations. However, by proving a novel structural property of the set of priority-neutral matchings, we also show that not every lattice arises as a priority-neutral lattice, which suggests that the exact nature of the family of priority-neutral lattices may be subtle.

We study various novel complexity measures for two-sided matching mechanisms, applied to the two canonical strategyproof matching mechanisms, Deferred Acceptance (DA) and Top Trading Cycles (TTC). Our metrics are designed to capture the complexity of various structural (rather than computational) concerns, in particular ones of recent interest within economics. We consider a unified, flexible approach to formalizing our questions: Define a protocol or data structure performing some task, and bound the number of bits that it requires. Our main results apply this approach to four questions of general interest; for mechanisms matching applicants to institutions, our questions are: (1) How can one applicant affect the outcome matching? (2) How can one applicant affect another applicant's set of options? (3) How can the outcome matching be represented / communicated? (4) How can the outcome matching be verified? Holistically, our results show that TTC is more complex than DA, formalizing previous intuitions that DA has a simpler structure than TTC. For question (2), our result gives a new combinatorial characterization of which institutions are removed from each applicant's set of options when a new applicant is added in DA; this characterization may be of independent interest. For question (3), our result gives new tight lower bounds proving that the relationship between the matching and the priorities is more complex in TTC than in DA. We nonetheless showcase that this higher complexity of TTC is nuanced: By constructing new tight lower-bound instances and new verification protocols, we prove that DA and TTC are comparable in complexity under questions (1) and (4). This more precisely delineates the ways in which TTC is more complex than DA, and emphasizes that diverse considerations must factor into gauging the complexity of matching mechanisms.

A menu description presents a mechanism to player $i$ in two steps. Step (1) uses the reports of other players to describe $i$'s menu: the set of $i$'s potential outcomes. Step (2) uses $i$'s report to select $i$'s favorite outcome from her menu. Can menu descriptions better expose strategyproofness, without sacrificing simplicity? We propose a new, simple menu description of Deferred Acceptance. We prove that -- in contrast with other common matching mechanisms -- this menu description must differ substantially from the corresponding traditional description. We demonstrate, with a lab experiment on two elementary mechanisms, the promise and challenges of menu descriptions.

We consider the problem of implementing a fixed social choice function between multiple players (which takes as input a type $t_i$ from each player $i$ and outputs an outcome $f(t_1,\ldots, t_n)$), in which each player must be incentivized to follow the protocol. In particular, we study the communication requirements of a protocol which: (a) implements $f$, (b) implements $f$ and computes payments that make it ex-post incentive compatible (EPIC) to follow the protocol, and (c) implements $f$ and computes payments in a way that makes it dominant-strategy incentive compatible (DSIC) to follow the protocol. We show exponential separations between all three of these quantities, already for just two players. That is, we first construct an $f$ such that $f$ can be implemented in communication $c$, but any EPIC implementation of $f$ (with any choice of payments) requires communication $\exp(c)$. This answers an open question of [FS09, BBS13]. Second, we construct an $f$ such that an EPIC protocol implements $f$ with communication $C$, but all DSIC implementations of $f$ require communication $\exp(C)$.

We study the strategic simplicity of stable matching mechanisms where one side has fixed preferences, termed priorities. Specifically, we ask which priorities are such that the strategyproofness of deferred acceptance (DA) can be recognized by agents unable to perform contingency reasoning, that is, \emph{when is DA obviously strategyproof} (Li, 2017)? We answer this question by completely characterizing those priorities which make DA obviously strategyproof (OSP). This solves an open problem of Ashlagi and Gonczarowski, 2018. We find that when DA is OSP, priorities are either acyclic (Ergin, 2002), a restrictive condition which allows priorities to only differ on only two agents at a time, or contain an extremely limited cyclic pattern where all priority lists are identical except for exactly two. We conclude that, for stable matching mechanisms, the tension between understandability (in the sense of OSP) and expressiveness of priorities is very high.

We study the stable marriage problem in two-sided markets with randomly generated preferences. We consider agents on each side divided into a constant number of "soft tiers", which intuitively indicate the quality of the agent. Specifically, every agent within a tier has the same public score, and agents on each side have preferences independently generated proportionally to the public scores of the other side. We compute the expected average rank which agents in each tier have for their partners in the men-optimal stable matching, and prove concentration results for the average rank in asymptotically large markets. Furthermore, we show that despite having a significant effect on ranks, public scores do not strongly influence the probability of an agent matching to a given tier of the other side. This generalizes results of [Pittel 1989] which correspond to uniform preferences. The results quantitatively demonstrate the effect of competition due to the heterogeneous attractiveness of agents in the market, and we give the first explicit calculations of rank beyond uniform markets.

The seminal book of Gusfield and Irving [GI89] provides a compact and algorithmically useful way to represent the collection of stable matches corresponding to a given set of preferences. In this paper, we reinterpret the main results of [GI89], giving a new proof of the characterization which is able to bypass a lot of the "theory building" of the original works. We also provide a streamlined and efficient way to compute this representation. Our proofs and algorithms emphasize the connection to well-known properties of the deferred acceptance algorithm.

A breakthrough of Ashlagi, Kanoria, and Leshno [AKL17] found that imbalance in the number of agents on either side of a random matching market has a profound effect on the market's expected characteristics. Specifically, across all stable matchings, the "long side" (i.e. the side with a greater number of agents) receives significantly worse matches in expectation than the short side. Intuitively, this occurs because an agent on the long side is essentially unneeded to create a stable matching -- a matching could form almost as easily without them. Thus, an agent on the long side has very little market power, and must settle for a match which is not much better than a random assignment. We provide a new and simpler proof for a result of [AKL17] which formalizes this intuition.

State-of-the-art posted-price mechanisms for submodular bidders with $m$ items achieve approximation guarantees of $O((\log \log m)^3)$ [Assadi and Singla, 2019]. Their truthfulness, however, requires bidders to compute an NP-hard demand-query. Some computational complexity of this form is unavoidable, as it is NP-hard for truthful mechanisms to guarantee even an $m^{1/2-\varepsilon}$-approximation for any $\varepsilon > 0$ [Dobzinski and Vondr\'ak, 2016]. Together, these establish a stark distinction between computationally-efficient and communication-efficient truthful mechanisms. We show that this distinction disappears with a mild relaxation of truthfulness, which we term implementation in advised strategies, and that has been previously studied in relation to "Implementation in Undominated Strategies" [Babaioff et al, 2009]. Specifically, advice maps a tentative strategy either to that same strategy itself, or one that dominates it. We say that a player follows advice as long as they never play actions which are dominated by advice. A poly-time mechanism guarantees an $\alpha$-approximation in implementation in advised strategies if there exists poly-time advice for each player such that an $\alpha$-approximation is achieved whenever all players follow advice. Using an appropriate bicriterion notion of approximate demand queries (which can be computed in poly-time), we establish that (a slight modification of) the [Assadi and Singla, 2019] mechanism achieves the same $O((\log \log m)^3)$-approximation in implementation in advised strategies.

The article provides a background on Iran and U.S. foreign policy. Information is presented about the U.S.-Iran relations, foreign policy of Iran and its relations with Middle Eastern states, Russia and China, its support for terrorist groups such as Hamas and Hezbollah, the Iranian political system and the 200-2023 political protests, military structure and capabilities of Iran, as well as its nuclear, unmanned aerial vehicle and ballistic missile programs, and U.S. economic sanctions on Iran.

The article focuses on the challenges facing U.S. policymakers in light of the Taliban's return to power in Afghanistan. Topics include counterterrorism efforts regarding the Islamic State (ISIS) and Al Qaeda, the severe restrictions imposed on women and girls, and the ongoing humanitarian and economic crises in the country.

The article discusses the ongoing conflict between Israel and Lebanese Hezbollah, which escalated following Hamas's attacks on Israel in October 2023. It details the military exchanges, casualties, evacuations, and the humanitarian crisis in Lebanon. It also highlights Israel's military responses, including strikes on Hezbollah's leadership, and the potential implications for Iran, the U.S., and Lebanese politics.

The article focuses on Hezbollah's role as a significant Iranian-backed militia and its impact on regional stability and U.S. interests. Topics include the group's leadership and military capabilities, its involvement in Lebanese politics and social services, and its ongoing conflict with Israel and the implications for U.S. policy.

The article offers information related to Israel and Hamas October 2023 Conflict. It mentions Israel's cabinet formally declared war on Hamas and has initiated efforts to recover hostages, begun an aerial bombardment campaign against militants in Gaza. It also mentions Israel Defense Forces has called all civilians to evacuate southward and U.S. Secretary of State Antony Blinken and Israel have agreed to develop a plan that will enable international humanitarian aid to reach civilians in Gaza.

The article provides an overview of Iran's background and U.S. policy, highlighting Iran's regional influence and U.S. concerns about its nuclear program and support for armed groups. Topics discussed include historical U.S.-Iran relations, Trump and Biden administration policies, and developments in 2023, including attacks on Gulf shipping, diplomatic efforts, and a prisoner exchange.