Lack of cooperation (free riding) is one the key problems that confronts today's P2P systems. What makes this problem particularly difficult unique set challenges systems pose: large populations, high turnover, a symmetry interest, collusion, zero-cost identities, and traitors. To tackle these we model system using Generalized Prisoner's Dilemma (GPD),and propose Reciprocative decision function as basis family incentives techniques. These techniques are fullydistributed include:...

We devise a model to study the phenomenon of free-riding and free-identities in peer-to-peer systems. At heart our is user certain type, an intrinsic private parameter that reflects user's willingness contribute resources system. A decides whether or free-ride based on how current contribution cost system compares her type. impact mechanisms exclude low type users or, more realistically, penalize free-riders with degraded service. also consider dynamic scenarios arrivals departures users,...

While the fundamental premise of peer-to-peer (P2P) systems is that voluntary resource sharing among individual peers, there an inherent tension between rationality and collective welfare threatens viability these systems. This paper surveys recent research at intersection economics computer science targets design distributed consisting rational participants with diverse selfish interests. In particular, we discuss major findings open questions related to free-riding in P2P systems: factors...

We develop a model to study the phenomenon of free-riding in peer-to-peer (P2P) systems. At heart our is user certain type, an intrinsic and private parameter that reflects user's willingness contribute resources system. A decides whether or free-ride based on how current contribution cost system compares her type. When societal generosity (i.e., average type) low, intervention required order sustain present effect mechanisms exclude low type users or, more realistic, penalize free-riders...

We consider the problem of locating a facility on network represented by graph. A set strategic agents have different ideal locations for facility; cost an agent is distance between its location and facility. mechanism maps reported to wish design mechanisms that are strategyproof (SP) in sense can never benefit lying and, at same time, provide small approximation ratio with respect minimax measure. novel “hybrid” randomized provides tight 3/2 when circle (known as ring case computer...

We study anonymous posted price mechanisms for combinatorial auctions in a Bayesian framework. In mechanism, item prices are posted, then the consumers approach seller sequentially an arbitrary order, each purchasing her favorite bundle from among unsold items at prices. These simple, transparent and trivially dominant strategy incentive compatible (DSIC).We show that when agent preferences fractionally subadditive (which includes all submodular functions), there always exist that,...

We study mechanisms for candidate selection that seek to minimize the social cost, where voters and candidates are associated with points in some underlying metric space. The cost of a is sum its distances each voter. Some our work assumes these can be modeled on real line, but other results ours more general.

Simultaneous item auctions are simple and practical procedures for allocating items to bidders with potentially complex preferences. In a simultaneous auction, every bidder submits independent bids on all simultaneously. The allocation prices then resolved each separately, based solely the submitted that item. We study efficiency of Bayes-Nash equilibrium (BNE) outcomes first- second-price when have complement-free (a.k.a. subadditive) valuations. While it is known social welfare pure Nash...

In this paper we formulate the fixed budget resource allocation game to understand performance of a distributed market-based system. Multiple users decide how distribute their bids) among multiple machines according individual preferences maximize utility. We look at both efficiency and fairness equilibrium, where is evaluated through measures utility uniformity envy-freeness. show analytically simulations that despite being highly decentralized, such system converges quickly an equilibrium...

We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The establishes prophet inequalities by constructing price-based approximation algorithms, natural extension of threshold algorithms settings beyond binary selection. Our analysis takes the form an theorem: we derive sufficient conditions on prices when all weights are known in advance, then prove that resulting guarantees extend directly to settings. unifies and simplifies...

Signaling is an important topic in the study of asymmetric information economic settings. In particular, transparency available to a seller auction setting question major interest. We introduce signaling when conducting second price probabilistic good whose actual instantiation known auctioneer but not bidders. This framework can be used model impressions selling display advertising. establish several results within this framework. First, we problem computing scheme that maximizes...

