In this paper we design information elicitation mechanisms for Bayesian auctions. While in Bayesian mechanism design the distributions of the players’ private types are often assumed to be common knowledge, information elicitation considers the situation where the players know the distributions better than the decision maker. To weaken the information assumption in Bayesian auctions, we consider an information structure where the knowledge about the distributions is arbitrarily scattered among the players. In such an unstructured information setting, we design mechanisms for unit-demand auctions and additive auctions that aggregate the players’ knowledge, generating revenue that are constant approximations to the optimal Bayesian mechanisms with a common prior. Our mechanisms are 2-step dominant-strategy truthful, and the approximation ratios improve gracefully with the amount of knowledge the players collectively have.

We study a new class of contract design problems where a principal delegates the execution of multiple projects to a set of agents. The principal's expected reward from each project is a combinatorial function of the agents working on it. Each agent has limited capacity and can work on at most one project, and the agents are heterogeneous, with different costs and contributions for participating in different projects. The main challenge of the principal is to decide how to allocate the agents to projects when the number of projects grows in scale.

We quantify the value of the monopoly's bargaining power in terms of competition complexity—that is, the number of additional bidders the monopoly must attract in simple auctions to match the expected revenue of the optimal mechanisms —within the setting of multi-item auctions. We show that for simple auctions that sell items separately, the competition complexity is Θ(n/α) in an environment with n original bidders under the slightly stronger assumption of α-strong regularity, in contrast to the standard regularity assumption in the literature, which requires Ω (n · ln m/n) additional bidders. This significantly reduces the value of learning the distribution to design the optimal mechanisms, especially in large markets with many items for sale. For simple auctions that sell items as a grand bundle, we establish a constant competition complexity bound in a single-bidder environment when the number of items is small or when the value distribution has a monotone hazard rate. Some of our competition complexity results also hold when we compete against the first best benchmark (i.e., optimal social welfare).

Abstract In this paper we design information elicitation mechanisms for Bayesian auctions. While in Bayesian mechanism design the distributions of the players’ private types are often assumed to be common knowledge, information elicitation considers the situation where the players know the distributions better than the decision maker. To weaken the information assumption in Bayesian auctions, we consider an information structure where the knowledge about the distributions is arbitrarily scattered among the players. In such an unstructured information setting, we design mechanisms for unit-demand auctions and additive auctions that aggregate the players’ knowledge, generating revenue that are constant approximations to the optimal Bayesian mechanisms with a common prior. Our mechanisms are 2-step dominant-strategy truthful and the approximation ratios improve gracefully with the amount of knowledge the players collectively have.

Classical auction theory typically focuses on models with exogenous signal structures, where all auction participants privately know their item valuations. However, practical scenarios often find buyers initially uninformed about their item values due to the lack of data on item quality or suitability. Instead, buyers rely on seller advertisements to learn their values. For instance, streaming services offer free trials to influence consumer perceptions before subscriptions, while real estate agencies provide property inspections for better buyer estimations.

This paper concerns the design of contracts to incentivize experts to acquire information for predicting a future state when doing so is costly and when this information acquisition is private. This problem may arise in a variety of situations, often when the contract designer expects to make a high-stakes decision---for instance, whether to launch a military attack in response to a perceived threat, whether to make a sizable investment, or whether to approve a risky vaccine to fight a budding pandemic. In these cases, whether a given action is best (e.g., invasion, investment, approval, respectively, for the above examples) may depend on the underlying state, which we will take as binary in this paper for simplicity. Notice that this problem features the combination of moral hazard (since the principal cannot monitor the expert's effort) and endogenous adverse selection (since the expert's actions generate private information).

We study mechanisms for selling a single item when buyers have private costs for participating in the mechanism. An agent's participation cost can also be interpreted as an outside option value that she must forego to participate. This substantially changes the revenue maximization problem, which becomes non- convex in the presence of participation costs. For multiple buyers, we show how to construct a (2 + ɛ)- approximately revenue-optimal mechanism in polynomial time. Our approach makes use of a many-buyers-to-single-buyer reduction, and in the single-buyer case our mechanism improves to an FPTAS. We also bound the menu size and the sample complexity for the optimal single-buyer mechanism. Moreover, we show that posting a single price in the single-buyer case is in fact optimal under the assumption that either (1) the participation cost is independent of the value, and the value distribution has decreasing marginal revenue or monotone hazard rate; or (2) the participation cost is a concave function of the value. When there are multiple buyers, we show that sequential posted pricing guarantees a large fraction of the optimal revenue under similar conditions.

