Digital labor markets are increasingly used to procure diverse forms of human input, from data annotation to food delivery. A central concern in such markets is the ability of platforms to suppress wages by exploiting the abundance of low-cost labor. To better understand labor outcomes, we introduce a novel posted-price procurement model with coverage objectives. In our model a platform seeks to acquire a set of M tasks while minimizing wait time, as well as total spending. Workers are sampled from a population and complete a task if the posted price is higher than their estimated cost of labor. First, we show that with a simple pricing strategy the platform can cover all categories in time O(M), while paying only a O(log(M)/M) fraction of the total cost of labor by exploiting high worker uncertainty about their costs. Then, we study the impact of collective action to prevent the exploitation of workers. We show how a small, strategically chosen coalition of workers that commits to a price floor forces the platform's total spending from logarithmic to linear in M, substantially reducing the power of the platform to suppress wages. In contrast, a randomly sampled coalition of equal size remains largely ineffective. We complement our theory with synthetic experiments that demonstrate the benefit of targeted recruitment for collective action across different market regimes. More broadly, our results provide a theoretical foundation for understanding how to organize collective bargaining for promoting welfare in digital labor markets.
论文检索
输入标题、作者或关键词，从 100,903 篇学术成果中精准定位
Online market platforms play an increasingly powerful role in the economy. An empirical phenomenon is that platforms, such as Amazon, Apple, and DoorDash, also enter their own marketplaces, imitating successful products developed by third-party sellers. We formulate a Stackelberg model, where the platform acts as the leader by committing to an entry policy: when will it enter and compete on a product? We study this model through a theoretical and computational framework. We begin with a single seller, and consider different kinds of policies for entry. We characterize the seller's optimal explore-exploit strategy via a Gittins-index policy, and give an algorithm to compute the platform's optimal entry policy. We then consider multiple sellers, to account for competition and information spillover. Here, the Gittins-index characterization fails, and we employ deep reinforcement learning to examine seller equilibrium behavior. Our findings highlight the incentives that drive platform entry and seller innovation, consistent with empirical evidence from markets such as Amazon and Google Play, with implications for regulatory efforts to preserve innovation and market diversity.
We initiate the study of single-sample bilateral trade with a broker, drawing an analogy to the setting of single-sample bilateral trade without a broker considered in [1] and [5]. Our model captures the three-sided interaction in which a broker mediates trade between a buyer and seller, each described by a valuation distribution from which a single sample can be drawn. We consider two settings in particular: one where the valuation distributions of the buyer and seller are identical and one where the valuation distributions are stochastically ordered. We analyze simple mechanisms that rely only on a single sample from each agent's distribution and show that these mechanisms achieve constant-factor approximations to the first-best gains-from-trade (GFT), first-best social welfare (SW), and optimal profit under the standard monotone-hazard-rate assumption. We then complement these results with matching or nearly matching upper bounds on the GFT and SW of our mechanisms. Notably, in both settings, we observe fairly small losses in the approximation factors to the first-best GFT and first-best SW due to the existence of the broker (benchmarked against the corresponding approximation factors in the setting without a broker). Furthermore, our results stand in stark contrast to those of [12], who show inapproximability results under a strategic broker with full distributional knowledge. Our results provide insight into the design of data-efficient brokerage mechanisms for online marketplaces and decentralized trading platforms, where intermediaries must facilitate trade under severe informational constraints. They highlight how even minimal data can enable robust and incentive-compatible brokerage in uncertain markets for both the broker and the market participants.
Data powers almost everything we experience on the web today---from the recommendations and ads we see to the AI systems and online marketplaces that shape our digital interactions. The increasing demand for high-quality data has given rise to platforms that facilitate the buying and selling of data. A key practical challenge in such markets is determining how to price data. Competitive equilibrium (CE), a foundational concept in classical market economics, determines prices for rivalrous goods by matching their supply and demand. In this work, we initiate the study of CE in data markets, explicitly incorporating the role of data in improving predictive performance in buyers' utility functions, and the non-rival nature of data by adapting the standard market-clearing condition to allow the simultaneous allocation of data records to multiple buyers. We analyze the existence, structure, and computation of CE in such data markets. We establish that CE always exists, and almost all instances admit a unique and rational equilibrium price vector. In general, however, there could be a non-convex set of prices, which rules out convex-programming approaches for finding a CE. Despite these challenges, we design an FPTAS for computing approximate equilibria using a Walrasian-style price adjustment algorithm. Our framework opens avenues for studying richer buyer utilities under correlated data sellers, and deeper structural and algorithmic aspects of data markets.
In traditional resource/task allocation models, an agent's value on an item is fixed regardless of when, where, or how the agent consumes the item. In this work, we introduce a more general framework involving a set of positions (for example, roles within a company), where agents have valuations that depend on the specific positions they are assigned. This setting is well motivated as the agent faces different resources and support at different positions, and thus may need varying levels of effort to complete the item, supposing the items are chores. We further consider the constrained setting when each item can only be allocated to a certain set of positions (e.g., a research project cannot be assigned to an administrative staff). We particularly consider the case when the constraints form a graph where edges are items and vertices are positions, so an item can only be allocated to an incident position, which is known as the orientation problem [Christodoulou et al. EC 2023]. In this paper, fairness is measured by maximin share (MMS), and efficiency is measured by Pareto and social optimality. We present a complete set of results on the computational complexity and approximation algorithms for computing efficient and fair allocations.
The canonical model for multi-channel marketing, Bandits with Knapsacks (BwK), optimizes cumulative rewards subject to resource constraints but typically assumes a fixed, exogenous budget. This assumption is tenuous in real-world systems requiring performance-adaptive investment, where pre-committing to a budget is challenging and suboptimal. We introduce Marketing Hosting, a paradigm modeling the budget as an endogenous, performance-dependent variable. This yields a new problem class, Bandits with Endogenous Knapsacks (BwEK), characterized by a challenging feedback loop coupling rewards with constraints. We develop a specialized primal-dual algorithm to manage this coupling. For settings with hard, per-round constraints, we design a novel risk-aware algorithm that mitigates the path-dependent risk of ruin, providing the first high-probability safety guarantee for such problems. Finally, we solve the strategic bi-level problem of learning the optimal reinvestment rate. We validate our theoretical results through extensive simulations, real-world data experiments, and a live A/B test.
How hard is it to achieve consensus in a social network under uncertainty? In this paper we model this problem as a social graph of agents where each vertex is initially colored red or blue. The goal of the agents is to achieve consensus, which is when the colors of all agents align. Agents attempt to do this locally through steps in which an agent changes their color to the color of the majority of their neighbors. In real life, agents may not know exactly how many of their neighbors are red or blue, which introduces uncertainty into this process. Modeling uncertainty as perturbations of relative magnitude 1+ε to these color neighbor counts, we show that even small values of \eps greatly hinder the ability to achieve consensus in a social network. We prove theoretically tight upper and lower bounds on the price of uncertainty, a metric defined in previous work by Balcan et al. to quantify the effect of uncertainty in network games.
We study non-atomic congestion games on parallel-link networks with polynomial latencies. We investigate the power of machine-learned predictions in the design of coordination mechanisms aimed at minimizing the impact of selfishness. Our main results demonstrate that enhancing coordination mechanisms with simple advice on the input rate can optimize the social cost whenever the advice is accurate (consistency ), while only incurring minimal losses even when the predictions are arbitrarily inaccurate (bounded robustness ). Moreover, we provide a full characterization of consistent mechanisms, which holds for all monotone cost functions, and show that our proposed mechanism is optimal with respect to robustness. We further explore the notion of error-tolerance within this context, i.e., we provide an approximation guarantee that degrades smoothly as a function of the prediction error, up to a predetermined threshold, while achieving a bounded robustness.
In the secretary problem, a set of secretary candidates arrive in a uniformly random order and reveal their values one by one. A company, who can only hire one candidate and hopes to maximize the expected value of its hire, needs to make irrevocable online decisions about whether to hire the current candidate. The classical framework of evaluating a policy is to compute its worst-case competitive ratio against the optimal solution in hindsight, and there the best policy -- the ''1/e law'' -- has a competitive ratio of 1/e. We propose an alternative evaluation framework through the lens of regret -- the worst-case additive difference between the optimal hindsight solution and the expected performance of the policy, assuming that each value is normalized between 0 and 1. The 1/e law for the classical framework has a regret of 1 - 1/e ≈ 0.632; by contrast, we show that the class of ''pricing curves'' algorithms can guarantee a regret of at most 1/4 = 0.25 (which is tight within the class), and the class of ''best-only pricing curves'' algorithms can guarantee a regret of at most 0.190 (with a lower bound of 0.171). In addition, we show that in general, no policy can give a regret guarantee better than 0.152. Finally, we discuss other objectives in our regret-minimization framework.
Generative AI (GenAI) will have significant impact on content creation platforms. In this paper, we study the dynamic competition between a GenAI and a human contributor. Unlike the human, the GenAI's content only improves when more contents are created by the human over time; however, GenAI has the advantage of generating content at a lower cost. We study the algorithmic problem in this dynamic competition model about how the human contributor can maximize her utility when competing against the GenAI for content generation over a set of topics. In time-sensitive content domains (e.g., news or pop music creation) where contents' value diminishes over time, we show that there is no polynomial time algorithm for finding the human's optimal (dynamic) strategy, unless the randomized exponential time hypothesis is false. Fortunately, we are able to design a polynomial time algorithm that naturally cycles between myopically optimizing over a short time window and pausing and provably guarantees an approximation ratio of 1/2 . We then turn to time-insensitive content domains where contents do not lose their value (e.g., contents on history facts). Interestingly, we show that this setting permits a polynomial time algorithm that maximizes the human's utility in the long run. Finally, we conduct simulations that demonstrate the advantage of our algorithms in comparison to a collection of baselines.
98% of sales on Amazon.com flow through the Buy Box. However, Amazon sometimes decides not to feature any offers for a product and removes the Buy Box from the product page -- a situation known as Buy Box suppression. Suppression may have severe consequences on individual sellers and might affect competition if it disciplines prices across online marketplaces. This paper studies suppression using a new, high-frequency dataset that tracks 17,754 products on Amazon.com at hourly intervals for eight weeks in 2024, along with corresponding offers from 59,301 unique competitors. We open-source both the dataset and collection code. We find that the primary reason for suppression is changes to the offers for a product on Amazon. Lower competitor prices only modestly increase the probability of suppression. Suppression has substantial impacts on sellers: products immediately fall sharply in search, ad placements completely disappear within 12 hours, and sales ranks are 12% worse after 48 hours. In contrast, we find no evidence of impacts on competitor prices in the short run. Our results highlight how Buy Box suppression acts as an important and underexplored mechanism of platform governance.
We consider an extension to classic position auctions in which sponsored creatives are embedded within AI-generated content rather than shown in predefined slots. Leveraging advanced LLM technologies, it becomes viable to seamlessly integrate sponsored creatives with AI content and accurately estimate the context-aware benefits of differing insertion positions. However, this approach introduces novel challenges; substitution effects require rigorous treatment compared to standard position auction settings, where slots are independent of each other. In this work, we formalize a mathematical model of the extended position auction problem and study the welfare- and revenue-maximization mechanism design problems. We assume a specific click-through rate estimation for each position-creative pair and consider two user behavior models: a multinomial logit (MNL) and a cascade model. For the MNL model, which is order-insensitive, we efficiently implement optimal mechanisms. For the cascade model, which is order-sensitive, we provide approximately optimal mechanisms.
The widespread adoption of Large Language Models (LLMs) through Application Programming Interfaces (APIs) induces a critical vulnerability: the potential for dishonest manipulation by service providers. This manipulation can manifest in various forms, such as secretly substituting a proclaimed high-performance model with a low-cost alternative, or inflating responses with meaningless tokens to increase billing. This work tackles the issue through the lens of algorithmic game theory and mechanism design. We are the first to propose a formal economic model for a realistic user-provider ecosystem, where a user can iteratively delegate T queries to multiple model providers, and providers can engage in a range of strategic behaviors. As our central contribution, we prove that for a continuous strategy space and any ε∈(0,1/2), there exists an approximate incentive-compatible mechanism with an additive approximation ratio of O(T1-ε log T), and a guaranteed quasi-linear second-best user utility. We also prove an impossibility result, stating that no mechanism can guarantee an expected user utility that is asymptotically better than our mechanism. Furthermore, we demonstrate the effectiveness of our mechanism in simulation experiments with real-world API settings.
Real-world pricing mechanisms are typically optimized using training data, a setting corresponding to the pricing query complexity problem in Mechanism Design. The previous work [11] studies the single-distribution case1, with tight bounds of ~Θ (ε-3 ) for a general distribution and ~Θ (ε-2 ) for either a regular or monotone-hazard-rate (MHR) distribution, where ε ∈ (0, 1) denotes the (additive) revenue loss of a learned uniform price relative to the Bayesian-optimal uniform price. This can be directly interpreted as ''the query complexity of the Uniform Pricing mechanism, in the single-distribution case''. Yet in the multi-distribution case, can the regularity and MHR conditions still lead to improvements over the tight bound ~Θ (ε-3) for general distributions? We answer this question in the negative, by establishing a (near-)matching lower bound Ømega(ε-3) for either two regular distributions or three MHR distributions. We also address the regret minimization problem and, in comparison with the folklore upper bound ~O(T2/3 ) for general distributions (see, e.g., [13]), establish a (near-)matching lower bound Ømega(T2/3 ) for either two regular distributions or three MHR distributions, via a black-box reduction. Again, this is in stark contrast to the tight bound ~Θ(T1/2 ) for a single regular or MHR distribution.
Identifying high-revenue mechanisms that are both dominant strategy incentive compatible (DSIC) and individually rational (IR) is a fundamental challenge in auction design. While theoretical approaches have encountered bottlenecks in multi-item combinatorial auctions, there has been much empirical progress in the automated design of such mechanisms using machine learning. However, existing research primarily focuses on randomized auctions, with less attention given to more practical deterministic auctions. Therefore, in this paper, we introduce OD-VVCA, an objective decomposition approach for automated designing revenue-maximizing deterministic Virtual Valuations Combinatorial Auctions (VVCAs), which are inherently DSIC and IR. We use a parallelizable dynamic programming algorithm to compute the allocation and revenue outcomes of a VVCA efficiently. We then decompose the revenue objective function into continuous and piecewise-constant discontinuous components, optimizing each using distinct methods. Extensive experiments show that OD-VVCA achieves high revenue in multi-item auctions, especially in large-scale settings where it outperforms both randomized and deterministic baselines, indicating its efficacy and scalability.
Online advertising platforms must decide how to allocate multiple ads across limited screen real estate, where each ad's effectiveness depends not only on its own placement but also on nearby ads competing for user attention. Such spatial externalities — arising from proximity, clutter, or crowding — can significantly alter welfare and revenue outcomes, yet existing auction and allocation models typically treat ad slots as independent or ordered along a single dimension. We introduce a new framework for spatial externalities in online advertising, in which the value of an ad depends on both its slot and the configuration of surrounding ads. We model ad slots as points in a metric space, and model an advertiser's value as a function of both their bid and a discount factor determined by the configuration of other displayed ads. Within this framework, we analyze two natural models. For the Nearest-Neighbor model, where the value suppression depends only on the closest neighboring ad, we present a polynomial-time algorithm that achieves a constant approximation for the general case. We show that the allocation rule is monotone and can be implemented as a truthful mechanism. For a structured setting of 2D Euclidean space, we provide a PTAS. In contrast, for the Product-Distance model, where interference is aggregated multiplicatively across all neighbors, we establish a strong (and nearly-tight) hardness of approximation -- no polynomial-time algorithm can achieve any polynomial-factor approximation unless P=NP, via a reduction from Max-Independent-Set. Our results provide a foundation for reasoning about spatial externalities in ad allocation and for designing efficient, truthful mechanisms under such interactions.
We study two online resource allocation problems with reusability in an adversarial setting, namely \problemkRentalFD and \problemkRentalVD. In both problems, a decision-maker manages k identical reusable units and faces a sequence of rental requests over time. We develop theoretically grounded relax-and-round algorithms with provable competitive ratio guarantees for both settings. For \problemkRentalFD, we present an optimal randomized algorithm that achieves the best possible competitive ratio. The algorithm first computes an optimal fractional allocation using a price-based approach, and then applies a novel lossless online rounding scheme to obtain an integral solution. For \problemkRentalVD, we first establish the impossibility of achieving lossless online rounding. We then introduce a limited-correlation rounding technique that treats each unit independently while introducing controlled dependencies across allocation decisions involving the same unit. Combined with a carefully-crafted price-based method for computing the fractional allocation, this approach yields an order-optimal competitive ratio for the variable-duration setting.
Agents enter barter exchanges to swap items they have for items they want. We study Barter Exchange with Asymmetric Valuations (BAV), a centralized barter exchange where each agent has an individual valuation over items. Given a reallocation of items, let an agent's profit be their received value minus their value given away, according to said agent's valuation of items. The goal of the clearinghouse (the party facilitating the exchange) is to output a reallocation of items that maximizes welfare (sum of agent profits) subject to each agent receiving non-negative profit. BAV is a natural extension of the barter exchange model studied in (Luque et al., WWW '24), which assumes agents necessarily agree on item values. We prove BAV is strongly NP-hard and design a polynomial-time randomized algorithm with optimal expected welfare, non-negative expected profit for every agent, and that, with probability 1, every agent is at most the value of two items away from positive profit. Since valuations may be private and revealed by self-interested agents, we also study BAV from a mechanism design lens.