Search

Exploring large-scale networks is a time consuming and expensive task which is usually operated in a complex and uncertain environment. A crucial aspect of ne

We study the revenue performance of sequential posted-price mechanisms and some natural extensions for a setting where the valuations of the buyers are drawn from a correlated distribution. Sequential posted-price mechanisms are conceptually simple mechanisms that work by proposing a "take-it-or-leave-it" offer to each buyer. We apply sequential posted-price mechanisms to single-parameter multiunit settings in which each buyer demands only one item and the mechanism can assign the service to at most k of the buyers. For standard sequential posted-price mechanisms, we prove that with the valuation distribution having finite support, no sequential posted-price mechanism can extract a constant fraction of the optimal expected revenue, even with unlimited supply. We extend this result to the case of a continuous valuation distribution when various standard assumptions hold simultaneously (i.e., everywhere-supported, continuous, symmetric, and normalized (conditional) distributions that satisfy regularity, the MHR condition, and affiliation). In fact, it turns out that the best fraction of the optimal revenue that is extractable by a sequential posted-price mechanism is proportional to the ratio of the highest and lowest possible valuation. We prove that a simple generalization of these mechanisms achieves a better revenue performance; namely, if the sequential posted-price mechanism has for each buyer the option of either proposing an offer or asking the buyer for its valuation, then a ω(1/ max{1,d}) fraction of the optimal revenue can be extracted, where d denotes the degree of dependence of the valuations, ranging from complete independence (d = 0) to arbitrary dependence (d = n - 1).

Bilateral trade is a fundamental economic scenario comprising a strategically acting buyer and seller (holding an item), each holding valuations for the item, drawn from publicly known distributions. It was recently shown that the only mechanisms that are simultaneously dominant strategy incentive compatible, strongly budget balanced, and ex-post individually rational, are fixed price mechanisms, i.e., mechanisms that are parametrised by a price p, and trade occurs if and only if the valuation of the buyer is at least p and the valuation of the seller is at most p. The gain from trade (GFT) is the increase in welfare that results from applying a mechanism. We study the GFT achievable by fixed price mechanisms. We explore this question for both the bilateral trade setting and a double auction setting where there are multiple i.i.d. unit demand buyers and sellers. We first identify a fixed price mechanism that achieves a GFT of at least 2/ r times the optimum, where r is the probability that the seller’s valuation does not exceed that of the buyer’s valuation. This extends a previous result by McAfee. Subsequently, we improve this approximation factor in an asymptotic sense, by showing that a more sophisticated rule for setting the fixed price results in a GFT within a factor O(log (1/ r)) of the optimum. This is asymptotically the best approximation factor possible. For the double auctio

We study multiprocessor scheduling games with setup times on identical machines. Given a set of scheduling policies (coordination mechanism) on the machines, each out of $n$ players chooses a machine to assign his owned job to, so as to minimize his individual completion time. Each job has a processing length and is of a certain type. Same-type jobs incur a setup overhead to the machine they are assigned to. We study the Price of Anarchy with respect to the makespan of stable assignments, that are pure Nash or strong equilibria for the underlying strategic game. We study in detail the performance of a well established preemptive scheduling mechanism. In an effort to improve over its performance, we introduce a class of mechanisms with certain properties, for which we examine existence of pure Nash and strong equilibria. We identify their performance limitations, and analyze an optimum mechanism out of this class. Finally, we point out several interesting open problems.

We study multiprocessor scheduling games with setup times on identical machines. Given a set of scheduling policies (coordination mechanism) on the machines, each out of $n$ players chooses a machine to assign his owned job to, so as to minimize his individual completion time. Each job has a processing length and is of a certain type. Same-type jobs incur a setup overhead to the machine they are assigned to. We study the Price of Anarchy with respect to the makespan of stable assignments, that are pure Nash or strong equilibria for the underlying strategic game. We study in detail the performance of a well established preemptive scheduling mechanism. In an effort to improve over its performance, we introduce a class of mechanisms with certain properties, for which we examine existence of pure Nash and strong equilibria. We identify their performance limitations, and analyze an optimum mechanism out of this class. Finally, we point out several interesting open problems.