In the context of emerging 6G technology challenges, this paper introduces the LSMFF-AMC approach, leveraging multimodal feature fusion (MFF) with Long-Short range attention (LSRA) to enhance automatic modulation classification(AMC). The method significantly boosts classification accuracy by employing convolutional neural networks (CNN) for diverse modal feature extraction and integrating LSRA for comprehensive feature combination. Our experiments demonstrate an increase in accuracy from 88% to nearly 97%, outperforming traditional single-modal approaches. Additionally, a convergence analysis of the training loss function reveals LSMFF-AMC's superior and faster convergence compared to standard AMC methods.

We study the linear contextual bandit problem with finite action sets. When the problem dimension is$d$, the time horizon is$T$, and there are$n \leq 2^{d/2}$candidate actions per time period, we 1) show that the minimax expected regret is$\Omega (\sqrt {dT (\log T) (\log n)})$for every algorithm, and 2) introduce a Variable-Confidence-Level (VCL) SupLinUCB algorithm whose regret matches the lower bound up to iterated logarithmic factors. Our algorithmic result saves two$\sqrt {\log T}$factors from previous analysis, and our information-theoretical lower bound also improves previous results by one$\sqrt {\log T}$factor, revealing a regret scaling quite different from classical multi-armed bandits in which no logarithmic$T$term is present in minimax regret. Our proof techniques include variable confidence levels and a careful analysis of layer sizes of SupLinUCB on the upper bound side, and delicately constructed adversarial sequences showing the tightness of elliptical potential lemmas on the lower bound side.

This paper develops a framework for the design of scoring rules to optimally incentivize an agent to exert a multi-dimensional effort. This framework is a generalization to strategic agents of the classical knapsack problem (cf. Briest, Krysta, and Vocking, 2005; Singer, 2010) and it is foundational to applying algorithmic mechanism design to the classroom. The paper identifies two simple families of scoring rules that guarantee constant approximations to the optimal scoring rule. The truncated separate scoring rule is the sum of single dimensional scoring rules that is truncated to the bounded range of feasible scores. The threshold scoring rule gives the maximum score if reports exceed a threshold and zero otherwise. Approximate optimality of one or the other of these rules is similar to the bundling or selling separately result of Babaioff, Immorlica, Lucier, and Weinberg (2014). Finally, we show that the approximate optimality of the best of those two simple scoring rules is robust when the agent’s choice of effort is made sequentially.

A prevalent assumption in auction theory is that the auctioneer has full control over the market and that the allocation she dictates is final. In practice, however, agents might be able to resell acquired items in an aftermarket. A prominent example is the market for carbon emission allowances. These allowances are commonly allocated by the government using uniform-price auctions, and firms can typically trade these allowances among themselves in an aftermarket that may not be fully under the auctioneer's control. While the uniform-price auction is approximately efficient in isolation, we show that speculation and resale in aftermarkets might result in a significant welfare loss. Motivated by this issue, we consider three approaches, each ensuring high equilibrium welfare in the combined market. The first approach is to adopt smooth auctions such as discriminatory auctions. This approach is robust to correlated valuations and to participants acquiring information about others' types. However, discriminatory auctions have several downsides, notably that of charging bidders different prices for identical items, resulting in fairness concerns that make the format unpopular. Two other approaches we suggest are either using posted-pricing mechanisms, or using uniform-price auctions with anonymous reserves. We show that when using balanced prices, both these approaches ensure high equilibrium welfare in the combined market. The latter also inherits many of the benefits from uniform-price auctions such as price discovery, and can be introduced with a minor modification to auctions currently in use to sell carbon emission allowances.