We study anonymous posted price mechanisms for combinatorial auctions in a Bayesian framework. In mechanism, item prices are posted, then the consumers approach seller sequentially an arbitrary order, each purchasing her favorite bundle from among unsold items at prices. These simple, transparent and trivially dominant strategy incentive compatible (DSIC).We show that when agent preferences fractionally subadditive (which includes all submodular functions), there always exist that,...

We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The establishes prophet inequalities by constructing price-based approximation algorithms, natural extension of threshold algorithms settings beyond binary selection. Our analysis takes the form an theorem: we derive sufficient conditions on prices when all weights are known in advance, then prove that resulting guarantees extend directly to settings. unifies and simplifies...

We consider the problem of selecting fair divisions a heterogeneous divisible good among set agents. Recent work (Cohler et al., AAAI 2011) focused on designing algorithms for computing maxsum—social welfare maximizing—allocations under fairness notion envy-freeness. Maxsum allocations can also be found alternative notions such as equitability. In this paper, we examine properties these allocations. particular, provide conditions when maxsum envy-free or equitable are Pareto optimal and give...

We study the problem of allocating shared resources, such as bandwidth in computer networks and computational resources clusters, among multiple users by proportional-share market mechanism. Under this mechanism, each user partitions his budget receives a fraction resource proportional to bid. first formulate allocation game under mechanism efficiency fairness equilibrium game. present analytic simulation results demonstrating that achieves reasonable balance high degrees at equilibrium.

A strong equilibrium (Aumann 1959) is a pure Nash which resilient to deviations by coalitions. We define the price of anarchy be ratio worst case social optimum. In contrast traditional anarchy, quantifies loss incurred due both selfishness and lack coordination, isolates originated from that obtained coordination. study in two settings, one job scheduling other network creation. game we show for unrelated machines can bounded as function number size coalition. For creation at most 2. cases...

We study strategyproof (SP) mechanisms for the location of a facility on discrete graph. give full characterization SP lines and sufficiently large cycles. Interestingly, deviates from one given by Schummer Vohra (2004) continuous case. In particular, it is shown that an mechanism cycle close to dictatorial, but all agents can affect outcome, in contrast Our also used derive lower bound approximation ratio with respect social cost be achieved certain graphs. Finally, we show how...

Signaling is an important topic in the study of asymmetric information economic settings. In particular, transparency available to a seller auction setting question major interest. We introduce signaling when conducting second price probabilistic good whose actual instantiation known auctioneer but not bidders. This framework can be used model impressions selling display advertising. establish several results within this framework. First, we problem computing scheme that maximizes...

We consider the problem of locating a public facility on tree, where set n strategic agents report their locations and mechanism determines, either deterministically or randomly, location facility. The contribution this paper is twofold.First, we introduce, for first time, general clean family strategyproof (SP) mechanisms tree networks. Quite miraculously, all deterministic randomized SP that have been previously proposed can be cast as special cases family. Thus, unifies much existing...

We present an analysis framework for bounding the price of anarchy (POA) in games that have many players, as most pertinent to computer science applications. use this demonstrate that, models which POA has been studied, large is much smaller than worst-case bound. Our also differentiates between mechanisms with similar performance, such simultaneous uniform-price auctions and greedy combinatorial auctions, thereby providing new insights about are likely perform well realistic settings.

The existence of EFX allocations goods is a major open problem in fair division, even for additive valuations. current state the art that no setting where are impossible known, and yet, results known only very restricted settings, such as: (i) agents with identical valuations, (ii) 2 agents, (iii) 3 It also exists if one can leave n-1 items unallocated, n number agents. We develop new techniques allow us to push boundaries enigmatic beyond these results, (arguably) simplify proofs earlier...

A major problem in fair division is how to allocate a set of indivisible resources among agents fairly and efficiently. The goal this work characterize the tradeoffs between two well-studied measures fairness efficiency --- envy freeness up any item (EFX) for fairness, Nash welfare by saying, given constants α β, whether there exists an α-EFX allocation that guarantees β-fraction maximum (β-MNW). For additive valuations, we show ∈ [0,1], partial 1/(α+1)-MNW. This tradeoff turns out be tight...