We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of our model is a reward function , which maps the agent efforts to an expected reward of the principal. We seek to design computationally efficient algorithms for finding optimal (or near-optimal) linear contracts for reward functions that belong to the complement-free hierarchy. Our first main result gives constant-factor approximation algorithms for submodular and XOS reward functions, with value oracles for submodular reward functions and value and demand oracles for XOS reward functions. It relies on an unconventional use of “prices” and (approximate) demand queries for selecting the set of agents that the principal should contract with, and exploits a novel scaling property of XOS functions and their marginals, which may be of independent interest. As our second main result, we show that constant approximation is the best we can get for submodular reward functions, even with both value and demand oracles. For the larger class of subadditive reward functions, we establish an \(\Omega (\sqrt {n})\) impossibility for settings with n agents. A striking feature of this impossibility is that it applies to subadditive functions that are constant-factor close to submodular. This rapid degradation presents a surprising departure from previous literature, e.g., on combinatorial auctions, where approximation guarantees tend to deteriorate more gracefully.

Online Set Cover and Load Balancing are central problems in online optimization, and there is a long line of work focusing on developing algorithms for these problems with convex objectives. Although we know optimal online algorithms with $\ell_{p}$-norm objectives, recent developments for general norms and convex objectives that rely on the online primal-dual framework apply only to fractional settings due to large integrality gaps. Our work focuses on directly designing integral online algorithms for Set Cover and Load Balancing with convex objectives, bypassing the convex-relaxation and the primal-dual technique. Some of the main implications of our approach are: 1) For Online Set Cover, we can extend the results of [1] for convex objectives and of [2] for symmetric norms from fractional to integral settings. 2) Our results for convex objectives and symmetric norms even apply to the Online Generalized Scheduling Problem, which generalizes both Set Cover and Load Balancing. Previous works could only handle the offline version of this problem with norm objectives [3]. 3) Our approach easily extends to settings involving disjointcomposition of norms. This allows us to recover or improve the norm-composition results of [4], [2] and extend our results to a large class of norms beyond the symmetric setting. Our approach involves first reducing these online problems to online packing problems, and to then design good approximation algorithms for the latter. To solve these packing problem, we use two key ideas. First, we decouple the global packing problem into a series of local packing problems on different machines. Second, we choose random activation thresholds for machines such that conditional on a machine being activated the expected number of jobs it covers is high compared to its cost. This approach may be of independent interest and could find applications to other online problems. Index Terms-online algorithms, set cover, load balancing

Motivated by stochastic optimization, we introduce the problem of learning from samples of contextual value distributions. A contextual value distribution can be understood as a family of real-valued distributions, where each sample consists of a context x and a random variable drawn from the corresponding real-valued distribution Dx. By minimizing a convex surrogate loss, we learn an empirical distribution D'x for each context, ensuring a small Levy distance to Dx.

Combinatorial contracts are emerging as a key paradigm in algorithmic contract design, paralleling the role of combinatorial auctions in algorithmic mechanism design. In this paper we study natural combinatorial contract settings involving teams of agents, each capable of performing multiple actions. This scenario extends two fundamental special cases: the single-agent combinatorial action model of [18], and the multi-agent binary- action model of [4, 19].

Abstract. We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take any subset of a given set of unobservable actions, each of which has an associated cost. The cost of a set of actions is the sum of the costs of the individual actions, and the principal’s reward as a function of the chosen actions satisfies some form of diminishing returns. The principal incentivizes the agents through a contract based on the observed outcome. Our main results are for the case where the task delegated to the agent is a project, which can be successful or not. We show that if the success probability as a function of the set of actions is gross substitutes, then an optimal contract can be computed with polynomially many value queries, whereas if it is submodular, the optimal contract is NP-hard. All our results extend to linear contracts for higher-dimensional outcome spaces, which we show to be robustly optimal given first moment constraints. Our analysis uncovers a new property of gross substitutes functions and reveals many interesting connections between combinatorial contracts and combinatorial auctions, where gross substitutes is known to be the frontier for efficient computation.

In online combinatorial allocations/auctions,$n$bidders sequentially arrive, each with a combinatorial valuation (such as submodular/XOS) over subsets of$m$indivisible items. The aim is to immediately allocate a subset of the remaining items to maximize the total welfare, defined as the sum of bidder valuations. A long line of work has studied this problem when the bidder valuations come from known independent distributions. In particular, for submodular/XOS valuations, we know 2-competitive algorithms/mechanisms that set a fixed price for each item and the arriving bidders take their favorite subset of the remaining items given these prices. However, these algorithms traditionally presume the availability of the underlying distributions as part of the input to the algorithm. Contrary to this assumption, practical scenarios often require the learning of distributions, a task complicated by limited sample availability. This paper investigates the feasibility of achieving$O$(1) -competitive algorithms under the realistic constraint of having access to only a limited number of samples from the underlying bidder distributions. Our first main contribution shows that a mere single sample from each bidder distribution is sufficient to yield an$O$(1)-competitive algorithm for submodular/XOS valuations. This result leverages a novel extension of the secretary-style analysis, employing the sample to have the algorithm compete against itself. Although online, this first approach does not provide an online truthful mechanism. Our second main contribution shows that a polynomial number of samples suffices to yield a (2 + ∊) -competitive online truthful mechanism for submodular/XOS valuations and any constant ∊ > 0. This result is based on a generalization of the median-based algorithm for the single-item prophet inequality problem to combinatorial settings with multiple items.

