Papers for

market designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Computing fair chore markets is as hard as difficult math problems

The Complexity of Computing a Competitive Equilibrium in Fisher Markets with Chores

Abstract: We study the complexity of computing competitive equilibria in Fisher markets with divisible chores and positive rational disutility coefficients and earning requirements. For linear disutilities, we prove that exact equilibrium computation is CLS-complete. In particular, the problem remains CLS-hard even when the earning requirements are binary in $1$ and $2^k$, where $k$ is an integer. We prove hardness by encoding the first-order conditions of a box-constrained quadratic program in equilibrium prices and earning flows, using a compact minimum-cost flow construction. For convex constant-elasticity-of-substitution (CES) disutilities, exact equilibrium prices may be irrational. We formulate the problem of finite-precision equilibrium price computation, in which we seek rational prices with a certified market clearing error at most a given rational tolerance encoded in binary. We prove that this problem is CLS-complete for every fixed rational exponent $ρ>1$. To prove this hardness, we encode a quartic polynomial through the fourth-order expansion of the CES price potential function corresponding to the Eisenberg-Gale (EG) dual program, and show that every sufficiently accurate approximate equilibrium of the constructed market lies near uniform prices. Additionally, we also identify a tractable special case of chores Fisher markets. In particular, we provide a strongly polynomial algorithm for exact equilibrium computation in linear markets whose disutility matrix has rank at most two and earning requirements are arbitrary positive rationals. For $n$ agents and $m$ chores, the algorithm uses $O(nm(n+m))$ rational arithmetic operations and comparisons, with polynomial intermediate encoding length.

Sun 8 NovComputer Science and Game Theory
The gist
This paper studies how hard it is to find fair prices and payments when people have chores to do instead of things they want. The authors show that exactly calculating these fair solutions is very challenging, as it requires solving complex mathematical problems. They also find some special cases where it is easier to compute these fair outcomes efficiently. This helps us understand which chore-sharing situations can be solved fairly with a computer and which cannot.
Open → 2611.11556v1

Improved upper bound on number of stable matchings in pairing problems

A Sub-$3^n$ Upper Bound on the Number of Stable Matchings

Abstract: We study the problem of determining the maximum number of stable matchings. This classical counting problem was posed by Knuth and has been studied for five decades. We obtain a new $2.999^n$ upper bound on the number of stable matchings with $n$ men and $n$ women. This improves the best-known previous result by Palmer and Pálvölgyi. This result gets much closer to the well-known lower bound $\frac{2.28^n}{\text{poly}(n)}$. We refine their entropy-based framework by capturing broader structural relationships among stable matchings. To capture these relationships, we introduce new frameworks, including cones and supports. This establishes the $3.332^n$ bound. We also exploit relationships among local structures and use a charging argument to improve the bound to $2.999^n$.

Wed 4 NovData Structures and AlgorithmsDiscrete Mathematics
The gist
Counting how many stable ways to match pairs of men and women can be tricky and has interested researchers for decades. The authors found a better way to limit the maximum number of these stable matchings, showing it is less than three times itself for each person involved. They built on earlier math methods by including more detailed relationships and introduced new tools to understand these matchings. This brings the upper estimate closer to the lowest known estimates, narrowing the possible range.
Open → 2611.06604v1

One woman’s strategy changes partner rankings in stable marriage markets

One Strategic Woman: Sharp Ranks and a Persistent Core

Abstract: In a balanced random stable-marriage market, one fixed woman manipulates men-proposing deferred acceptance to obtain her best attainable partner. We prove that the women's expected average true partner rank is asymptotic to $(\ln n)^2$, improving the previous $O((\ln n)^4)$ bound, while the men's is asymptotic to $n/(2\ln n)$. The men's and women's average ranks, normalized by $n/\ln n$ and $\ln n$, converge jointly in distribution to $(U,U^{-1})$, where $U$ is uniform on $(0,1)$. Under optimal truthful truncation, the span of women's average ranks within the reported stable core, divided by $\ln n$, converges in distribution to $U^{-1}-1$.

Wed 4 NovComputer Science and Game Theory
The gist
The paper studies a situation where many men and women are matched as partners, like in dating or job assignments. It looks at what happens when one woman strategically changes her preferences to get her best possible partner. The authors show math formulas describing how good partners the men and women get on average with this strategy. They also explain how much women’s choices can vary when they report their preferences truthfully in this matching game.
Open → 2611.06175v1

Mixed strategy elimination trails pure strategy by one round in games

Iterated Elimination of Dominated Mixed Strategies

Abstract: This note compares two iterated dominance procedures, one based on eliminating mixed strategies and one based on eliminating pure strategies. It shows that, in compact and continuous games, the mixed-strategy procedure can trail the pure-strategy procedure by at most one round: If the pure-strategy procedure terminates at round $M$, the mixed-strategy procedure terminates at either $M$ or $M+1$, and this bound is tight. It also provides two characterizations of the mixed-strategy procedure that are round-for-round equivalent to it and that require checking for improvements only against opponents' pure strategies.

Tue 3 NovComputer Science and Game Theory
The gist
The paper studies two ways to simplify games by successively removing less effective strategies. The first method removes strategies that are not helpful even when mixed with others, and the second method removes strategies only if they are pure and dominated. The authors find that the mixed strategy removal procedure takes at most one extra step compared to the pure strategy one. They also show how to check mixed strategy improvements by looking only at pure strategies, simplifying analysis.
Open → 2611.05705v1

Randomness and money burning can boost benefits in trade but with limits

The Power and Limits of Money Burning in Bilateral Trade

