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.
论文检索
输入标题、作者或关键词，从 954 篇学术成果中精准定位
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.
In online advertising, the inherent complexity and dynamic nature of advertising environments necessitate the use of auto-bidding services to assist advertisers in bid optimization. The complexity escalates in multi-channel scenarios, where effective allocation of budgets and constraints across channels with distinct behavioral patterns becomes critical for optimizing return on investment. Current approaches predominantly employ either optimization-based strategies or reinforcement learning (RL) techniques. However, optimization-based methods lack the flexibility to adapt to dynamic market conditions, while RL-based approaches struggle to capture essential historical dependencies and observational patterns within the constraints of Markov Decision Process (MDP) frameworks. To address these limitations, we propose AHBid, an Adaptable Hierarchical Bidding framework that integrates generative planning with real-time control. The framework employs a high-level generative planner utilizing diffusion models to dynamically allocate budgets and constraints through effective capture of historical context and temporal patterns. We introduce a constraint enforcement mechanism to ensure compliance with specified constraints, complemented by a trajectory refinement mechanism that enhances adaptability to environmental changes through historical data utilization. The system further incorporates a control-based bidding algorithm that synergistically combines historical knowledge with real-time information, significantly improving both adaptability and operational efficacy. Extensive experiments are conducted using both large-scale offline datasets and online A/B tests, demonstrating the effectiveness of AHBid by yielding a 13.57% increase in overall return compared to existing baselines.
We introduce a game-theoretic framework that examines strategic interactions between a platform and its content creators in the presence of AI-generated content. Our model's main novelty is in capturing creators' dual strategic decisions: their investment in content quality and their (possible) consent to share their content with the platform's GenAI, both of which significantly impact their utility. To incentivize creators, the platform strategically allocates a portion of its GenAI-driven revenue to creators who share their content. We focus on the class of full-sharing equilibrium profiles, in which all creators willingly share their content with the platform's GenAI system. Such equilibria are highly desirable both theoretically and practically. Our main technical contribution is formulating and efficiently solving a novel optimization problem that approximates the platform's optimal revenue subject to inducing a full-sharing equilibrium. A key aspect of our approach is identifying conditions under which full-sharing equilibria exist and a surprising connection to the Prisoner's Dilemma. Finally, our simulations demonstrate how revenue-allocation mechanisms affect creator utility and the platform's revenue.
We study the problem of fairly allocating m indivisible chores among n agents with additive cost functions. While the maximin share (MMS) is a prominent fairness criterion in theory, exact MMS allocations do not always exist. This has motivated relaxation that guarantees MMS fairness for only a subset of agents, aiming to maximize the number of satisfied agents. However, for chore allocation, guaranteeing most agents their full MMS is trivial but highly unsatisfactory, e.g., overburdening a single agent, which is undesirable in real-world platforms aiming for user retention and satisfaction. To address this, we propose a stronger and more practical notion called α-approximate all-but-one MMS (α-AMMS), which guarantees that n-1 agents receive their full MMS value, while the remaining agent receives an α-approximation. This model reflects common platform design goals, where satisfying the vast majority of users is critical, and near-fairness for the rest is acceptable. We show that there exist α-AMMS allocations, with α = 9/8 for three agents; α = 4/3 for four agents; and α = (n+1)2/4n for n ≥ 5 agents.
In a web-based review platform, papers from various research fields must be assigned to a group of reviewers. Each paper has an inherent cost, which represents the effort required for reading and evaluating it (e.g., the paper's length). Reviewers can bid on papers they are interested in, and if they are assigned a paper they have bid on, no cost is incurred. Otherwise, the inherent cost c(e) for paper e applies. We capture this with a model of restricted additive costs: every item e has a cost c(e), and each agent either incurs 0 or c(e) for e. In this work, we study how to allocate such chores fairly and efficiently. We propose an algorithm for computing allocations that are both EFX and MMS. Furthermore, we show that our algorithm achieves a 2-approximation of the optimal social cost, and the approximation ratio is optimal. We also show that slightly weaker fairness guarantees can be obtained if one requires the algorithm to run in polynomial time.
We study the voting problem with two alternatives where voters' preferences depend on a not-directly-observable state variable. While equilibria in the one-round voting mechanisms lead to a good decision, they are usually hard to compute and follow. We consider the two-round voting mechanism where the first round serves as a polling stage and the winning alternative only depends on the outcome of the second round. We show that the two-round voting mechanism is a powerful tool for making collective decisions. Firstly, every (approximated) equilibrium in the two-round voting mechanisms (asymptotically) leads to the decision preferred by the majority as if the state of the world were revealed to the voters. Moreover, there exist natural equilibria in the two-round game following intuitive behaviors such as informative voting, sincere voting, and surprisingly popular strategies. This sharply contrasts with the one-round voting mechanisms in the previous literature, where no simple equilibrium is known. Finally, we show that every equilibrium in the standard one-round majority vote mechanism gives an equilibrium in the two-round mechanisms that is not more complicated. Therefore, the two-round voting mechanism provides a natural equilibrium in every instance, including those where one-round voting fails, and it can reach an informed majority decision whenever one-round voting can. Our experiments on LLM voters also imply that two-round voting leads to the correct outcome more often than one-round voting under some circumstances.
We investigate majority voting where agents possess private information about an unobservable ground truth that determines their preferences. In such settings, agents may hold different preferences and (collectively) engage in counterintuitive strategic behaviors. Previous work either assumes strategic behavior occurs without coordination or with unlimited coordination, yielding overly inclusive or exclusive predictions about voting outcomes. We incorporate coordination ability—the largest coalition size at which agents could strategically coordinate—into the analysis. Under the ex-ante Bayesian k-strong equilibrium framework, where no group of at most k agents can benefit from deviation, we provide closed-form characterizations of when informed majority decisions, the decision favored by the majority if the ground truth is common knowledge, are achievable. Specifically, we determine (1) when all k-strong equilibria reach the informed majority decision and (2) when at least one such equilibrium exists. These conditions depend on three factors: coordination ability, fraction of majority agents, and information structure. The boundary for the second question exhibits surprising complexity--non-continuous, non-linear, and segmental. Our results reveal the complicated landscape and provide refined predictions for strategic behavior across different coordination levels.