Selling a single item to $n$ self-interested bidders is a fundamental problem in economics, where the two objectives typically considered are welfare maximization and revenue maximization. Since the optimal auctions are often impractical and do not work for sequential bidders, posted pricing auctions, where fixed prices are set for the item for different bidders, have emerged as a practical and effective alternative. This paper investigates how many samples are needed from bidders' value distributions to find near-optimal posted prices, considering both independent and correlated bidder distributions, and welfare versus revenue maximization. We obtain matching upper and lower bounds (up to logarithmic terms) on the sample complexity for all these settings.

We study online capacitated resource allocation, a natural generalization of online stochastic max-weight bipartite matching. This problem is motivated by ride-sharing and Internet advertising applications, where online arrivals may have the capacity to serve multiple offline users.

The Prophet Inequality and Pandora's Box problems are fundamental stochastic problem with applications in Mechanism Design, Online Algorithms, Stochastic Optimization, Optimal Stopping, and Operations Research. A usual assumption in these works is that the probability distributions of the n underlying random variables are given as input to the algorithm. Since in practice these distributions need to be learned under limited feedback, we initiate the study of such stochastic problems in the Multi-Armed Bandits model.

Many classical problems in theoretical computer science involve norms, even if implicitly; for example, both XOS functions and downward-closed sets are equivalent to some norms. The last decade has seen a lot of interest in designing algorithms beyond the standard ℓp norms ||· ||p. Despite notable advancements, many existing methods remain tailored to specific problems, leaving a broader applicability to general norms less understood. This paper investigates the intrinsic properties of ℓp norms that facilitate their widespread use and seeks to abstract these qualities to a more general setting. We identify supermodularity—often reserved for combinatorial set functions and characterized by monotone gradients—as a defining feature beneficial for ||·||pp. We introduce the notion of p-supermodularity for norms, asserting that a norm is p-supermodular if its pth power function exhibits supermodularity. The association of supermodularity with norms offers a new lens through which to view and construct algorithms. Our work demonstrates that for a large class of problems p-supermodularity is a sufficient criterion for developing good algorithms. This is either by reframing existing algorithms for problems like Online Load-Balancing and Bandits with Knapsacks through a supermodular lens, or by introducing novel analyses for problems such as Online Covering, Online Packing, and Stochastic Probing. Moreover, we prove that every symmetric norm can be approximated by a p-supermodular norm. Together, these recover and extend several existing results, and support p-supermodularity as a unified theoretical framework for optimization challenges centered around norm-related problems.

Prophet inequalities compare the expected performance of an online algorithm for a stochastic optimization problem to the expected optimal solution in hindsight. They are a major alternative to classic worst-case competitive analysis, of particular importance in the design and analysis of simple (posted-price) incentive compatible mechanisms with provable approximation guarantees. A central open problem in this area concerns subadditive combinatorial auctions. Here $n$ agents with subadditive valuation functions compete for the assignment of $m$ items. The goal is to find an allocation of the items that maximizes the total value of the assignment. The question is whether there exists a prophet inequality for this problem that significantly beats the best known approximation factor of $O(\log m)$. We make major progress on this question by providing an $O(\log \log m)$ prophet inequality. Our proof goes through a novel primal-dual approach. It is also constructive, resulting in an online policy that takes the form of static and anonymous item prices that can be computed in polynomial time given appropriate query access to the valuations. As an application of our approach, we construct a simple and incentive compatible mechanism based on posted prices that achieves an $O(\log \log m)$ approximation to the optimal revenue for subadditive valuations under an item-independence assumption.

Abstract. The secretary and the prophet inequality problems are central to the field of stopping theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions. Kleinberg and Weinberg and Feldman, Gravin, and Lucier show that for adversarial arrival order of random variables the optimal prophet inequalities give a [Formula: see text]-approximation. For many settings, however, it is conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the [Formula: see text]-approximation and obtain [Formula: see text]-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan and of Esfandiari and colleagues who worked in the special cases where either we can fully control the arrival order or there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.

Vector norms play a fundamental role in computer science and optimization, so there is an ongoing effort to generalize existing algorithms to settings beyond ℓ∞ and ℓp norms. We show that many online and bandit applications for general norms admit good algorithms as long as the norm can be approximated by a function that is “gradient-stable”, a notion that we introduce. Roughly it says that the gradient of the function should not drastically decrease (multiplicatively) in any component as we increase the input vector. We prove that several families of norms, including all monotone symmetric norms, admit a gradient-stable approximation, giving us the first online and bandit algorithms for these norm families. In particular, our notion of gradient-stability gives O (log2 (dimension))-competitive algorithms for the symmetric norm generalizations of Online Generalized Load Balancing and Bandits with Knapsacks. Our techniques extend to applications beyond symmetric norms as well, e.g., to Online Vector Scheduling and to Online Generalized Assignment with Convex Costs. Some key properties underlying our applications that are implied by gradient-stable approximations are a “smooth game inequality” and an approximate converse to Jensen's inequality.