Abstract: We study the power of money burning in bilateral trade. In this problem, a seller owns an indivisible item, a buyer would like to acquire it, and each of these two traders has a private value for the item and the values are sampled from independent distributions. We ask whether the traders can benefit from a mechanism that burns money, that is, one that charges the buyer more than it pays the seller, so that neither trader enjoys the difference (money burnt is a loss for the traders). Is it possible that the traders will ever be better off if the trade mechanism can burn money? For Bayesian incentive-compatible mechanisms and for deterministic dominant-strategy incentive-compatible (DSIC) mechanisms, it is known that money burning is always a waste and can only hurt the traders. Maybe surprisingly, we show that once a DSIC mechanism can use randomization, money burning can significantly benefit the traders, and the gain of each of them can be arbitrarily large. In contrast, we show that the power of DSIC randomized mechanisms that burn money is still very limited in the sense that they cannot guarantee any constant fraction of the first-best gains-from-trade.

Tue 3 NovComputer Science and Game Theory
The gist
The paper looks at how two people trading a single item can sometimes do better if some of the money paid is deliberately wasted (burned). Normally, wasting money in trade only hurts everyone involved, but the authors show that if the trading rules allow random choices, wasting money can actually help both buyer and seller gain more. However, even with this trick, they prove there are limits to how much better off the traders can be, and they can't always get a big share of the best possible outcome.
Open → 2611.05505v1

Improving fair share guarantees for complex value settings in item division

Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations

Abstract: For $n$ agents and $m$ indivisible goods, an agent's maximin share (MMS) is the largest minimum bundle value she can obtain by partitioning the goods into $n$ bundles. Constant MMS approximations are known for additive, submodular, or XOS valuations, but whether such a guarantee exists for general subadditive valuations remains open. We advance this question in two directions. For general subadditive valuations, we exponentially improve the guarantee from $Ω(1/\log\log n)$ to $Ω(1/\log^* n)$, where $\log^* n$ is the iterated logarithm. We then seek constant MMS guarantees under additional structure on subadditive valuations by studying $q$-partitioning valuations: every partition of a bundle into at most $q$ groups admits nonnegative group prices that sum to the bundle's value and whose sum on any collection of groups is at most the value of their union. This hierarchy ranges from subadditivity at $q=2$ to XOS for $q\ge m$. We give the first study of MMS in the intermediate classes and prove constant guarantees whenever $q/n$ has a fixed positive lower bound, including $1/6$ for $q\ge n$ and $1/4$ for $q\ge2n$. For XOS valuations, we further improve the universal guarantee from $4/17\approx 0.2353$ to $5/16=0.3125$. For subadditive valuations, we prove a bidding amplification theorem that gives an exponential bound on each agent's probability of receiving less than half her MMS, while satisfying her budget in every outcome. For $q$-partitioning valuations, we give a scalar criterion that converts bounds on the value lost from disjoint deletions within a bundle into bounds on potential losses, even when an agent contributes zero below the target bundle value. For XOS valuations, we prove a reservation theorem that selects goods for integral assignment together with auxiliary additive valuations and accounts for the loss in rounding.

Tue 3 NovComputer Science and Game Theory
The gist
Dividing items fairly among many people is hard when everyone's value for groups of items isn't simple to add up. This paper improves how close we can get to a fair share for each person in very complex situations, making it much better than before. The authors break down complex value systems into levels and show constant fair share guarantees for several of these, including some where previous results didn't exist. They also develop new technical tools that make these guarantees stronger and more reliable.
Open → 2611.05073v1

On chain trading patterns reveal more racing than herding behavior

Herding or Racing? Decomposing Cross-Account Order-Flow Persistence in On-Chain Markets

Abstract: Most of the autocorrelation in trade signs on decentralized exchanges comes from pairs of trades sent by different wallets. For Uniswap v3, this has been read as herding dominating order splitting -- the reverse of what equity markets show. We show that this herding share mixes two quantities: the probability $p$ that consecutive orders come from the same account, which is small when thousands of wallets are trading, and the ratio $κ$ of cross-account to same-account sign correlation. For any $p$, $κ$ equals one under the public-signal benchmark of Tóth et al. and zero under independent order splitting. On Uniswap v3 USDC-WETH (one week each in 2023 and 2024), the herding share is 0.65-0.86, but $κ$ is only 0.05-0.10. On a fully on-chain EVM limit order book, the herding share is similar (0.61-0.87), but $κ$ is 0.72-0.76; among Uniswap swaps above USD 100k, it is 0.34-0.52. Where $κ$ is high, cross-account co-movement is mostly a race for the price on a centralized exchange. It is concentrated in orders a few blocks apart, and a cross-fitted gradient-boosted filter that sees only Binance data removes about three quarters or more of it. This race flow accounts for most of the losses of liquidity providers. We recommend reporting $κ$ alongside the herding share and modeling on-chain order flow as splitting traders plus arbitrageurs who respond to the centralized-exchange price.

Mon 2 NovComputational Engineering, Finance, and Science
The gist
Trades made on decentralized marketplaces often look like many different users are copying each other, a behavior called herding. The authors show that this isn’t the full story: a large part of this behavior is actually due to separate traders racing to act on price changes, not copying each other’s trades. They introduced a way to separate true herding from this racing effect and found that racing plays a big role especially in certain order books and large trades. This can help explain why people who provide liquidity to these markets often lose money.
Open → 2611.02616v1

Strategic tanking can improve matches without misreporting preferences

Strategic Tanking in Stable Matching Markets

Abstract: Motivated by a broad literature in psychology, organizational behavior, and matching markets, we introduce strategic tanking: an agent deliberately makes themselves less attractive to selected potential partners in order to improve their eventual assignment. Unlike traditional manipulation in stable matching, a tanker does not misreport whom they prefer; instead, they influence how others rank them. We show that tanking has a striking connection to classical preference manipulation. Cutoff tanking, in which an agent tanks with every potential partner below a chosen threshold, has exactly the same effect on the stable set as truncating one's own preference list at that threshold. Thus an agent can reproduce the power of a classical truncation while leaving their own preferences unchanged and every match acceptable. Arbitrary tanking, however, can go substantially further: under proposer-deferred acceptance, tanking equilibria can lie outside the sincere stable set. More broadly, whenever the sincere stable set contains multiple matchings, profitable strategic behavior remains available through either traditional preference manipulation or tanking, even when one side is restricted to honestly reporting their own preferences.