Online advertising via auctions increasingly dominates the marketing landscape. A typical advertiser may participate in thousands of auctions each day with bids tailored to a variety of signals about user demographics and intent. These auctions are strategically linked through a global budget constraint. To help address the difficulty of bidding, many major online platforms now provide automated budget management via a flexible approach called budget pacing: rather than bidding directly, an advertiser specifies a global budget target and a maximum willingness-to-pay for different types of advertising opportunities. The specified maximums are then scaled down (or "paced") by a multiplier so that the realized total spend matches the target budget. These automated bidders are now near-universally adopted across all mature advertising platforms, raising pressing questions about market outcomes that arise when advertisers use budget pacing simultaneously. In this paper we study the aggregate welfare and individual regret guarantees of dynamic pacing algorithms in repeated auctions with budgets. We show that when agents simultaneously use a natural form of gradient-based pacing, the liquid welfare obtained over the course of the dynamics is at least half the optimal liquid welfare obtainable by any allocation rule, matching the best possible bound for static auctions even in pure Nash equilibria [Aggarwal et al., WINE 2019; Babaioff et al., ITCS 2021]. In contrast to prior work, these results hold without requiring convergence of the dynamics, circumventing known computational obstacles of finding equilibria [Chen et al., EC 2021]. Our result is robust to the correlation structure among agents' valuations and holds for any core auction, a broad class that includes first-price, second-price, and GSP auctions. We complement the aggregate guarantees by showing that an agent using such pacing algorithms achieves an O(T^{3/4}) regret relative to the value obtained by the best fixed pacing multiplier in hindsight in stochastic bidding environments. Compared to past work, this result applies to more general auctions and extends to adversarial settings with respect to dynamic regret.

We study a generalization of both the classic single-dimensional mechanism design problem, and the hidden-action principal-agent problem of contract theory [c.f., Alon et al. 2021]. In this setting, the principal seeks to incentivize an agent with a private Bayesian type to take a costly action. The goal is to design an incentive compatible menu of contracts which maximizes the expected revenue.

We show that economic conclusions derived from Bulow and Roberts (1989) for linear utility models approximately extend to non-linear utility models. Specifically, we quantify the extent to which agents with non-linear utilities resemble agents with linear utilities, and we show that the approximation of mechanisms for agents with linear utilities approximately extend for agents with non-linear utilities. We illustrate the framework for the objectives of revenue and welfare on non-linear models that include agents with budget constraints, agents with risk aversion, and agents with endogenous valuations. We derive bounds on how much these models resemble the linear utility model and combine these bounds with well-studied approximation results for linear utility models. We conclude that simple mechanisms are approximately optimal for these non-linear agent models. * The full version of the paper can be accessed at https://arxiv.org/abs/2003.00545. This work is support by NSF CCF AF #1618502.

We study a fair resource sharing problem, where a set of resources are to be shared among a group of agents. Each agent demands one resource and each resource can serve a limited number of agents. An agent cares about what resource they get as well as the externalities imposed by their mates, who share the same resource with them. Clearly, the strong notion of envy-freeness, where no agent envies another for their resource or mates, cannot always be achieved and we show that even deciding the existence of such a strongly envy-free assignment is an intractable problem. Hence, a more interesting question is whether (and in what situations) a relaxed notion of envy-freeness, the Pareto envyfreeness, can be achieved. Under this relaxed notion, an agent envies another only when they envy both the resource and the mates of the other agent. In particular, we are interested in a dorm assignment problem, where students are to be assigned to dorms with the same capacity and they have dichotomous preference over their dormmates. We show that when the capacity of each dorm is 2, a Pareto envy-free assignment always exists and we present a polynomial-time algorithm to compute such an assignment. Nevertheless, the result breaks immediately when the capacity increases to 3, in which case even Pareto envyfreeness cannot be guaranteed. In addition to the existential results, we also investigate the utility guarantees of (Pareto) envy-free assignments in our model.