We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of our model is a reward function, which maps the agent efforts to an expected reward of the principal. We seek to design computationally efficient algorithms for finding optimal (or near-optimal) linear contracts for reward functions that belong to the complement-free hierarchy.

We consider the problem of posting prices for unit-demand buyers if all $n$ buyers have identically distributed valuations drawn from a distribution with monotone hazard rate. We show that even with multiple items asymptotically optimal welfare can be guaranteed. Our main results apply to the case that either a buyer's value for different items are independent or that they are perfectly correlated. We give mechanisms using dynamic prices that obtain a $1 - Θ\left( \frac{1}{\log n}\right)$-fraction of the optimal social welfare in expectation. Furthermore, we devise mechanisms that only use static item prices and are $1 - Θ\left( \frac{\log\log\log n}{\log n}\right)$-competitive compared to the optimal social welfare. As we show, both guarantees are asymptotically optimal, even for a single item and exponential distributions.

We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take any subset of a given set of unobservable actions, each of which has an associated cost. The cost of a set of actions is the sum of the costs of the individual actions, and the principal's reward as a function of the chosen actions satisfies some form of diminishing returns. The principal incentivizes the agents through a contract, based on the observed outcome. Our main results are for the case where the task delegated to the agent is a project, which can be successful or not. We show that if the success probability as a function of the set of actions is gross substitutes, then an optimal contract can be computed with polynomially many value queries, whereas if it is submodular, the optimal contract is NP-hard. All our results extend to linear contracts for higher-dimensional outcome spaces, which we show to be robustly optimal given first moment constraints. Our analysis uncovers a new property of gross substitutes functions, and reveals many interesting connections between combinatorial contracts and combinatorial auctions, where gross substitutes is known to be the frontier for efficient computation.

We design novel mechanisms for welfare-maximization in two-sided markets. That is, there are buyers willing to purchase items and sellers holding items initially, both acting rationally and strategically in order to maximize utility. Our mechanisms are designed based on a powerful correspondence between two-sided markets and prophet inequalities. They satisfy individual rationality, dominant-strategy incentive compatibility, budget-balance constraints and give constant-factor approximations to the optimal social welfare. We improve previous results in several settings: Our main focus is on matroid double auctions, where the set of buyers who obtain an item needs to be independent in a matroid. We construct two mechanisms, the first being a 1/3-approximation of the optimal social welfare satisfying strong budget-balance and requiring the agents to trade in a customized order, the second being a 1/2-approximation, weakly budget-balanced and able to deal with online arrival determined by an adversary. In addition, we construct constant-factor approximations in two-sided markets when buyers need to fulfill a knapsack constraint. Also, in combinatorial double auctions, where buyers have valuation functions over item bundles instead of being interested in only one item, using similar techniques, we design a mechanism which is a $1/2$-approximation of the optimal social welfare, strongly budget-balanced and can deal with online arrival of agents in an adversarial order.

We present a computationally-efficient truthful mechanism for combinatorial auctions with subadditive bidders that achieves an $O((\log\!\log{m})^3)$-approximation to the maximum welfare in expectation using $O(n)$ demand queries; here $m$ and $n$ are the number of items and bidders, respectively. This breaks the longstanding logarithmic barrier for the problem dating back to the $O(\log{m}\cdot\log\!\log{m})$-approximation mechanism of Dobzinski from 2007. Along the way, we also improve and considerably simplify the state-of-the-art mechanisms for submodular bidders.

We introduce online learning with vector costs ($OLVC_p$) where in each time step $t \in \{1,\ldots, T\}$, we need to play an action $i \in \{1,\ldots,n\}$ that incurs an unknown vector cost in $[0,1]^d$. The goal of the online algorithm is to minimize the $\ell_p$ norm of the sum of its cost vectors. This captures the classical online learning setting for $d=1$, and is interesting for general $d$ because of applications like online scheduling where we want to balance the load between different machines (dimensions). We study $OLVC_p$ in both stochastic and adversarial arrival settings, and give a general procedure to reduce the problem from $d$ dimensions to a single dimension. This allows us to use classical online learning algorithms in both full and bandit feedback models to obtain (near) optimal results. In particular, we obtain a single algorithm (up to the choice of learning rate) that gives sublinear regret for stochastic arrivals and a tight $O(\min\{p, \log d\})$ competitive ratio for adversarial arrivals. The $OLVC_p$ problem also occurs as a natural subproblem when trying to solve the popular Bandits with Knapsacks (BWK) problem. This connection allows us to use our $OLVC_p$ techniques to obtain (near) optimal results for BWK in both stochastic and adversarial settings. In particular, we obtain a tight $O(\log d \cdot \log T)$ competitive ratio algorithm for adversarial BWK, which improves over the $O(d \cdot \log T)$ competitive ratio algorithm of Immorlica et al. (2019).