Fri 30 OctComputer Science and Game TheoryMultiagent Systems
The gist
Sometimes in matching systems like college admissions or job placements, a person can do better by making themselves seem less attractive to some potential partners. This is different from lying about what they want—here, they just influence how others rank them. The authors show that doing this in certain ways mimics another known tactic where people shorten their own preference lists, but without changing their true preferences. More complex ways of tanking can lead to results outside the usual stable options, meaning there are more ways to improve outcomes even if others are honest.
Open → 2610.42105v1

Learning algorithms shape game outcomes and enable collusion

How Learning Selects Equilibria and When It Leads to Collusion

Abstract: We study how learning algorithm design shapes equilibrium selection in infinite-horizon discounted Markov games with finite states and actions. Each episode, players choose smooth best responses to beliefs about opponents' policies, test them using noisy observations, and resample rejected beliefs or explore at rates determined by increasing transformations of their discounted values. We show that stochastically stable states induce approximate stationary Nash equilibria maximizing the minimum transformed discounted value across players, with transformations governing which players selection favors. In repeated games with bounded recall of noisy public signals, longer recall weakly increases the selected minimum transformed value. In repeated Cournot games, every stochastically stable state induces an approximate public perfect equilibrium whose minimum discounted profit across firms exceeds the Cournot-Nash benchmark. Collusion is therefore inevitable under these conditions and learning dynamics. For symmetric firms, selected profits can approach the monopoly benchmark arbitrarily closely. These results offer a novel equilibrium-selection perspective on algorithmic collusion.

Mon 26 OctComputer Science and Game Theory
The gist
This paper looks at how the design of learning algorithms affects which solutions players settle on in repeated games where they make decisions over time. The authors find that certain learning behaviors tend to select outcomes that benefit all players, sometimes leading to collusion where companies earn more than usual competitive profits. For example, in repeated market competition models, the learning process can push firms toward agreements that resemble monopoly profits rather than standard competition. These findings highlight how algorithmic learning can influence economic outcomes and explain why collusion might emerge without explicit agreements.
Open → 2610.36306v1

Tractability boundaries identified for hylland-zeckhauser matching models

Exploring the Tractability Frontier of Hylland-Zeckhauser Models

Abstract: The Hylland-Zeckhauser (HZ) mechanism provides a market-based approach to one-sided matching, making efficient equilibrium computation central to its implementation. Bi-valued utilities admit a strongly polynomial-time algorithm [VY], whereas with four values per buyer, the problem is PPAD-hard under inverse polynomial approximation [CCPY]. To understand the tractability boundary, we study two extensions of the bi-valued case: a third linear utility value and separable concave utilities with two common marginal slopes. For every fixed rational $a\in(0,1)$, we prove that computing a normalized additive $\varepsilon_{*}(a)/N$-equilibrium in an $N$-buyer HZ market is PPAD-hard for some constant $\varepsilon_{*}(a)>0$, even when all utilities belong to the same prescribed set $\{0,a,1\}$. This resolves the main question left open by [VY, CCPY]: whether three utility values already suffice for PPAD-hardness. Using the same market gadgets, we show that hardness at a specified constant accuracy on the recognizable family generated by our construction is equivalent to the PCP-for-PPAD conjecture. Consequently, assuming that conjecture, general markets over $\{0,a,1\}$ admit no PTAS unless $\mathrm{PPAD}\subseteq\mathrm{P}$. For the concave extension, we compute an exact equilibrium in polynomial time with two marginal slopes common across goods for each buyer and arbitrary rational buyer--good breakpoints. The algorithm selects a cheapest utility-maximizing bundle for each buyer. With three common marginal slopes, suitable breakpoints encode the three valued linear case, yielding PPAD-hardness. Thus, our paper identifies two thresholds separating tractable and intractable cases of HZ models with utility functions specified by utility values or marginal slopes. In both cases, the tractability threshold lies between two and three.

Mon 26 OctComputer Science and Game Theory
The gist
The paper studies a particular market-based method for matching buyers and goods efficiently. It shows that when buyers have three different utility values, finding an approximate equilibrium is computationally very hard, confirming a long-standing open question. The authors also identify a case with special concave utilities where equilibrium can still be found efficiently. Their work thus pinpoints exactly when this matching problem transitions from easy to hard, based on the complexity of utility preferences.
Open → 2610.35848v1

Iterated round robin methods may not always settle but some strategies guarantee fairness

On the Convergence of Iterated Round Robin

Abstract: Round Robin (RR) is a simple and widely used picking sequence mechanism for allocating indivisible goods, known to guarantee envy-freeness up to one item (EF1) when preferences are additive. Despite being manipulable (meaning that agents may have an incentive to strategically misreport their preferences), it is known to always admit at least one pure Nash equilibrium. In this paper, we study an iterated variant of RR, in which agents observe the outcome of the mechanism at each iteration and may revise their reported preferences through a best-response dynamics. We first consider a full-information setting, where agents observe both the outcome and the reported preferences of all the agents. In this setting, we show that cycles can occur even under strong restrictions on the manipulations carried out by the agents. We nonetheless identify a natural restriction (item-preserving swaps), under which convergence to a pure Nash equilibrium is guaranteed to exist for any number of agents and items. We also show that restricting to adjacent swaps guarantees convergence for two agents and a limited number of items, leaving the question open for unbounded number of items. We then turn to a partial-information setting, in which agents only observe the resulting allocation and must then infer the preference profiles of the others assuming consistency with the RR sequence. We study three behaviours guiding the agents when deciding how to manipulate under uncertainty on the other agents' preferences. We show that two of the studied behaviours, despite being quite natural, may cycle while a more cautious rule guarantees iterated RR to be strategyproof.