Designing dominant-strategy incentive compatible (DSIC) mechanisms for a seller to generate (approximately) optimal revenue by selling items to players is a fundamental problem in Bayesian mechanism design. However, most existing studies assume that the seller knows the entire distribution from which the players’ values are drawn. Unfortunately, this assumption may not hold in reality: for example, when the distributions have exponentially large supports or do not have succinct representations. In this work we consider, for the first time, the query complexityof Bayesian mechanisms. The seller only has limited oracle accesses to the players’ distributions, via quantile queriesand value queries. For single-item auctions, we design mechanisms with logarithmicnumber of value or quantile queries which achieve almost optimal revenue. We then prove logarithmic lower-bounds, i.e., logarithmic number of queries are necessary for any constant approximation DSIC mechanisms, even when randomized and adaptive queries are allowed. Thus our mechanisms are almost optimal regarding query complexity. Our lower-bounds can be extended to multi-item auctions with monotone subadditive valuations, and we complement this part with constant approximation mechanisms for unit-demand or additive valuation functions. Our results are robust even if the answers to the queries contain noises.

We consider the model of the data broker selling information to a single agent to maximize his revenue. The agent has private valuation for the additional information, and upon receiving the signal from the data broker, the agent can conduct her own experiment to refine her posterior belief on the states with additional costs. In this paper, we show that in the optimal mechanism, the agent has no incentive to acquire any additional costly information under equilibrium. Still, the ability to acquire additional information distorts the incentives of the agent, and reduces the optimal revenue of the data broker. Moreover, assuming the valuation functions are linear, we fully characterize the revenue optimal mechanisms, which in general may be complex and contain a continuum of menu entries. However, we show that posting a deterministic price for revealing the states obtains at least half of the optimal revenue for arbitrary prior and cost functions. This leads to a sharp contrast to the exogenous information setting where the menu complexity can be unbounded for approximating the optimal revenue.

This paper introduces an objective for optimizing proper scoring rules. The objective is to maximize the increase in payoff of a forecaster who exerts a binary level of effort to refine a posterior belief from a prior belief. In this framework we characterize optimal scoring rules in simple settings, give efficient algorithms for computing optimal scoring rules in complex settings, and identify simple scoring rules that are approximately optimal. In comparison, standard scoring rules in theory and practice -- for example the quadratic rule, scoring rules for the expectation, and scoring rules for multiple tasks that are averages of single-task scoring rules -- can be very far from optimal.

In this paper, we study how to fairly allocate a set of indivisible chores to a number of (asymmetric) agents with additive cost functions. We consider the fairness notion of (weighted) proportionality up to any item (PROPX), and show that a (weighted) PROPX allocation always exists and can be computed efficiently. We also consider the partial information setting, where the algorithms can only use agents’ ordinal preferences. We design algorithms that achieve 2-approximate (weighted) PROPX, and the approximation ratio is optimal. We complement the algorithmic results by investigating the relationship between (weighted) PROPX and other fairness notions such as maximin share and AnyPrice share, and bounding the social welfare loss by enforcing the allocations to be (weighted) PROPX.

Linear contextual bandit is a class of sequential decision-making problems with important applications in recommendation systems, online advertising, healthcare, and other machine learning-related tasks. While there is much prior research, tight regret bounds of linear contextual bandit with infinite action sets remain open. In this paper, we consider the linear contextual bandit problem with (changing) infinite action sets. We prove a regret upper bound on the order of O(\sqrt{d^2T\log T}) \poly(\log\log T) where d is the domain dimension and T is the time horizon. Our upper bound matches the previous lower bound of \Omega(\sqrt{d^2 T\log T}) in [Li et al., 2019] up to iterated logarithmic terms.

This paper considers prior-independent mechanism design, in which a single mechanism is designed to achieve approximately optimal performance on every prior distribution from a given class. Most results in this literature focus on mechanisms with truthtelling equilibria, a.k.a., truthful mechanisms. Feng and Hartline [FOCS 2018] introduce the revelation gap to quantify the loss of the restriction to truthful mechanisms. We solve a main open question left in Feng and Hartline [FOCS 2018]; namely, we identify a non-trivial revelation gap for revenue maximization.

This paper compares two leading approaches for robust optimization in the models of online algorithms and mechanism design. Competitive analysis compares the performance of an online algorithm to an offline benchmark in worst-case over inputs, and prior-independent mechanism design compares the expected performance of a mechanism on an unknown distribution (of inputs, i.e., agent values) to the optimal mechanism for the distribution in worst case over distributions. For competitive analysis, a critical concern is the choice of benchmark. This paper gives a method for selecting a good benchmark. We show that optimal algorithm/mechanism for the optimal benchmark is equal to the prior-independent optimal algorithm/mechanism. We solve a central open question in prior-independent mechanism design, namely we identify the prior-independent revenue-optimal mechanism for selling a single item to two agents with i.i.d. and regularly distributed values. We use this solution to solve the corresponding benchmark design problem. Via this solution and the above equivalence of prior-independent mechanism design and competitive analysis (a.k.a. prior-free mechanism design) we show that the standard method for lower bounds of prior-free mechanisms is not generally tight for the benchmark design program.11For the full version of this work, see https://arxiv.org/abs/2001.10157.