Prophet inequalities compare the expected performance of an online algorithm for a stochastic optimization problem to the expected optimal solution in hindsight. They are a major alternative to classic worst-case competitive analysis, of particular importance in the design and analysis of simple (posted-price) incentive compatible mechanisms with provable approximation guarantees. A central open problem in this area concerns subadditive combinatorial auctions. Here n agents with subadditive valuation functions compete for the assignment of m items. The goal is to find an allocation of the items that maximizes the total value of the assignment. The question is whether there exists a prophet inequality for this problem that significantly beats the best known approximation factor of O(log m). We make major progress on this question by providing an O(log log m) prophet inequality. Our proof goes through a novel primal-dual approach. It is also constructive, resulting in an online policy that takes the form of static and anonymous item prices that can be computed in polynomial time given appropriate query access to the valuations. As an application of our approach, we construct a simple and incentive compatible mechanism based on posted prices that achieves an O(log log m) approximation to the optimal revenue for subadditive valuations under an item-independence assumption.

The random-order or secretary model is one of the most popular beyond-worst case model for online algorithms. While it avoids the pessimism of the traditional adversarial model, in practice we cannot expect the input to be presented in perfectly random order. This has motivated research on ``best of both worlds'' (algorithms with good performance on both purely stochastic and purely adversarial inputs), or even better, on inputs that are a mix of both stochastic and adversarial parts. Unfortunately the latter seems much harder to achieve and very few results of this type are known. Towards advancing our understanding of designing such robust algorithms, we propose a random-order model with bursts of adversarial time steps. The assumption of burstiness of unexpected patterns is reasonable in many contexts, since changes (e.g. spike in a demand for a good) are often triggered by a common external event. We then consider the Knapsack Secretary problem in this model: there is a knapsack of size $k$ (e.g., available quantity of a good), and in each of the $n$ time steps an item comes with its value and size in $[0,1]$ and the algorithm needs to make an irrevocable decision whether to accept or reject the item. We design an algorithm that gives an approximation of $1 - \tilde{O}(Γ/k)$ when the adversarial time steps can be covered by $Γ\ge \sqrt{k}$ intervals of size $\tilde{O}(\frac{n}{k})$. In particular, setting $Γ= \sqrt{k}$ gives a $(1 - O(\frac{\ln^2 k}{\sqrt{k}}))$-approximation that is resistant to up to a $\frac{\ln^2 k}{\sqrt{k}}$-fraction of the items being adversarial, which is almost optimal even in the absence of adversarial items. Also, setting $Γ= \tildeΩ(k)$ gives a constant approximation that is resistant to up to a constant fraction of items being adversarial.

We study the price of anarchy of mechanisms in the presence of risk-averse agents. Previous work has focused on agents with quasilinear utilities, possibly with a budget. Our model subsumes this as a special case but also captures that agents might be less sensitive to payments than in the risk-neutral model. We show that many positive price-of-anarchy results proved in the smoothness framework continue to hold in the more general risk-averse setting. A sufficient condition is that agents can never end up with negative quasilinear utility after playing an undominated strategy. This is true, e.g., for first-price and second-price auctions. For all-pay auctions, similar results do not hold: We show that there are Bayes-Nash equilibria with arbitrarily bad social welfare compared to the optimum.

The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg [33] and Feldman et al. [17] show that for adversarial arrival order of random variables the optimal prophet inequalities give a 1/2-approximation. For many settings, however, it's conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the 1/2-approximation and obtain (1 – 1/e)-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan [45] and Esfandiari et al. [15] who worked in the special cases where we can fully control the arrival order or when there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.

We study packing linear programs (LPs) in an online model where the columns are presented to the algorithm in random order. This natural problem was investigated in various recent studies motivated, e.g., by online ad allocations and yield management, where rows correspond to resources and columns to requests specifying demands for resources. Our main contribution is a $1-O(\sqrt{\nicefrac{(\log d)}{B}})$-competitive online algorithm. Here $d$ denotes the column sparsity, i.e., the maximum number of resources that occur in a single column, and $B$ denotes the capacity ratio $B$, i.e., the ratio between the capacity of a resource and the maximum demand for this resource. In other words, we achieve a $(1-\epsilon)$-approximation if the capacity ratio satisfies $B=\Omega(\frac{\log d}{\epsilon^2})$, which is known to be the best possible for any (randomized) online algorithms. Our result improves exponentially on previous work with respect to the capacity ratio. In contrast to existing results on packing LP problems, our algorithm does not use dual prices to guide the allocation of resources over time. Instead, the algorithm simply solves, for each request, a scaled version of the partially known primal program and randomly rounds the obtained fractional solution to obtain an integral allocation for this request. We show that this simple algorithmic technique is not restricted to packing LPs with large capacity ratio of order $\Omega(\log d)$, but also yields close-to-optimal competitive ratios if the capacity ratio is bounded by a constant. In particular, we prove an upper bound on the competitive ratio of $\Omega(d^{\nicefrac{-1}{(B-1)}})$ for any $B\geq2$. In addition, we show that our approach can be combined with VCG payments and obtain an incentive-compatible $(1-\epsilon)$-competitive mechanism for packing LPs with $B=\Omega(\frac{\log m}{\epsilon^2})$, where $m$ is the number of constraints. Finally, we apply our technique to the generalized assignment problem for which we obtain the first online algorithm with competitive ratio $O(1)$.