Fri 16 OctComputer Science and Game Theory
The gist
When sharing items among people, Round Robin is a common fair method where everyone takes turns picking items. The paper studies what happens when people change their stated preferences repeatedly to get better outcomes. The authors find that this process can sometimes get stuck in cycles and never settle on a stable sharing plan. But if people’s preference changes follow certain restrictions, the sharing method will eventually settle into a stable and fair outcome. They also examine situations where people don’t see all preferences and find some cautious strategies ensure fairness.
Open → 2610.23040v1

Fair division with subsidies ensures balanced outcomes for indivisible items

Best-of-Both-Worlds Fair Division via Subsidies

Abstract: We study the relationship between fair division with $\textit{subsidies}$ and $\textit{best-of-both-worlds}$ (BoBW) fairness for indivisible items. We prove a general reduction of BoBW existence to envy-freeability. Specifically, for any scale-free ex-post property $P$ (e.g., EF1, EFX, PO) and any scale-free valuation class $\mathcal{V}$ (e.g, additive, submodular, subadditive, monotone), if every instance in $\mathcal{V}$ admits a $P$-allocation that can be made envy-free using subsidies, then every such instance admits an ex-ante envy-free lottery supported on $P$-allocations. The proof uses linear programming duality. As applications, the reduction gives alternative proofs of BoBW existence results for additive goods, chores, and mixtures of goods and chores. The converse of our general reduction holds for two agents but fails for three: We provide a four-good counterexample with monotone submodular valuations where an ex-ante envy-free and ex-post EF1 lottery exists, but no allocation is simultaneously EF1 and envy-freeable. For lexicographic valuations, we prove simultaneous EFX, Pareto optimality, and envy-freeability (and hence BoBW guarantees for EFX+PO) for three agents, and show that even EFX and envy-freeability can be incompatible for four agents.

Sat 10 OctComputer Science and Game Theory
The gist
Fairly dividing things that can't be split, like toys or chores, is tricky because some people might feel left out or unfairly treated. The authors found a way to use subsidies—extra help like money or tokens—to make these divisions feel fair both before and after the items are assigned. They proved that if subsidies can fix envy after dividing, then it's possible to create a fair random lottery over different fair divisions. Their work connects complicated fairness rules and shows which combinations work well or not, depending on the number of people and item types.
Open → 2610.14994v1

Constant-factor approximation improves utility in multidimensional consumer choice

A Constant-Factor Approximation to Multidimensional Consumer Utility

Abstract: Motivated by social services where consumers pay with non-transferable ordeals, we study mechanisms that maximize consumer utility for multiple unit-demand buyers and heterogeneous items whose values are drawn independently from known prior distributions. Prior work in utility maximization approximates social welfare and shows that the gap between optimal utility and social welfare is logarithmic. We resolve the question of whether simple mechanisms can guarantee a constant-factor approximation to optimal utility itself. Our mechanisms achieve a $(5.67+\varepsilon)$-approximation for general independent values, improving to $2e/(e-1)<3.164$ when values are i.i.d. Each buyer chooses their favorite option from posted item prices or free item lotteries, and contention resolution determines which buyers' requests are served; this is BIC, ex-post individually rational, and computable in polynomial time. Our main technical contribution is a general upper bound on the optimal ex-ante-constrained utility that separates the contributions captured by posted prices and free lotteries. These results establish a utility counterpart to the theory of simple, approximately revenue-optimal mechanisms.

Wed 7 OctComputer Science and Game Theory
The gist
This paper looks at how to design simple selling methods that help buyers get as much satisfaction as possible when choosing from many different items, each valued differently. The authors created a way to set prices and lotteries so buyers pick their favorite options, and then decide fairly who gets which item. Their method guarantees that the total happiness of all buyers is within a fixed fraction of the best possible. This solves a longstanding question about whether such simple approaches can closely match ideal results.
Open → 2610.10516v1

Minimum subsidies needed for fair allocation of indivisible goods

Asymptotic Subsidies for Envy-Free Allocation

Abstract: We study the minimum monetary subsidy required for exact envy-freeness in allocating $m_n$ indivisible goods to $n$ agents. Valuations are additive, item values are i.i.d. from a distribution on $[0,1]$ with density bounded above and away from zero, and all agents value money equally. We consider $n\to\infty$ with $m_n=qn+r_n$, where $q\ge0$ is a fixed integer and $0\le r_n<n$. For the nonzero-remainder case where $1\le r_n<n$, we give a cubic-time algorithm based on a maximum-weight matching of balanced bundles and complementary dual prices. It returns an envy-free outcome for every instance. Under the random model, both its payment and the unrestricted minimum are $n-r_n+o_p(n)$ for $q\ge1$. When $q=0$ and $r_n/n$ converges to a limit below one, the error term improves to $O_p(1)$. For exact divisibility, where $r_n=0$, prior work gives zero subsidy with high probability for $q\ge2$. The square case $q=1$ is exceptional. Its minimum subsidy is $Θ_p(\log n)$ and, with high probability, equals the optimum over allocations in which every agent receives exactly one good. This restricted optimum can be computed in cubic time using a maximum-weight perfect matching and all-pairs shortest paths. Together, these results provide a unified asymptotic characterization of the minimum subsidy.

Wed 7 OctComputer Science and Game Theory
The gist
Dividing indivisible goods fairly between many people can sometimes cause envy, where someone feels another got a better share. This paper studies how much extra money (subsidy) is needed to prevent envy exactly when dividing these goods. The authors provide algorithms and mathematical results to calculate this minimum subsidy, especially as the number of people grows very large. Their findings give a clear picture of how subsidies behave depending on the number of goods and people involved.
Open → 2610.10272v1

Envy-free allocations feasible with individual budget constraints

Envy-free Allocations with Individual Payments

