A canonical setting for non-monetary online resource allocation is one where agents compete over multiple rounds for a single item per round, with i.i.d. valuations and additive utilities across rounds. With $n$ symmetric agents, a natural benchmark for each agent is the utility realized by her favorite $1/n$-fraction of rounds; a line of work has demonstrated one can robustly guarantee each agent a constant fraction of this ideal utility, irrespective of how other agents behave. In particular, several mechanisms have been shown to be $1/2$-robust, and recent work established that repeated first-price auctions based on artificial credits have a robustness factor of $0.59$, which cannot be improved beyond $0.6$ using first-price and simple strategies. In contrast, even without strategic considerations, the best achievable factor is $1-1/e\approx 0.63$. In this work, we break the $0.6$ first-price barrier to get a new $0.625$-robust mechanism, which almost closes the gap to the non-strategic robustness bound. Surprisingly, we do so via a simple auction, where in each round, bidders decide if they ask for the item, and we allocate uniformly at random among those who ask. The main new ingredient is the idea of competitive subsidies, wherein we charge the winning agent an amount in artificial credits that decreases when fewer agents are bidding (specifically, when $k$ agents bid, then the winner pays proportional to $k/(k+1)$, varying the payment by a factor of 2 depending on the competition). Moreover, we show how it can be modified to get an equilibrium strategy with a slightly weaker robust guarantee of $5/(3e) \approx 0.61$ (and the optimal $1-1/e$ factor at equilibrium). Finally, we show that our mechanism gives the best possible bound under a wide class of auction-based mechanisms.

We consider repeated allocation of a shared resource via a non-monetary mechanism, wherein a single item must be allocated to one of multiple agents in each round. We assume that each agent has i.i.d. values for the item across rounds, and additive utilities. Past work on this problem has proposed mechanisms where agents can get one of two kinds of guarantees: (\(i\)) (approximate) Bayes-Nash equilibria via linkage-based mechanisms which need extensive knowledge of the value distributions, and (\(ii\)) simple distribution-agnostic mechanisms with robust utility guarantees for each individual agent, which are worse than the Nash outcome, but hold irrespective of how others behave (including possibly collusive behavior). Recent work has hinted at barriers to achieving both simultaneously. Our work however establishes this is not the case, by proposing the first mechanism in which each agent has a natural strategy that is both a Bayes-Nash equilibrium and also comes with strong robust guarantees for individual agent utilities. Our mechanism comes out of a surprising connection between the online shared resource allocation problem and implementation theory, and uses a surprising strengthening of Border’s theorem. In particular, we show that establishing robust equilibria in this setting reduces to showing that a particular subset of the Border polytope is non-empty. We establish this via a novel joint Schurconvexity argument. This strengthening of Border’s criterion for obtaining a stronger conclusion is of independent technical interest, as it may prove useful in other settings.

We study the problem of fair online resource allocation via non-monetary mechanisms, where multiple agents repeatedly share a resource without monetary transfers. Previous work has shown that every agent can guarantee 1/2 of their ideal utility (the highest achievable utility given their fair share of resources) robustly, i.e., under arbitrary behavior by the other agents. While this 1/2-robustness guarantee has now been established under very different mechanisms, including pseudo-markets and dynamic max-min allocation, improving on it has appeared difficult. In this work, we obtain the first significant improvement on the robustness of online resource sharing. In more detail, we consider the widely-studied repeated first-price auction with artificial currencies. Our main contribution is to show that a simple randomized bidding strategy can guarantee each agent a 2 - √2 ≈ 0.59 fraction of her ideal utility, irrespective of others' bids. Specifically, our strategy requires each agent with fair share α to use a uniformly distributed bid whenever her value is in the top α-quantile of her value distribution. Our work almost closes the gap to the known 1 - 1/e ≈ 0.63 hardness for robust resource sharing; we also show that any static (i.e., budget independent) bidding policy cannot guarantee more than a 0.6-fraction of the ideal utility, showing our technique is almost tight.

We consider the classical Dynamic Max-min fair (DMMF) mechanism for allocating an indivisible resource without money over multiple agents and T rounds. We show that under mild assumption on value distributions, it guarantees every agent close to optimal utility in large markets.

In this paper, we introduce a novel approach to repeated auctions that accounts for bidders' temporal preferences, important in applications such as advertising. In our model, when a player wins an auction after not winning for ℓ rounds, she is awarded r(ℓ) utility and her goal is to maximize her total utility. r : ℕ → ℝ ≥0 satisfies the following properties. (i) The more rounds without a win, the higher the reward, i.e., r is weakly increasing. (ii) As more rounds pass without winning, the increase in reward becomes smaller, i.e., r is concave. The motivation behind these properties comes from the advertising literature, which states that an increased frequency of winning builds advertising effectiveness at a decreasing (but not declining) rate. The above properties guarantee that adding more wins to any sequence of winning intervals increases the total reward.