This paper considers optimizing a submodular function subject to a set of downward closed constraints. Previous literature on this problem has often constructed solutions by (1) discovering a fractional solution to the multi-linear extension and (2) rounding this solution to an integral solution via a contention resolution scheme. This line of research has improved results by either optimizing (1) or (2). Diverging from previous work, this paper introduces a principled method called contention resolution extensions of submodular functions. A contention resolution extension combines the contention resolution scheme into a continuous extension of a discrete submodular function. The contention resolution extension can be defined from effectively any contention resolution scheme. In the case where there is a loss in both (1) and (2), by optimizing them together, the losses can be combined resulting in an overall improvement. This paper showcases the concept by demonstrating that for the problem of optimizing a non-monotone submodular subject to the elements forming an independent set in an interval graph, the algorithm gives a .188-approximation. This improves upon the best known 1/(2e)~eq .1839 approximation.

We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes prophet inequalities by constructing price-based online approximation algorithms, a natural extension of threshold algorithms for settings beyond binary selection. Our analysis takes the form of an extension theorem: we derive sufficient conditions on prices when all weights are known in advance, then prove that the resulting approximation guarantees extend directly to stochastic settings. Our framework unifies and simplifies much of the existing literature on prophet inequalities and posted price mechanisms and is used to derive new and improved results for combinatorial markets (with and without complements), multidimensional matroids, and sparse packing problems. Finally, we highlight a surprising connection between the smoothness framework for bounding the price of anarchy of mechanisms and our framework, and show that many smooth mechanisms can be recast as posted price mechanisms with comparable performance guarantees.

In a combinatorial auction with item bidding, agents participate in multiple single-item second-price auctions at once. As some items might be substitutes, agents need to strate- gize in order to maximize their utilities. A number of results indicate that high welfare can be achieved this way, giving bounds on the welfare at equilibrium. Recently, however, criticism has been raised that equilibria are hard to compute and therefore unlikely to be attained. In this paper, we take a different perspective. We study simple best-response dynamics. That is, agents are activated one after the other and each activated agent updates his strategy myopically to a best response against the other agents’ current strategies. Often these dynamics may take exponentially long before they converge or they may not converge at all. However, as we show, convergence is not even necessary for good welfare guarantees. Given that agents’ bid updates are aggressive enough but not too aggressive, the game will remain in states of good welfare after each agent has updated his bid at least once. In more detail, we show that if agents have fractionally subadditive valuations, natural dynamics reach and remain in a state that provides a 1/3 approximation to the optimal welfare after each agent has updated his bid at least once. For subadditive valuations, we can guarantee an Ω(1/log m) approximation in case of m items that applies after each agent has updated his bid at least once and at any point after that. The latter bound is complemented by a negative result, showing that no kind of best-response dynamics can guarantee more than a an o(log log m/ log m) fraction of the optimal social welfare.

The Temp Secretary Problem was recently introduced by [Fiat et al., ESA 2015]. It is a generalization of the Secretary Problem, in which commitments are temporary for a fixed duration. We present a simple online algorithm with improved performance guarantees for cases already considered by [Fiat et al., ESA 2015] and give competitive ratios for new generalizations of the problem. In the classical setting, where candidates have identical contract durations gamma << 1 and we are allowed to hire up to B candidates simultaneously, our algorithm is (1/2) - O(sqrt{gamma})-competitive. For large B, the bound improves to 1 - O(1/sqrt{B}) - O(sqrt{gamma}). Furthermore we generalize the problem from cardinality constraints towards general packing constraints. We achieve a competitive ratio of 1 - O(sqrt{(1+log(d) + log(B))/B}) - O(sqrt{gamma}), where d is the sparsity of the constraint matrix and B is generalized to the capacity ratio of linear constraints. Additionally we extend the problem towards arbitrary hiring durations. Our algorithmic approach is a relaxation that aggregates all temporal constraints into a non-temporal constraint. Then we apply a linear scaling algorithm that, on every arrival, computes a tentative solution on the input that is known up to this point. This tentative solution uses the non-temporal, relaxed constraints scaled down linearly by the amount of time that has already passed.