Abstract: When an envy-free allocation of indivisible goods does not exist, monetary transfers can restore envy-freeness. Existing work on fair division with subsidies, however, typically assumes that these payments are provided by an external source, an assumption that may be unrealistic in many applications. We address this limitation by allowing only monetary transfers between agents, with each agent's payments constrained by their individual budget. We show that while it is polynomial-time tractable to determine whether a given allocation can be made envy-free by payments under individual budgets, the general problem of computing such an allocation from scratch is NP-hard, even when agents have relatively large budgets. Motivated by this intractability, we conduct a parameterized complexity analysis, establishing fixed-parameter tractability with respect to the number of goods or to the joint parameter number of agents and good types, and we provide efficient algorithms in several special cases. For explicitly listed items, our type-based algorithm answers the envy-freeness part of an open question of T. T. Nguyen and J. Rothe, "Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey."

Wed 7 OctComputer Science and Game TheoryData Structures and Algorithms
The gist
Sometimes when dividing things fairly, it's impossible to make everyone feel they got a fair share without some payments. The authors study how people can pay each other, respecting each person's spending limits, to fix these fairness problems. They found it's easy to check if a given division can be fixed this way but hard to find a good division from scratch. They also developed ways to handle some special cases efficiently and answered part of an open question about such problems.
Open → 2610.09610v1

Communication limits challenge truthful combinatorial auction designs

The Hardness of Dominant Strategy Mechanism Design, Revisited

Abstract: We study the communication complexity of \emph{dominant-strategy incentive-compatible} (DSIC) mechanisms for combinatorial auctions. For $γ\in [\log m, m]$, let $\mathsf{DSIC_{GEN}}(m, γ)$, $\mathsf{DSIC_{XOS}}(m, γ)$, and $\mathsf{DSIC_{GS}}(m, γ)$ denote the best approximation ratio attainable by a deterministic, individually rational, no-negative-transfers, DSIC mechanism using at most $2^γ$ communication over $m$ items, for general monotone, XOS, and gross substitutes (GS) valuations, respectively. We give a unified proof that shows $\mathsf{DSIC_{GEN}}(m, γ) = Ω(m/γ)$, $\mathsf{DSIC_{XOS}}(m, γ) = Ω((m/γ)^{1/5})$, and $\mathsf{DSIC_{GS}}(m, γ) = Ω((m/γ)^{1/7})$. The GS lower bound answers an open question of~\cite{DobzinskiRV22}: although poly-communication welfare maximization for GS valuations admits a poly-communication deterministic truthful mechanism via VCG, no good approximation is possible in poly-communication for deterministic DSIC mechanisms. Additionally, the general lower bound establishes that $\mathsf{DSIC_{GEN}}(m, γ) = Θ(m/γ)$ due to the deterministic DSIC $O(m/γ)$-approximation of~\cite{QiuW24}. We also obtain several results in the two-bidder setting. We show that attaining a $1.0001$-approximation for two weighted matroid-rank valuations (a subclass of GS) with a universally DSIC mechanism requires exponential communication. On the other hand, we give a poly-communication $(1+\sqrt{5})/2 \approx 1.618$-approximation for two submodular bidders using a universally DSIC mechanism. Prior to this work, it was not known whether even a poly-communication universally truthful mechanism could beat a $2$-approximation for two submodular valuations, nor whether a poly-communication universally DSIC mechanism could beat a $2$-approximation for two weighted matroid rank valuations.

Mon 5 OctComputer Science and Game Theory
The gist
This paper looks at how hard it is for auction systems to guarantee honest bidding when selling many items at once. The authors show that if the auction tries to communicate efficiently while ensuring honesty, it cannot achieve very good results, especially in complex cases. They prove that even for special types of bidder preferences, improving accuracy requires a lot of communication. They also give new examples demonstrating these limits in simple two-bidder auctions.
Open → 2610.06773v1

Improved worst case efficiency bound for random trade offers

An Improved Upper Bound for the Random-Offerer Mechanism in Bilateral Trade via Recursive Hard Instances

Abstract: We study the worst-case efficiency of the random-offerer mechanism in bilateral trade relative to the first-best gains from trade. We construct a family of independent buyer value and seller cost distributions whose ratio converges to $0.436943488\ldots$, improving the previous upper bound of $0.460242308\ldots$. Our construction combines recursively nested seller distributions with downward transport of buyer values. The recursive structure allows contributions from different scales to accumulate, leading to stronger hard instances. We analyze this construction through a recurrence and obtain an analytic characterization of the limiting constant.

Mon 5 OctComputer Science and Game Theory
The gist
The paper studies how efficient a simple trade method is when a buyer and seller randomly decide offers. The authors find new worst-case examples showing the method performs a bit worse than previously known, improving the known limit from about 46% to about 44%. They build tricky value and cost scenarios using a repeating pattern to make the efficiency drop. This helps better understand the limitations of random offer trading mechanisms.
Open → 2610.06547v1

Simple trading mechanisms achieve optimal gains in matching markets

The Power of Simple Mechanisms: A Tight $e$-Approximation for Gains from Trade in Matching Markets

Abstract: We study how well simple mechanisms approximate gains from trade (GFT) in two-sided matching markets with independent buyer values and seller costs, where feasible outcomes form an arbitrary downward-closed family of matchings. This model includes bilateral trade and double auctions as special cases. We focus on the Generalized Random-Offerer (GRO) mechanism, which is an equal mixture of the Generalized Sellers-Offering Mechanism (GSOM) and the Generalized Buyers-Offering Mechanism (GBOM). We determine GRO's exact worst-case approximation ratio with respect to first-best GFT, showing that it is $e$. This improves the previous $3.15$ approximation guarantee (Babaioff et al. STOC 2026) for the same mechanism. In bilateral trade, the result implies a $1/e$ guarantee for the random-offerer mechanism, improving the previous $1/π$ bound (Jo 2026). Our analysis uses a two-dimensional inequality in quantile space to compare first-best GFT with optimal one-sided auction profits. For each potential trade, we identify the region of buyer values and seller costs for which the first-best allocation selects that trade, and then randomly shrink this region in quantile space, yielding posted-price rules whose expected profits can be evaluated exactly. We establish tightness of the $e$ approximation by constructing markets with regular type distributions, pairwise disjoint trading edges, and a single knapsack constraint. On these instances, GRO's expected GFT approaches a $1/e$ fraction of first-best GFT, therefore ruling out any better guarantee even under these restrictions.

