We study the problem of regret minimization for a single bidder in sequence first-price auctions where discovers item's value only if auction is won. Our main contribution complete characterization, up to logarithmic factors, minimax terms auction's transparency, which controls amount information on competing bids disclosed by auctioneer at end each auction. results hold under different assumptions (stochastic, adversarial, and their smoothed variants) environment generating bidder's...

In this data article, we present a dataset made up of personal, social and clinical records related to patients undergoing rehabilitation program. Data refers registered in the "Acceptance/Discharge Report for area" (ADR) which implements Italian law (DGR 731/2005) refer hospitalization at hospital Rome "San Raffaele" years from 2015 2018 suffering orthopedic neurological pathologies. For each ADR report, status patient date acceptance discharge is reported using, among other, Barthel index...

Constrained submodular maximization problems encompass a wide variety of applications, including personalized recommendation, team formation, and revenue via viral marketing. The massive instances occurring in modern-day applications can render existing algorithms prohibitively slow. Moreover, frequently those are also inherently stochastic. Focusing on these challenges, we revisit the classic problem maximizing (possibly non-monotone) function subject to knapsack constraint. We present...

A celebrated impossibility result by Myerson and Satterthwaite (1983) shows that any truthful mechanism for two-sided markets maximizes social welfare must run a deficit, resulting in necessity to relax efficiency the use of approximation mechanisms. Such mechanisms general make extensive Bayesian priors. In this work, we investigate question increasing theoretical practical importance: how much prior information is required design with near-optimal approximations?

Bilateral trade, a fundamental topic in economics, models the problem of intermediating between two strategic agents, seller and buyer, willing to trade good for which they hold private valuations. In this paper, we cast bilateral regret minimization framework over $T$ rounds seller/buyer interactions, with no prior knowledge on their Our main contribution is complete characterization regimes fixed-price mechanisms different feedback valuations, using as benchmark best hindsight. More...

Pandora’s problem is a fundamental model that studies optimal search under costly inspection. In the classic version, there are n boxes, each associated with known cost and distribution over values. A strategy inspects boxes sequentially obtains utility equals difference between maximum value of an inspected box total inspection cost. Weitzman (1979) presented surprisingly simple expected utility. this work we introduce new variant in which every also publicly deadline, indicating final...

The Pandora's Box Problem, originally formalized by Weitzman in 1979, models selection from a set of options each with stochastic parameters, when evaluation (i.e. sampling) is costly. This includes, for example, the problem hiring skilled worker, where only one hire can be made, but candidate an expensive procedure.

Abstract We study truthful mechanisms for welfare maximization in online bipartite matching. In our (multi-parameter) setting, every buyer is associated with a (possibly private) desired set of items, and has private value being assigned an item her set. Unlike most matching settings, where agents arrive online, setting the items one by adversarial order while buyers are present entire duration process. This poses significant challenge to design mechanisms, due ability strategize over future...

Bilateral trade models the problem of intermediating between two rational agents — a seller and buyer both characterized by private valuation for an item they want to trade. We study online learning version problem, in which at each time step new arrive learner has set prices them without any knowledge about their (adversarially generated) valuations.

Bilateral trade, a fundamental topic in economics, models the problem of intermediating between two strategic agents, seller and buyer, willing to trade good for which they hold private valuations. Despite simplicity this problem, classical result by Myerson Satterthwaite (1983) affirms impossibility designing mechanism is simultaneously efficient, incentive compatible, individually rational, budget balanced. This fostered an intense investigation meaningful trade-offs these desired...

We consider the problem of fairly allocating a set indivisible goods to strategic agents with additive valuation functions. assume no monetary transfers, and therefore, mechanism in our setting is an algorithm that takes as input reported—rather than true—values agents. Our main goal explore whether there exist mechanisms have pure Nash equilibria for every instance and, at same time, provide fairness guarantees allocations correspond these equilibria. focus on two relaxations envy-freeness,...

Constrained submodular maximization problems encompass a wide variety of applications, including personalized recommendation, team formation, and revenue via viral marketing. The massive instances occurring in modern day applications can render existing algorithms prohibitively slow, while frequently, those are also inherently stochastic. Focusing on these challenges, we revisit the classic problem maximizing (possibly non-monotone) function subject to knapsack constraint. We present simple...

We study repeated bilateral trade where an adaptive $\sigma$-smooth adversary generates the valuations of sellers and buyers. provide a complete characterization regret regimes for fixed-price mechanisms under different feedback models in two cases learner can post either same or prices to buyers sellers. begin by showing that minimax after $T$ rounds is order $\sqrt{T}$ full-feedback scenario. Under partial feedback, any algorithm has price suffers worst-case linear regret. However, when at...

We address a generalization of the bandit with knapsacks problem, where learner aims to maximize rewards while satisfying an arbitrary set long-term constraints. Our goal is design best-of-both-worlds algorithms that perform optimally under both stochastic and adversarial Previous works this problem via primal-dual methods, require some stringent assumptions, namely Slater's condition, in settings, they either assume knowledge lower bound on parameter, or impose strong requirements primal...

Maximizing monotone submodular functions under cardinality constraints is a classic optimization task with several applications in data mining and machine learning. In this paper we study problem dynamic environment consistency constraints: elements arrive streaming fashion the goal maintaining constant approximation to optimal solution while having stable (i.e., number of changes between two consecutive solutions bounded). We provide algorithms setting different trade-offs quality. also...

Maximizing monotone submodular functions under a matroid constraint is classic algorithmic problem with multiple applications in data mining and machine learning. We study this significant the fully dynamic setting, where elements can be both inserted deleted real-time. Our main result randomized algorithm that maintains an efficient structure \({\tilde{O}({k^{2}}{\varepsilon})}\) amortized update time (in number of insertions deletions) yields \({(4+O(\varepsilon))}\) -approximate solution...

Motivated by online retail, we consider the problem of selling one item (e.g., an ad slot) to two non-excludable buyers (say, a merchant and brand). This captures, for example, situations where brand cooperatively bid in auction advertise product, both benefit from being shown. A mechanism collects bids decides whether allocate which payments parties should make. gives rise intricate incentive compatibility constraints, e.g., on how split between parties. We approach finding...

In this work, we study online submodular maximization, and how the requirement of maintaining a stable solution impacts approximation. particular, seek bounds on best-possible approximation ratio that is attainable when algorithm allowed to make at most constant number updates per step. We show tight information-theoretic bound $\tfrac{2}{3}$ for general monotone functions, an improved (also tight) $\tfrac{3}{4}$ coverage functions. Since both these are attained by non poly-time algorithms,...

Pandora’s problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper, we initiate the study of with combinatorial costs, capturing applications where cost nonadditive. Weitzman’s celebrated algorithm (1979) demonstrates for additive strategy nonadaptive and computationally feasible. We inquire to which extent structural computational simplicity extends beyond costs. Our main result class submodular functions admits an follows...