Advertisers are increasingly using automated bidding to optimize their ad campaigns on online advertising platforms. Autobidding allows an advertiser to optimize her objective subject to various constraints. In this paper, we design online autobidding algorithms to optimize value subject to ROI and budget constraints.

Bandits with Knapsacks (BwK), the generalization of the Multi-Armed Bandits problem under global budget constraints, has received a lot of attention in recent years. It has numerous applications, including dynamic pricing, repeated auctions, ad allocation, network scheduling, etc. Previous work has focused on one of the two extremes: Stochastic BwK where the rewards and consumptions of the resources of each round are sampled from an i.i.d. distribution, and Adversarial BwK where these parameters are picked by an adversary. Achievable guarantees in the two cases exhibit a massive gap: No-regret learning is achievable in the stochastic case, but in the adversarial case only competitive ratio style guarantees are achievable, where the competitive ratio depends either on the budget or on both the time and the number of resources. What makes this gap so vast is that in Adversarial BwK the guarantees get worse in the typical case when the budget is more binding. While “best-of-both-worlds” type algorithms are known (single algorithms that provide the best achievable guarantee in each extreme case), their bounds degrade to the adversarial case as soon as the environment is not fully stochastic.Our work aims to bridge this gap, offering guarantees for a workload that is not exactly stochastic but is also not worst-case. We define a condition, Approximately Stationary BwK, that parameterizes how close to stochastic or adversarial an instance is. Based on these parameters, we explore what is the best competitive ratio attainable in BwL. We explore two algorithms that are oblivious to the values of the parameters but guarantee competitive ratios that smoothly transition between the best possible guarantees in the two extreme cases, depending on the values of the parameters. Our guarantees offer great improvement over the adversarial guarantee, especially when the available budget is small. We also prove bounds on the achievable guarantee, showing that our results are approximately tight when the budget is small.

We study non-monetary mechanisms for the fair and efficient allocation of reusable public resources. We consider settings where a limited resource is repeatedly shared among a set of agents, each of whom may request to use the resource over multiple consecutive rounds, receiving some utility only if they get to use the resource for the full duration of their request. Such settings are of particular significance in scientific research where large-scale instruments such as electron microscopes, particle colliders, or telescopes are shared between multiple research groups; this model also subsumes and extends existing models of repeated non-monetary allocation where the resource is demanded only for a single round.

We study the liquid welfare in sequential first-price auctions with budget-limited buyers. We focus on first-price auctions, which are increasingly commonly used in many settings, and consider liquid welfare, a natural and well-studied generalization of social welfare for the case of budget-constrained buyers. We use a behavioral model for the buyers, assuming a learning style guarantee: the resulting utility of each buyer is within a γ factor (where γ ≥ 1) of the utility achievable by shading her value with the same factor at each iteration. Under this assumption, we show a γ + 1/2 + O(1/γ) price of anarchy for liquid welfare assuming buyers have additive valuations. This positive result is in stark contrast to sequential second-price auctions, where even with γ = 1, the resulting liquid welfare can be arbitrarily smaller than the maximum liquid welfare, even though the latter can be achieved by a constant shading factor. We prove a lower bound of γ on the liquid welfare loss under the above assumption in first-price auctions, making our bound asymptotically tight. For the case when γ = 1 our theorem implies a price of anarchy upper bound that is about 2.41; we show a lower bound of 2 for that case.

In the maritime domain, vessels typically maintain straight, predictable routes at open sea, except in the rare cases of adverse weather conditions, accidents and traffic restrictions. Consequently, large amounts of streaming positional updates from vessels can hardly contribute additional knowledge about their actual motion patterns. We have been developing a system for vessel trajectory compression discarding a significant part of the original positional updates, with minimal trajectory reconstruction error. In this work, we present an extension of this system, that allows the user to fine-tune trajectory compression according to the requirements of a given application. The extended system avoids the issues of hyper-parameter tuning, supports incremental optimization and facilitates composite maritime event recognition. Finally, we report empirical results from a comprehensive empirical evaluation against two real-world datasets of vessel positions.

In previous work we introduced a trajectory detection module that can provide summarized representations of vessel trajectories by consuming AIS positional messages online. This methodology can provide reliable trajectory synopses with little deviations from the original course by discarding at least 70% of the raw data as redundant. However, such trajectory compression is very sensitive to parametrization. In this paper, our goal is to fine-tune the selection of these parameter values. We take into account the type of each vessel in order to provide a suitable configuration that can yield improved trajectory synopses, both in terms of approximation error and compression ratio. Furthermore, we employ a genetic algorithm converging to a suitable configuration per vessel type. Our tests against a publicly available AIS dataset have shown that compression efficiency is comparable or even better than the one with default parametrization without resorting to a laborious data inspection.