Tue 29 SeptComputer Science and Game Theory
The gist
This paper looks at how well simple methods can do when matching buyers and sellers in markets to maximize gains from trade. The authors focus on a mechanism that randomly mixes two ways of offering trades and prove it gets very close to the best possible outcome—specifically, within a factor of e (about 2.718). They improve previous results that had weaker guarantees. Their analysis uses math to carefully compare ideal trade outcomes with what these simple methods can reliably achieve. They also show that their result is the best possible under reasonable conditions.
Open → 2609.37997v1

Truthful mechanism guarantees fair share of indivisible goods for agents

Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee

Abstract: We study the truthful and fair allocation of indivisible goods to $n$ strategic agents with additive valuations. Babaioff, Feige, and Manaker Morag [FOCS 2026] gave a randomized mechanism that uses only the agents' rankings of the goods, is truthful in expectation (TIE), and guarantees every agent $1/(H_{n-1}+2)=Θ(1/\log n)$ of her maximin share (MMS) in every realized allocation, where $H_{n-1}$ is the $(n-1)$th harmonic number; this is nearly the best possible with rankings alone. They conjectured that cardinal information allows TIE mechanisms to achieve a constant ex-post MMS guarantee. We confirm this conjecture: our TIE mechanism guarantees every agent at least $1/7$ of her MMS in every realized allocation; moreover, the mechanism is ex-ante envy-free and can be implemented in polynomial time. Our mechanism has two key technical ingredients, both of which may be of independent interest. The first is a truthful fractional allocation rule specifying each agent's probability of receiving each good: it favors each agent on her top $n-1$ goods and reduces her probability of receiving a good for each other agent who also ranks it among her top $n-1$ goods. The second is the balanced edge coloring: we decompose these probabilities into equally likely matchings from agents to high-value goods, those that alone meet an agent's guarantee, and balance these matchings in a fine-grained way without changing any marginal probability, so that every agent who receives no high-value good can obtain sufficient value from the remaining goods without over-allocating any good.

Mon 28 SeptComputer Science and Game Theory
The gist
The paper studies how to fairly divide indivisible items among people who value them differently and may act strategically. Previous work showed it’s possible to guarantee each person a fair share based only on their rankings, but that share decreases as the group grows. The authors confirm a prediction that knowing exact values lets you do better: their method ensures everyone gets at least one-seventh of their fair share, and no one envies others before the division. This method runs efficiently and uses randomness cleverly to be truthful and fair.
Open → 2609.35670v1

Fair and efficient resource allocation problems occupy complex decision class

Fair and Efficient Allocations: Decision Problems in the Gap of Polynomial Hierarchy