We study multinomial logit bandit with limited adaptivity, where the algorithms change their exploration actions as infrequently as possible when achieving almost optimal minimax regret. We propose two measures of adaptivity: the assortment switching cost and the more fine-grained item switching cost. We present an anytime algorithm (AT-DUCB) with $O(N \log T)$ assortment switches, almost matching the lower bound $\Omega(\frac{N \log T}{ \log \log T})$. In the fixed-horizon setting, our algorithm FH-DUCB incurs $O(N \log \log T)$ assortment switches, matching the asymptotic lower bound. We also present the ESUCB algorithm with item switching cost $O(N \log^2 T)$.

We study the linear contextual bandit problem with finite action sets. When the problem dimension is $d$, the time horizon is $T$, and there are $n \leq 2^{d/2}$ candidate actions per time period, we (1) show that the minimax expected regret is $\Omega(\sqrt{dT \log T \log n})$ for every algorithm, and (2) introduce a Variable-Confidence-Level (VCL) SupLinUCB algorithm whose regret matches the lower bound up to iterated logarithmic factors. Our algorithmic result saves two $\sqrt{\log T}$ factors from previous analysis, and our information-theoretical lower bound also improves previous results by one $\sqrt{\log T}$ factor, revealing a regret scaling quite different from classical multi-armed bandits in which no logarithmic $T$ term is present in minimax regret. Our proof techniques include variable confidence levels and a careful analysis of layer sizes of SupLinUCB on the upper bound side, and delicately constructed adversarial sequences showing the tightness of elliptical potential lemmas on the lower bound side.

We study how to maximize the broker's (expected) profit in a two-sided market, where she buys items from a set of sellers and resells them to a set of buyers. Each seller has a single item to sell and holds a private value on her item, and each buyer has a valuation function over the bundles of the sellers' items. We consider the Bayesian setting where the agents' values/valuations are independently drawn from prior distributions, and aim at designing dominant-strategy incentive-compatible (DSIC) mechanisms that are approximately optimal. Production-cost markets, where each item has a publicly-known cost to be produced, provide a platform for us to study two-sided markets. Briefly, we show how to covert a mechanism for production-cost markets into a mechanism for the broker, whenever the former satisfies cost-monotonicity. This reduction holds even when buyers have general combinatorial valuation functions. When the buyers' valuations are additive, we generalize an existing mechanism to production-cost markets in an approximation-preserving way. We then show that the resulting mechanism is cost-monotone and thus can be converted into an 8-approximation mechanism for two-sided markets.

The dispersion problem has been widely studied in computational geometry and facility location and is closely related to the packing problem. The goal is to locate $n$ points (e.g., facilities or persons) in a $k$-dimensional polytope, so that they are far away from each other and from the boundary of the polytope. In many real-world scenarios, however, the points arrive and depart at different times, and decisions must be made without knowing future events. Therefore, we study, for the first time in the literature, the online dispersion problem in Euclidean space. There are two natural objectives when time is involved: the all-time worst-case (ATWC) problem tries to maximize the minimum distance that ever appears at any time; and the cumulative distance (CD) problem tries to maximize the integral of the minimum distance throughout the whole time interval. Interestingly, the online problems are highly nontrivial even on a segment. For cumulative distance, this remains the case even when the problem is time-dependent but offline, with all the arriving and departure times given in advance. For the online ATWC problem on a segment, we construct a deterministic polynomial-time algorithm which is $(2\ln 2+\epsilon)$-competitive, where $\epsilon>0$ can be arbitrarily small and the algorithm's running time is polynomial in $\frac{1}{\epsilon}$. We show that this algorithm is actually optimal. For the same problem in a square, we provide a $1.591$-competitive algorithm and a $1.183$ lower bound. Furthermore, for arbitrary $k$-dimensional polytopes with $k\geq 2$, we provide a $\frac{2}{1-\epsilon}$-competitive algorithm and a $\frac{7}{6}$ lower bound. All our lower bounds come from the structure of the online problems and hold even when computational complexity is not a concern. Interestingly, for the offline CD problem in arbitrary $k$-dimensional polytopes, we provide a polynomial-time black-box reduction to the online ATWC problem, and the resulting competitive ratio increases by a factor of at most 2. Our techniques also apply to online dispersion problems with different boundary conditions.