We consider capacity maximization in wireless networks under adversarial interference conditions. There are n links, i.e., sender-receiver pairs, which repeatedly try to perform a successful transmission. In each time step, the success of attempted transmissions depends on interference conditions, which are captured by an interference model (e.g., the SINR model). Additionally, an adversarial jammer can render a (1-δ)-fraction of time steps in a time window unsuccessful. For this scenario, we analyze a framework for distributed no-regret learning algorithms to get provable approximation guarantees. We obtain an O(1/δ)-approximation for the problem of maximizing the number of successful transmissions. Our approach provides even a constant-factor approximation when the jammer exactly blocks a (1-δ)-fraction of time steps. In addition, we consider the parameters of the jammer being partially unknown to the algorithm, and we also consider a stochastic jammer, for which we obtain a constant-factor approximation after a polynomial number of time steps. We extend our results to more general settings, in which links arrive and depart dynamically, and where each sender tries to reach multiple receivers. Our algorithms perform favorably in simulations.

The algorithmic requirements for dominant strategy incentive compatibility, or truthfulness, are well understood. Is there a similar characterization of algorithms that when combined with a suitable payment rule yield near-optimal welfare in all equilibria? We address this question by providing a tight characterization of a (possibly randomized) mechanism's Price of Anarchy provable via smoothness, for single-parameter settings. The characterization assigns a unique value to each allocation algorithm; this value provides an upper and a matching lower bound on the Price of Anarchy of a derived mechanism provable via smoothness. The characterization also applies to the sequential or simultaneous composition of single-parameter mechanisms. Importantly, the factor that we identify is typically not in one-to-one correspondence to the approximation guarantee of the algorithm. Rather, it is usually the product of the approximation guarantee and the degree to which the mechanism is loser independent.

Many algorithms, that are originally designed without explicitly considering incentive properties, are later combined with simple pricing rules and used as mechanisms. The resulting mechanisms are often natural and simple to understand. But how good are these algorithms as mechanisms? Truthful reporting of valuations is typically not a dominant strategy (certainly not with a pay-your-bid, first-price rule, but it is likely not a good strategy even with a critical value, or second-price style rule either). Our goal is to show that a wide class of approximation algorithms yields this way mechanisms with low Price of Anarchy. The seminal result of Lucier and Borodin [2010] shows that combining a greedy algorithm that is an α-approximation algorithm with a pay-your-bid payment rule yields a mechanism whose Price of Anarchy is O(α). In this paper we significantly extend the class of algorithms for which such a result is available by showing that this close connection between approximation ratio on the one hand and Price of Anarchy on the other also holds for the design principle of relaxation and rounding provided that the relaxation is smooth and the rounding is oblivious.

Using renewable energy in an efficient way is a key challenge facing our society. In this paper we study online mechanisms motivated by markets for such renewable energy, such as wind energy. While the aggregate demand of the large populations served by energy providers is quite predictable, supply in such systems is rather uncertain; e.g. it depends on the strength of the wind at the wind turbines. Energy, when it is available, must be delivered immediately, due to the inefficiency of technologies for electric power storage, hence the supply is perishable. We model this scenario with an online market where supply is unknown, but participants know their own demand, and bid for energy at the beginning of the period. Items arrive online and are perishable, meaning that they have to be allocated to bidders immediately after arrival. This setup have been used for modeling renewable energy markets by earlier works, such as Tan and Varaiya (1993). We perform a price-of-anarchy analysis for a simple greedy allocation scheme, and compare efficiency of equilibria and learning outcomes to the socially optimal offline allocation. Due to the uncertainty, traditional dominant-strategy truthfulness cannot be achieved except by trivial mechanisms, which makes simple allocation mechanisms, such as the greedy, an appealing alternative. We show that simple first-price or second-price auctions combined with a greedy allocation rule ensure that equilibria closely approximate the optimum, assuming that bidders' preferences are non-increasing over time and additive within their demand, and demand is captured by a cardinality or matroid constraint. The results are of interest not only due to the application to energy markets, but also as they provide the first successful bounds on the price of anarchy of mechanisms in any online setting, while for the classical sequential auction setting Paes Leme et al. (2012) show that the price of anarchy is prohibitively high even with very simple bidder utilities. In more detail, we prove that equilibria and learning outcomes ensure at least half of the optimal welfare in case of the first-price rule with cardinality constraints, matching the approximation bound for the greedy algorithm. For second-price and more general matroid constraints, we show weaker guarantees. All results also extend to the Bayesian setting, where player values are random: bidder know their own future demand, but the competition is uncertain as is the supply, and all values may be correlated.

For a number of problems in the theory of online algorithms, it is known that the assumption that elements arrive in uniformly random order enables the design of algorithms with much better performance guarantees than under worst-case assumptions. The quintessential example of this phenomenon is the secretary problem, in which an algorithm attempts to stop a sequence at the moment it observes the maximum value in the sequence. As is well known, if the sequence is presented in uniformly random order there is an algorithm that succeeds with probability 1/e, whereas no non-trivial performance guarantee is possible if the elements arrive in worst-case order.