Abstract: We consider the fair division problem with indivisible goods and study the following decision problem: given a fair division instance, does there exist an allocation that is envy-free and efficient? We consider two efficiency criteria: Pareto-optimality and social welfare optimality. We provide a complete landscape on the computational complexity of this decision problem, with the number of agents ranging from $2$ to $\infty$, both additive valuations and general valuations, and the more restricted class of $k$-ary valuation functions (where an item's marginal value is restricted to $\{0,1,\ldots,k-1\}$ for some constant $k\geq2$). One interesting observation is that many versions of the above-mentioned decision problems fall into the ``gap'' between the first and the second levels of the polynomial hierarchy. Specifically, assuming the polynomial hierarchy does not collapse to the first level (i.e., assuming $\text{NP}\neq\text{coNP}$), these problems are in $(Σ_2^{\text{p}}\capΠ_2^{\text{p}})\setminus(\text{NP}\cup\text{coNP})$. In particular, we provide a fine-grained complexity analysis across different parameter regimes, including the number of agents and the choice of valuation models. Depending on different parameters, many problems admit different complexity classifications, ranging from the intermediate classes $Θ_2^{\text{p}}$ and $Δ_2^{\text{p}}$ between the two levels to $Σ_2^{\text{p}}$-completeness. Finally, De Keijzer et al. show the $Σ_2^{\text{p}}$-completeness of the decision problem when considering Pareto-optimality as the efficiency criterion with additive valuations. Our main results extend this result to more restricted settings, such as instances with a constant number of agents or $3$-ary valuation functions, which resolves the open problem given by Bouveret and Lang.

Fri 25 SeptComputer Science and Game Theory
The gist
This paper looks at how to fairly divide things that cannot be split, like indivisible items, among people so that no one envies another and the outcome is efficient. The authors study how hard it is to decide if a perfect division exists under different rules and conditions. They find that many of these problems are more complicated than typical computer problems, lying between well-known complexity levels, which means they are challenging to solve quickly. Their results also answer previously open questions about these difficulties in simpler situations with fewer people or restricted ways of valuing items.
Open → 2609.31849v1

Matching markets achieve most trade gains with simple rules

From Bilateral Trade to Matching Markets: Sharp Gains from Trade

Abstract: We study gains from trade in matching markets with independent private values and costs, Bayesian incentive compatibility, interim individual rationality, and no expected budget deficit. A second-best guarantee for finite bilateral trade extends without loss to matching markets with independent Borel priors, arbitrary downward-closed feasibility, and finite expected first-best gains. For bounded buyers with monotone hazard rates and arbitrary bounded sellers, we determine the exact worst-case ratio of second-best to first-best gains, approximately $0.72490721$. For binary buyers and sellers with at most $m$ types, we determine the exact ratio for every $m$, including $8/9$ when $m=2$ and a limit of $4/5$ as $m$ grows. Both families of bounds are tight already in bilateral trade.

Fri 25 SeptComputer Science and Game Theory
The gist
This paper explores how much benefit can be gained from trading things when many buyers and sellers match up, each with their own private values. The authors find exact limits on how efficient trade can be under certain fairness and incentive constraints, even when there are many types of buyers and sellers. Their results expand known insights from simple one-on-one trades to complex markets where multiple matches happen. They measure precisely how close practical trade outcomes come to the best possible trade outcomes.
Open → 2609.30702v1

Envy-free sharing of indivisible goods guaranteed with perfect complements

Envy-Free Allocation of Indivisible Goods under Leontief Preferences

Abstract: Envy-freeness is a fundamental notion of fairness in the allocation of indivisible goods. In this paper, we study envy-free allocation under Leontief preferences, which model perfect complements. Although Leontief preferences have been extensively studied in the context of allocating divisible goods and market equilibria, they have received comparatively little attention for the allocation of indivisible goods. We show that, unlike additive valuations in cardinal preferences, an envy-free allocation always exists for Leontief preferences when there are at least two goods. In contrast, envy-free allocations may fail to exist when there is a single good, however it can be decided in polynomial time. We next study the problem of computing a welfare-maximizing envy-free allocation. We prove that this problem is NP-hard in general, whereas it is polynomial-time solvable when there is only a single good or agents have identical demands. Finally, we investigate the parameterized complexity of this problem.

Wed 23 SeptComputer Science and Game TheoryComputational Complexity
The gist
Fair division means giving items to people so no one feels jealous of another’s share. This paper studies a type of preference where goods must be combined in fixed proportions, called Leontief preferences, often seen as perfect complements. The authors show that if there are at least two goods, it is always possible to divide them fairly without envy. They also explore how hard it is to find the fairest such division and identify scenarios where this task is easier or harder. Their work helps understand fairness in situations where items cannot be split and must be combined in specific ways.
Open → 2609.28308v1

Two more sellers or buyers enable optimal trade in two-sided markets

The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets

Abstract: We study Bulow-Klemperer-style competition complexity in two-sided double auctions with $m$ unit-demand buyers drawn i.i.d. from $F_B$ and $n$ unit-supply sellers drawn i.i.d. from $F_S$. When $m \ge n$ and buyer valuations first-order stochastically dominate seller costs ($F_B \succeq_{\mathrm{FSD}} F_S$), we prove that recruiting just two additional sellers enables Seller Trade Reduction (STR), a prior-independent mechanism, to achieve expected Gains From Trade (GFT) at least the first-best GFT of the original market. When the buyer side is the smaller side of the market ($m \le n$), an analogous result holds for Buyer Trade Reduction with 2 additional buyers. This resolves open questions of Babaioff, Goldner, and Gonczarowski (SODA 2020) and Cai, Liaw, Mehta, and Zhao (STOC 2024). We complement our upper bound by showing that this uniform bound is optimal: already for $m = n = 1$, no prior-free mechanism (deterministic or randomized) that is dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced can match the first-best GFT by recruiting only one additional seller.

Wed 23 SeptComputer Science and Game Theory
The gist
This paper studies trading between buyers and sellers, where each side has many participants with different values for goods. The researchers show that by adding just two extra participants on the smaller side, simple trading methods can achieve the best possible total gains from trade without knowing exact details about buyers or sellers. They also prove that adding only one extra participant is not enough to reach this optimal outcome. This answers previously open questions about how many extra participants are needed for effective trading mechanisms.
Open → 2609.27304v1

Matching mechanisms enable simple access to desired outcomes

Singleton-Attainability and Transparent Access in Matching

Abstract: Matching mechanisms differ in how much of an agent's preference ranking must be determined and reported to obtain a particular object. A mechanism is singleton-attainable (SA) if every object that an agent can obtain through some report can also be obtained by reporting only that object as acceptable. With an SA mechanism, once an attainable object has been identified, the agent need not rank or report any other object. Singleton-attainability identifies a distinct dimension in matching theory and market design: transparent access to attainable outcomes, separate from incentives, stability, welfare or equity. We establish general conditions for SA and derive its strategic implications. Top-lift invariance and truncation invariance together imply SA, while strategyproofness and stability each imply SA. By contrast, no Pareto improvement over a strategyproof, individually rational, and non-wasteful mechanism is SA. In particular, every Pareto improvement over Deferred Acceptance violates SA. We introduce report width, which measures how many acceptable objects may have to be reported to obtain an object. SA mechanisms have report width one. Report width is unbounded for a large class of efficient mechanisms that Pareto-improve Deferred Acceptance. Stable selection with report-induced priorities has width one when priorities are monotone and maximal width under reverse priority dominance. Rank-welfare maximization has width one when the outside-option rank is fixed and maximal width when it is report-dependent. These results reveal a structural divide, which we call the width dichotomy: across all mechanisms and families in our classification and all structural classes we study, report width is either one or unbounded.

Wed 23 SeptComputer Science and Game Theory
The gist
Matching systems decide how people get assigned to things like schools or jobs based on preferences. This paper looks at how much a person needs to list their choices to get a certain outcome. The authors identify a type of system where someone can get an object just by saying that object is acceptable, without listing others. They explore the implications and conditions of these systems, showing a sharp divide between mechanisms that need only one acceptable choice and those that require many.
Open → 2609.27293v1

Improved approximation for maximizing submodular functions in matroid intersections

Submodular Maximization over Bipartite Perfect Matchings and Matroid Intersection Bases

Abstract: Motivated by applications in fairness and foundational questions, we consider the problem of maximizing a monotone submodular function $f\colon 2^E \rightarrow \mathbb{R}_+$ over maximum cardinality sets in the intersection of two matroids on a common ground set $E$. An important special case is submodular perfect matching in bipartite graphs. Prior to this work, its approximability was poorly understood with only constant inapproximability known, despite not even a $\frac{1}{o(\sqrt{|E|})}$-approximation being known. Even when allowing to violate the cardinality constraint slightly, only a bicriteria approximation with a significant loss in the objective was known. Here, we obtain two results. First, we show that, within constant factors, the problem is approximation-equivalent to Submodular Orienteering in directed graphs. This yields an $Ω(1 / \log |E|)$-approximation in quasi-polynomial time together with an almost-matching hardness result. Second, we obtain an improved polynomial-time bicriteria approximation via a local search framework. More precisely, if $f(T^*)$ is the largest submodular value of a common independent set in both matroids of size at least $K$, we find a common independent set $T$ such that $|T| \geq (1 - ε) K$ and $f(T) \geq (1/2 - ε) f(T^*)$. In contrast, previous work only guarantees a value of $Ω(ε) f(T^*)$ while ensuring that $|T| \geq (1 - ε) K$.

Fri 18 SeptData Structures and Algorithms
The gist
This paper studies how to best choose a set of items that follow certain rules, to maximize a special kind of value called a 'submodular function,' which represents benefits with diminishing returns. The authors focus on cases where these items must form perfect matchings in bipartite graphs or satisfy two matroid constraints, which generalize many real-world pairing or selection problems. They reveal new connections to a known hard problem called submodular orienteering, leading to improved approximation methods. Their new technique also finds nearly optimal solutions that slightly relax size constraints but achieve much better value than previous approaches.
Open → 2609.21696v1

Max min fairness achieves near optimal results in large random markets

Asymptotic Max-Min Fair Allocation with Random Utilities

Abstract: We investigate the asymptotic behavior of max-min fair allocations for indivisible goods under i.i.d. random utilities. For $N$ agents and $K$ goods with utilities ${\mU_{i,j}}$ drawn independently from a common distribution $F$, we derive asymptotic characterizations of the max-min value in the balanced case $K=N$ (and in $K=LN$ extensions) via distributional quantiles. We then study the efficiency impact of max-min fairness by comparing the resulting total welfare with the optimal sum welfare. For distributions with sufficiently light tails, we prove that the relative efficiency loss converges to zero as the market grows, implying that max-min fairness incurs negligible welfare loss in large random instances for a broad class of distributions.

Wed 16 SeptComputer Science and Game TheoryInformation Theory
The gist
This paper looks at how to fairly divide items among people when each person values items differently and those values are random. The authors study a specific fairness rule called max-min fairness, which tries to make the worst-off person as well off as possible. They find that as the number of people and items grows, the fairness rule’s solution gets very close to the best possible overall happiness. This means that using max-min fairness in large random settings doesn’t really reduce total satisfaction much.
Open → 2609.19319v1

Matching markets keep half their best gains despite constraints

Second-Best Gains from Trade in Matching Markets

Abstract: We study gains from trade (GFT) in two-sided matching markets with independent private types and arbitrary downward-closed feasibility constraints. The second-best benchmark is the maximum expected GFT achievable by a Bayesian incentive compatible, interim individually rational mechanism that is strongly budget balanced at every report profile. These constraints generally preclude attaining the first-best GFT and raise the question of how much efficiency must be lost. We prove that the second-best GFT is at least one half of the first-best GFT in every such matching market. This recovers and generalizes the recent $1/2$ guarantee for bilateral trade by Liu et al. (2026) to markets with multiple buyers and sellers and arbitrary downward-closed feasibility constraints. Together with their matching lower bound for bilateral trade, our result establishes a tight worst-case ratio of $1/2$ for this general class of matching markets. Our proof builds on the virtual-GFT framework of Brüstle et al. (EC 2017) to reduce the problem to a one-parameter Lagrangian. The main step is a geometric, edge-by-edge analysis based on first-best edge-selection regions, combined with a randomized contraction in rank space.

Wed 16 SeptComputer Science and Game Theory
The gist
In markets where buyers and sellers are matched based on their preferences and limitations, it’s often impossible to achieve the absolute best trade efficiency due to practical rules. The authors show that even under these tough conditions, you can still capture at least half of the best possible gains from trade. This finding applies not just to simple one-to-one trades but also to more complex markets with many participants and restrictions. They use mathematical tools to prove this important efficiency guarantee.
Open → 2609.18724v1

Prediction markets improve capital recovery using flow-dependent fees

Prediction-Market Seed Capital Recovery from Noise-Dominant Flow

Abstract: Automated prediction markets require sponsors to prefund liquidity before observing order flow, creating a financing challenge at launch. We study whether nonnegative charges conditioned on observable payoff direction can improve recovery of this prefunded capital while limiting their effect on informed participation. We develop Seed Capital Flow (SCF), a direction-conditioned levy, in a stylized binary cost-function market with informed and liquidity-motivated traders. When order composition differs across directions, SCF concentrates the permitted fee burden on the direction with relatively more liquidity-motivated flow, whereas a uniform fee spreads it across both directions. Under a sufficiently tight common retention constraint, this allocation yields higher expected recovery capacity and can make additional liquidity choices financially viable. Synthetic numerical audits examine robustness to alternative flow patterns, stochastic arrivals, and label misspecification. The results characterize a mechanism-design tradeoff rather than an empirical prediction: the market remains prefunded, recovery is expected rather than guaranteed, and the analysis is limited to an opening-cohort setting.

Sat 12 SeptComputational Engineering, Finance, and Science
The gist
Starting prediction markets is tricky because someone has to put up money before people start trading. The authors study a new way to recover this upfront money by charging fees that depend on which side of the market is more noisy or less informed. Their method focuses fees on the less informed side, helping recover more money without hurting the participation of informed traders. They tested the idea using simulations and showed it can help markets be more financially sustainable at the start.
Open → 2609.14038v1