Generating good revenue is one of the most important problems in Bayesian auction design, and many (approximately) optimal dominant-strategy incentive compatible (DSIC) Bayesian mechanisms have been constructed for various auction settings. However, most existing studies do not consider the complexity for the seller to carry out the mechanism. It is assumed that the seller knows "each single bit" of the distributions and is able to optimize perfectly based on the entire distributions. Unfortunately this is a strong assumption and may not hold in reality: for example, when the value distributions have exponentially large supports or do not have succinct representations. In this work we consider, for the first time, the query complexity of Bayesian mechanisms. We only allow the seller to have limited oracle accesses to the players' value distributions, via quantile queries and value queries. For a large class of auction settings, we prove logarithmic lower-bounds for the query complexity for any DSIC Bayesian mechanism to be of any constant approximation to the optimal revenue. For single-item auctions and multi-item auctions with unit-demand or additive valuation functions, we prove tight upper-bounds via efficient query schemes, without requiring the distributions to be regular or have monotone hazard rate. Thus, in those auction settings the seller needs to access much less than the full distributions in order to achieve approximately optimal revenue.

In this paper, we focus on how to dynamically allocate a divisible resource fairly among n players who arrive and depart over time. The players may have general heterogeneous valuations over the resource. It is known that the exact envy-free and proportional allocations may not exist in the dynamic setting [Walsh, 2011]. Thus, we will study to what extent we can guarantee the fairness in the dynamic setting. We first design two algorithms which are O(log n)-proportional and O(n)-envy-free for the setting with general valuations, and by constructing the adversary instances such that all dynamic algorithms must be at least Omega(1)-proportional and Omega(n/log n)-envy-free, we show that the bounds are tight up to a logarithmic factor. Moreover, we introduce the setting where the players' valuations are uniform on the resource but with different demands, which generalize the setting of [Friedman et al., 2015]. We prove an O(log n) upper bound and a tight lower bound for this case.

The dispersion problem has been widely studied in computational geometry and facility location, and is closely related to the packing problem. The goal is to locate n points (e.g., facilities or persons) in a k-dimensional polytope, so that they are far away from each other and from the boundary of the polytope. In many real-world scenarios however, the points arrive and depart at different times, and decisions must be made without knowing future events. Therefore we study, for the first time in the literature, the online dispersion problem in Euclidean space. There are two natural objectives when time is involved: the all-time worst-case (ATWC) problem tries to maximize the minimum distance that ever appears at any time; and the cumulative distance (CD) problem tries to maximize the integral of the minimum distance throughout the whole time interval. Interestingly, the online problems are highly non-trivial even on a segment. For cumulative distance, this remains the case even when the problem is time-dependent but offline, with all the arriving and departure times given in advance. For the online ATWC problem on a segment, we construct a deterministic polynomial-time algorithm which is (2ln2+epsilon)-competitive, where epsilon>0 can be arbitrarily small and the algorithm's running time is polynomial in 1/epsilon. We show this algorithm is actually optimal. For the same problem in a square, we provide a 1.591-competitive algorithm and a 1.183 lower-bound. Furthermore, for arbitrary k-dimensional polytopes with k>=2, we provide a 2/(1-epsilon)-competitive algorithm and a 7/6 lower-bound. All our lower-bounds come from the structure of the online problems and hold even when computational complexity is not a concern. Interestingly, for the offline CD problem in arbitrary k-dimensional polytopes, we provide a polynomial-time black-box reduction to the online ATWC problem, and the resulting competitive ratio increases by a factor of at most 2. Our techniques also apply to online dispersion problems with different boundary conditions.