We study approximation algorithms for optimization of wireless spectrum access with n communication requests when interference conditions are given by the Rayleigh-fading model. This model extends the deterministic interference model based on the signal-to-interference-plus-noise ratio (SINR) using stochastic propagation to address fading effects observed in reality. We consider worst-case approximation guarantees for the two standard problems of capacity maximization and latency minimization. Our main result is a generic reduction of Rayleigh fading to the deterministic non-fading model. It allows to apply existing algorithms for the non-fading model in the Rayleigh-fading scenario while losing only a factor of O(log* n) in the approximation guarantee. This way, we obtain the first approximation guarantees for Rayleigh fading and, more fundamentally, show that non-trivial stochastic fading effects can be successfully handled using existing and future techniques for the non-fading model. We generalize these results in two ways. First, the same results apply for capacity maximization with variable data rates, when links obtain (non-binary) utility depending on the achieved SINR. Second, for binary utilities, we use a more detailed argument to obtain similar results even for distributed and game-theoretic approaches. Our analytical treatment is supported by simulations illustrating the performance of regret learning and, more generally, the relationship between both models.

The existence of a unique equilibrium is the classic tool for ensuring predictiveness of game theory. Typical uniqueness results, however, are for Nash and Bayes-Nash equilibria and do not guarantee that natural game playing dynamic converges to this equilibrium. In fact, there are well known examples in which the equilibrium is unique, yet natural learning behavior does not converge to it. Motivated by this, we strive for stronger uniqueness results. We do not only require that there is a unique equilibrium, but also that this equilibrium must be learnable. We adopt correlated equilibrium as our solution concept, as simple and natural learning algorithms guarantee that the empirical distribution of play converges to the space of correlated equilibria. Our main result is to show uniqueness of correlated equilibria in a large class of single-parameter mechanisms with matroid structure. We also show that our uniqueness result extends to problems with polymatroid structure under some conditions. Our model includes a number of special cases interesting on their own right, such as procurement auctions and Bertrand competitions. An interesting feature of our model is that we do not need to assume that the players have quasi-linear utilities, and hence can incorporate models with risk averse players and certain forms of externalities.

We study packing LPs in an online model where the columns are presented to the algorithm in random order. This natural problem was investigated in various recent studies motivated, e.g., by online ad allocations and yield management where rows correspond to resources and columns to requests specifying demands for resources. Our main contribution is a 1 -- O(√(log d/B))-competitive online algorithm. Here d denotes the column sparsity, i.e., the maximum number of resources that occur in a single column, and B denotes the capacity ratio B, i.e., the ratio between the capacity of a resource and the maximum demand for this resource. In other words, we achieve a (1--ε)-approximation if the capacity ratio satisfies B=Ω(logd/ε2), which is known to be best-possible for any (randomized) online algorithms.

We study combinatorial auctions for secondary spectrum markets, where short-term communication licenses are sold to wireless nodes. Channels can be assigned to multiple bidders according to interference constraints captured by a conflict graph. We suggest a novel approach to such combinatorial auctions using a graph parameter called inductive independence number. We achieve good approximation results by showing that interference constraints for wireless networks imply a bounded inductive independence number. For example, in the physical model the factor becomes O (√ k log 2 n ) for n bidders and k channels. Our algorithms can be turned into incentive-compatible mechanisms for bidders with arbitrary valuations.

We consider truthfulness concepts for auctions with payments based on first- and second-order stochastic dominance. We assume bidders consider wealth in standard quasi-linear form as valuation minus payments. Additionally, they are sensitive to risk in the distribution of wealth stemming from randomized mechanisms. First- and second-order stochastic dominance are well-known to capture risk-sensitivity, and we apply these concepts to capture truth-telling incentives for bidders.

We present algorithms for implementing local spectrum redistribution in wireless networks using a mechanism design approach. For example, in single-hop request scheduling, secondary users are modeled as rational agents that have private utility when getting assigned a channel for successful transmission. We present a simple algorithmic technique that allows to turn existing and future approximation algorithms and heuristics into truthful mechanisms for a large variety of networking problems. Our approach works with virtually all known interference models in the literature, including the physical model of interference based on SINR. It allows to address single-hop and multi-hop scheduling, routing, and even more general assignment and allocation problems. Our mechanisms are randomized and represent the first universally-truthful mechanisms for these problems with rigorous worst-case guarantees on the solution quality. In this way, our mechanisms can be used to obtain guaranteed solution quality even with risk-averse or risk-seeking bidders, for which existing approaches fail.

We consider protocols that serve communication requests arising over time in a wireless network that is subject to interference. Unlike previous approaches, we take the geometry of the network and power control into account, both allowing to increase the network's performance significantly.

We study truthful auctions for secondary spectrum usage in wireless networks. In this scenario, n communication requests need to be allocated to k available channels that are subject to interference and noise. We present the first truthful mechanisms for secondary spectrum auctions with symmetric or submodular valuations. Our approach to model interference uses an edge-weighted conflict graph, and our algorithms provide asymptotically almost optimal approximation bounds for conflict graphs with a small inductive independence number ρ << n. This approach covers a large variety of interference models such as, e.g., the protocol model or the recently popular physical model of interference. For unweighted conflict graphs and symmetric valuations we use LP-rounding to obtain O(ρ)-approximate mechanisms; for weighted conflict graphs we get a factor of O(ρ ρ (log n + log k)). For submodular users we combine the convex rounding framework of [Dughmi et al. 2011] with randomized meta-rounding to obtain O(ρ)-approximate mechanisms for matroid-rank-sum valuations; for weighted conflict graphs we can fully drop the dependence on k to get O(ρ ρ log n). We conclude with promising initial results for deterministically truthful mechanisms that allow approximation factors based on ρ.

