In this paper, we analyse how a peer-to-peer sharing platform should price its service to maximize profit, when user participation increases the value of the service to others by causing positive externalities. Modelling the service as an excludable public good, we propose a bounded utility model to capture many infrastructure sharing applications with bounded network value, in which complete coverage generates finite user valuation (e.g., WiFi or hotspot). Unbounded utility models are used to capture the large-scale user interactions in social media, where the network value follows Metcalfe's or Zipf's law. For these utility models, we analyze the optimal pricing schemes in the case of heterogeneous users under complete and incomplete information of users' service valuations. We propose the concept of `price of information' (PoI) to characterize the profit loss due to lack of information, and present asymptotic PoI bounds for different utility models. We also show that the difficult-to-implement differentiated pricing scheme, which is optimal under incomplete user information, can be replaced by a simple uniform price scheme that is asymptotic optimal. Finally, we extend our pricing schemes to a two-sided market by including a new group of `pure' service users who do not contribute to the public good, and show that the platform may charge zero price to the original group of users in order to attract this pure user group.

Paid peering is controversial. Generally speaking, large access ISPs favour it, while Content Providers (CPs) do not. But is CP opposition to paid peering irrational, especially if their transferred payments can incentivize the ISP to make greater investment in the common infrastructure? To answer this question we analyze an ecosystem consisting of a single access ISP that directly interconnects with multiple CPs, doing so in two extreme situations: when paid peering is used for all the involved CPs, and when all parties agree on a settlement-free deal. We analyse the equilibrium, finding the total amount of investments and profits of the various stakeholders, when their revenues are affected by the total investment in infrastructure and the charges that result from the different agreements. Interestingly, it turns out whether or not there is benefit to a CP, depends on whether its business model is to sell content, and so it can recover part of the paid peering charge by raising prices to its customers, or if the CP obtains its revenue from ads. It also depends on the volume (in traffic units) per customer transaction, since we find that CPs with high volume per transaction will be charged less per byte, and so will contribute proportionally less to the total paid peering revenue that subsidizes the common ISP infrastructure. We also find a crucial role for the end-users' evaluation of the level of investments of the various market players. Another relevant factor is the access price that an ISP charges its customers.

In designing and managing a shared infrastructure, one must take account of the fact that its participants will make self-interested and strategic decisions about the resources that they are willing to contribute to it and/or the share of its cost that they are willing to bear. Taking proper account of the incentive issues that thereby arise, we design mechanisms that, by eliciting appropriate information from the participants, can obtain for them maximal social welfare, subject to charging payments that are sufficient to cover costs. We show that there are incentivizing roles to be played both by the payments that we ask from the participants and the specification of how resources are to be shared. New in this paper is our formulation of models for designing optimal management policies, our analysis that demonstrates the inadequacy of simple sharing policies, and our proposals for some better ones. We learn that simple policies may be far from optimal and that efficient policy design is not trivial. However, we find that optimal policies have simple forms in the limit as the number of participants becomes large.

In this article we present a theoretical analysis of the online Sum-of-Squares algorithm ( SS ) for bin packing along with several new variants. SS is applicable to any instance of bin packing in which the bin capacity B and item sizes s ( a ) are integral (or can be scaled to be so), and runs in time O ( nB ). It performs remarkably well from an average case point of view: For any discrete distribution in which the optimal expected waste is sublinear, SS also has sublinear expected waste. For any discrete distribution where the optimal expected waste is bounded, SS has expected waste at most O (log n ). We also discuss several interesting variants on SS , including a randomized O ( nB log B )-time online algorithm SS * whose expected behavior is essentially optimal for all discrete distributions. Algorithm SS * depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the NP-hard problem of determining, given a discrete distribution F , just what is the growth rate for the optimal expected waste.

We consider problems of provisioning an excludable public good amongst n potential members of a peer-to-peer system who are able to communicate information about their private preferences for the good. The cost of provisioning the good in quantity Q depends on Q, and may also depend on n, or on the final number of participating peers m. Our aim is to maximize the expected social welfare in a way that is incentive compatible, rational and budget-balanced. Although it is unfortunately almost never possible to calculate or implement a truely optimal mechanism design, we show that as the number of participants becomes large the expected social welfare that can be obtained by the optimal design is at most a factor 1+O(1/n) or 1+O(1//spl radic/n) greater than that which can be obtained with a very simple scheme that requires only payment of a fixed contribution from any agent who joins the system as a participating peer. Our first application is to a model of file sharing, in which the public good is content availability; the second concerns a problem of peering wireless local area networks, in which the public good is the availability of connectivity for roaming peers. In both problems, we can cope with the requirement that the payments be made in kind, rather than in cash.

In this paper we present a theoretical analysis of the deterministic on-line Sum of Squares algorithm (SS) for bin packing, introduced and studied experimentally in [8], along with several new variants.SS is applicable to any instance of bin packing in which the bin capacity B and item sizes s(a) are integral (or can be scaled to be so), and runs in time O(nB).It performs remarkably well from an average case point of view: For any discrete distribution in which the optimal expected waste is sublinear, SS also has sublinear expected waste.For any discrete distribution where the optimal expected waste is bounded, SS has expected waste at most O(log n).In addition, we present a randomized O(nB log B)-time on-line algorithm SS*, based on SS, whose expected behavior is essentially optimal for all discrete distributions.Algorithm SS* also depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the NP-hard problem of determining, given a discrete distribution F, just what is the growth rate for the optimal expected waste.An off-line randomized variant SS** performs well in a worst-case sense: For any list L of integer-sized items to be packed into bins of a fixed size B, the expected number of bins used by SS** is at most OPT(L) + ~.

We consider the one-dimensional bin packing problem with unit-capacity bins and item sizes chosen according to the discrete uniform distribution U{j,k}, $1 < j \leq k,$ where each item size in {1/k,2/k,. . .,j/k} has probability 1/j of being chosen. Note that for fixed j,k as $m\rightarrow\infty$ the discrete distributions U{mj,mk} approach the continuous distribution U(0,j/k], where the item sizes are chosen uniformly from the interval (0,j/k]. We show that average-case behavior can differ substantially between the two types of distributions. In particular, for all j,k with j < k-1, there exist on-line algorithms that have constant expected wasted space under U{j,k}, whereas no on-line algorithm has even o(n 1/2 ) expected waste under U(0,u] for any $0 < u \leq 1$. Our U{j,k} result is an application of a general theorem of Courcoubetis and Weber [C. Courcoubetis and R.R. Weber, Probab. Engrg. Inform. Sci., 4 (1990), pp. 447--460] that covers all discrete distributions. Under each such distribution, the optimal expected waste for a random list of n items must be either $\Theta (n)$, $\Theta (n^{1/2} )$, or O(1), depending on whether certain"perfect" packings exist. The perfect packing theorem needed for the U{j,k} distributions is an intriguing result of independent combinatorial interest, and its proof is a cornerstone of the paper.

Addresses the issue of call acceptance and routing in ATM networks. The goal is to design an algorithm that guarantees bounds on the fraction of cells lost by a call. The method proposed for call acceptance and routing does not require models describing the traffic. Each switch estimates the additional fraction of cells that would be lost if new calls were routed through the switch. The routing algorithm uses these estimates. The estimates are obtained by monitoring the switch operations and extrapolating to the situation where more calls are routed through the switch. The extrapolation is justified by a scaling property. To reduce the variance of the estimates, the switches calculate the cell loss that would occur with virtual buffers. A way to choose the sizes of the virtual buffers in order to minimize the variance is discussed. Thus, the switches constantly estimate their spare capacity. Simulations were performed using Markov fluid sources to test the validity of the approach.>

Many complex proesses can be modeled by (countably) infinite, multidimensional Markov chains. Unfortunately, cnrnmt theoretical techniques for analyzing infinite Markov chains are for the most part limited to three or fewer dimensions. In this paper we propose a computer-aided approach to the analy-sis of higher-dimensional domains, using several open problems about the average-case behavior of the Best Fit bin packing algo-rithm as case studies. We show how to use dynamic and liiear programming to construct potential functions thal when applied to suitably modified multi-step versions of our original Markov chain, yield drifts that are bounded away fmm O. This enables us to completely classify the expected behavior of Best Fit under dis-crete uniform distributions U{J, K) when K is small. (Under U { J, K}, the allowed item sizes are i/K, 1 S i S J, with all J pos-sibilities equally likely.) In addition, we can answer yes to the long-standing open question of whether there exist distributions of this form for which Best Fit yields linearly-growing waste. The proof of the latter theorem relies on a 24-hour computation, and although its validity does not depend on the linear progra-mmingpackage we used, it does tely on the correctness of our dynamic progr smming code and of our computer’s implementation of the IEEE floating point standard.

We consider the average case behavior of onedmensional bin paekmg algorithms in the case where bins have unit capacity and item sizes are chosen according to the ' 'dficrete uniform" distribution U~; k), 1 s j < k, where each item size in the set {llk,21k,..., ji k) has probability 1/j of beiig chosen.Note that for fixed j,k the distributions U{?nj;mk]' approach the continuous distribution U(O, jlk] as m A W, where in U(O, jl k] the item sizes are chosen uniformly horn the half-open interval (O,jik].In this paper, we show that average case behavior can differ substantially under the two types of distributions.We show that for all j, k, j < k-1, there exist on-line algorithms that have constant expected waste under U~; k], whereas no on-line algorithm can have less than C2(n1'2) waste under U(O, U] for any u s 1. Conmariwise, although the First Fit Decreasing (off-line) algorithm has constant expected waste under U(O, u] for all u < 1/2,