We consider the problem to price (digital) items in order to maximize the revenue obtainable from a set of bidders. We suggest a natural monotonicity constraint on bundle prices, show that the problem remains NP-hard, and we derive a PTAS. We also discuss a special case, the highway pricing problem.

We generalize exactness to games with non-transferable utility (NTU). In an exact game for each coalition there is a core allocation on the boundary of its payoff set. Convex games with transferable utility are well-known to be exact. We study five generalizations of convexity in the NTU...

We show that in the canonical non-cooperative multilateral bargaining game, a subgameperfect equilibrium exists in pure stationary strategies, even when the space of feasible payoffs is not convex. At such an equilibrium there is no delay. We also have the converse result that randomization will...

This paper studies the sales of a single indivisible object where bidders have continuous valuations. In Grigorieva et al. [13] it was shown that, in this setting, query auctions necessarily allocate inefficiently in equilibrium. In this paper we propose a new sequential auction, called the...

To verify whether a transferable utility game is exact, one has to check a linear inequalityfor each exact balanced collection of coalitions. This paper studies the structure andproperties of the class of exact balanced collections. Comparing the definition of exactbalanced collections with the...

We study a dynamic pricing problem for a company that sells a single product to a group of customers over a finite time horizon. These customers are price sensitive and the price of today influences the group of customers of tomorrow. The objective is to set the prices over time so as to...

We consider a stochastic scheduling problem which generalizes traditional stochastic scheduling by introducing parameter uncertainty. Two classes of independent jobs have to be processed by a single machine so as to minimize the sum of expected completion times. The processing times of the jobs...

We consider a stochastic scheduling problem in which there is uncertainty about parame-ters of the probability distribution of the processing times. We restrict ourselves to the setting in which there are two different classes of jobs. The processing times of the jobs are assumed to be...

The performance of wireless networks suffers from collisions. These occur when multiplewireless nodes transmit simultaneously, and their signals interfere with each other. To reduce collisions, nodes may use a randomized protocol to regulate their behavior. An example of such a protocol is...

Increasing interest has recently been shown in analyzing the worst-case behavior of local search algorithms. In particular, the quality of local optima and the time needed to find the local optima by the simplest form of local search has been studied. This paper deals with worst-case performance...