We study algorithms for wireless spectrum access of $n$ communication requests when interference conditions are given by the Rayleigh-fading model. This model extends the recently popular deterministic interference model based on the signal-to-interference-plus-noise ratio (SINR) using stochastic propagation to address fading effects observed in reality. We consider worst-case approximation guarantees for the two standard problems of capacity maximization (maximize the expected number of successful transmissions in a single slot) and latency minimization (minimize the expected number of slots until all transmissions were successful). Our main result is a generic reduction of Rayleigh fading to the deterministic SINR model. It allows to apply existing algorithms for the non-fading model in the Rayleigh-fading scenario while losing only a factor of O(logast n) in the approximation guarantee. This way, we obtain the first approximation guarantees for Rayleigh fading and, more fundamentally, show that non-trivial stochastic fading effects can be successfully handled using existing and future techniques for the non-fading model. Using a more detailed argument, a similar result applies even for distributed and game-theoretic capacity maximization approaches. For example, it allows to show that regret learning yields an O(log* n)-approximation with uniform power assignments. Our analytical treatment is supported by simulations illustrating the performance of regret learning and, more generally, the relationship between both models.

We study convergence of distributed protocols for power control in a non-cooperative wireless transmission scenario. There are n wireless communication requests or links that experience interference and noise. To be successful a link must satisfy an SINR constraint. Each link is a rational selfish agent that strives to be successful with the least power that is required. A classic approach to this problem is the fixed-point iteration due to Foschini and Miljanic , for which we prove the first bounds on worst-case convergence times - after roughly O(n \log n) rounds all SINR constraints are nearly satisfied. When agents try to satisfy each constraint exactly, however, links might not be successful at all. For this case, we design a novel framework for power control using regret learning algorithms and iterative discretization. While the exact convergence times must rely on a variety of parameters, we show that roughly a polynomial number of rounds suffices to make every link successful during at least a constant fraction of all previous rounds.

In modern wireless networks, devices are able to set the power for each transmission carried out. Experimental but also theoretical results indicate that such power control can improve the network capacity significantly. We study this problem in the physical interference model using SINR constraints. In the SINR capacity maximization problem, we are given n pairs of senders and receivers, located in a metric space (usually a so-called fading metric). The algorithm shall select a subset of these pairs and choose a power level for each of them with the objective of maximizing the number of simultaneous communications. This is, the selected pairs have to satisfy the SINR constraints with respect to the chosen powers. We present the first algorithm achieving a constant-factor approximation in fading metrics. The best previous results depend on further network parameters such as the ratio of the maximum and the minimum distance between a sender and its receiver. Expressed only in terms of n, they are (trivial) Omega(n) approximations. Our algorithm still achieves an O(log n) approximation if we only assume to have a general metric space rather than a fading metric. Furthermore, by using standard techniques the algorithm can also be used in single-hop and multi-hop scheduling scenarios. Here, we also get polylog(n) approximations.

We study combinatorial auctions for the secondary spectrum market. In this market, short-term licenses shall be given to wireless nodes for communication in their local neighborhood. In contrast to the primary market, channels can be assigned to multiple bidders, provided that the corresponding devices are well separated such that the interference is sufficiently low. Interference conflicts are described in terms of a conflict graph in which the nodes represent the bidders and the edges represent conflicts such that the feasible allocations for a channel correspond to the independent sets in the conflict graph.

We present and analyze simple distributed contention resolution protocols for wireless networks. In our setting, one is given n pairs of senders and receivers located in a metric space. Each sender wants to transmit a signal to its receiver at a prespecified power level, e.g., all senders use the same, uniform power level as it is typically implemented in practice. Our analysis is based on the physical model in which the success of a transmission depends on the Signal-to-Interference-plus-Noise-Ratio (SINR). The objective is to minimize the number of time slots until all signals are successfully transmitted.

In the interference scheduling problem, one is given a set of n communication requests described by pairs of points from a metric space. The points correspond to devices in a wireless network. In the directed version of the problem, each pair of points consists of a dedicated sending and a dedicated receiving device. In the bidirectional version the devices within a pair shall be able to exchange signals in both directions. In both versions, each pair must be assigned a power level and a color such that the pairs in each color class (representing pairs communicating in the same time slot) can communicate simultaneously at the specified power levels. The feasibility of simultaneous communication within a color class is defined in terms of the Signal to Interference Plus Noise Ratio (SINR) that compares the strength of a signal at a receiver to the sum of the strengths of other signals. This is commonly referred to as the "physical model" and is the established way of modelling interference in the engineering community. The objective is to minimize the number of colors as this corresponds to the time needed to schedule all requests.