We consider the impact of fairness requirements on the social efficiency of truthful mechanisms for trade, focusing on Bayesian bilateral-trade settings. Unlike the full information case in which all gains-from-trade can be realized and equally split between the two parties, in the private information setting, equitability has devastating welfare implications (even if only required to hold ex-ante). We thus search for an alternative fairness notion and suggest requiring the mechanism to be KS-fair: it must ex-ante equalize the fraction of the ideal utilities of the two traders. We show that there is always a KS-fair (simple) truthful mechanism with expected gains-from-trade that are half the optimum, but always ensuring any better fraction is impossible (even when the seller value is zero). We then restrict our attention to trade settings with a zero-value seller and a buyer with valuation distribution that is Regular or MHR, proving that much better fractions can be obtained under these conditions, with simple posted-price mechanisms.

We consider the problem of allocating heterogeneous and indivisible goods among strategic agents, with preferences over subsets of goods, when there is no medium of exchange. This model captures the well studied problem of fair allocation of indivisible goods. Serial-quota mechanisms are allocation mechanisms where there is a predefined order over agents, and each agent in her turn picks a predefined number of goods from the remaining goods. These mechanisms are clearly strategy-proof, non-bossy, and neutral. Are there other mechanisms with these properties?

The "EIP-1559 algorithm" is used by the Ethereum blockchain to assemble transactions into blocks. While prior work has studied it under the assumption that bidders are "impatient", we analyze it under the assumption that bidders are "patient", which better corresponds to the fact that unscheduled transactions remain in the mempool and can be scheduled at a later time. We show that with "patient" bidders, this algorithm produces schedules of near-optimal welfare, provided it is given a mild resource augmentation (that does not increase with the time horizon). We prove some generalizations of the basic theorem, establish lower bounds that rule out several candidate improvements and extensions, and propose several questions for future work.

We study the problem of designing a two-sided market (double auction) to maximize the gains from trade (social welfare) under the constraints of (dominant-strategy) incentive compatibility and budget-balance. Our goal is to do so for an unknown distribution from which we are given a polynomial number of samples. Our first result is a general impossibility for the case of correlated distributions of values even between just one seller and two buyers, in contrast to the case of one seller and one buyer (bilateral trade) where this is possible. Our second result is an efficient learning algorithm for one seller and two buyers in the case of independent distributions which is based on a novel algorithm for computing optimal mechanisms for finitely supported and explicitly given independent distributions. Both results rely heavily on characterizations of (dominant-strategy) incentive compatible mechanisms that are strongly budget-balanced.

We consider a principal seller with m heterogeneous products to sell to an additive buyer over independent items. The principal can offer an arbitrary menu of product bundles, but faces competition from smaller and more agile single-item sellers. The single-item sellers choose their prices after the principal commits to a menu, potentially under-cutting the principal's offerings. We explore to what extent the principal can leverage the ability to bundle products together to extract revenue.

A prevalent assumption in auction theory is that the auctioneer has full control over the market and that the allocation she dictates is final. In practice, however, agents might be able to resell acquired items in an aftermarket. A prominent example is the market for carbon emission allowances. These allowances are commonly allocated by the government using uniform-price auctions, and firms can typically trade these allowances among themselves in an aftermarket that may not be fully under the auctioneer's control. While the uniform-price auction is approximately efficient in isolation, we show that speculation and resale in aftermarkets might result in a significant welfare loss. Motivated by this issue, we consider three approaches, each ensuring high equilibrium welfare in the combined market. The first approach is to adopt smooth auctions such as discriminatory auctions. This approach is robust to correlated valuations and to participants acquiring information about others' types. However, discriminatory auctions have several downsides, notably that of charging bidders different prices for identical items, resulting in fairness concerns that make the format unpopular. Two other approaches we suggest are either using posted-pricing mechanisms, or using uniform-price auctions with anonymous reserves. We show that when using balanced prices, both these approaches ensure high equilibrium welfare in the combined market. The latter also inherits many of the benefits from uniform-price auctions such as price discovery, and can be introduced with a minor modification to auctions currently in use to sell carbon emission allowances.

In this paper we revisit the notion of simplicity in mechanisms. We consider a seller of m heterogeneous items, facing a single buyer with valuation v. We observe that previous attempts to define complexity measures often fail to classify mechanisms that are intuitively considered simple (e.g., the "selling separately" mechanism) as such. We suggest to view a menu as simple if a bundle that maximizes the buyer's profit can be found by conducting a few primitive operations that are considered simple. The primitive complexity of a menu is the number of primitive operations needed to (adaptively) find a profit-maximizing entry in the menu. In this paper, the primitive operation that we study is essentially computing the outcome of the "selling separately" mechanism.

We explore the performance of polynomial-time incentive-compatible mechanisms in single-crossing domains. Single-crossing domains were extensively studied in the economics literature. Roughly speaking, a domain is single crossing if monotonicity characterizes incentive compatibility (intuitively, an algorithm is monotone if a bidder that "improves" his valuation is allocated a better outcome). That is, single-crossing domains are the standard mathematical formulation of domains that are informally known as "single parameter". In all major single-crossing domains studied so far (e.g., welfare maximization in various auctions with single-minded bidders, makespan minimization on related machines), the performance of the best polynomial-time incentive-compatible mechanisms matches the performance of the best polynomial-time non-incentive-compatible algorithms. Our two main results make progress in understanding the power of incentive-compatible polynomial-time mechanisms in single-crossing domains:

We consider fair allocation of a set M of indivisible goods to n equally-entitled agents, with no monetary transfers. Every agent i has a valuation function vi from some given class of valuation functions. A share s is a function that maps a pair (vi,n) to a non-negative value, with the interpretation that if an allocation of M to n agents fails to give agent i a bundle of value at least equal to s(vi,n), this serves as evidence that the allocation is not fair towards i. For such an interpretation to make sense, we would like the share to be feasible, meaning that for any valuations in the class, there is an allocation that gives every agent at least her share. The maximin share (MMS) was a natural candidate for a feasible share for additive valuations. However, Kurokawa, Procaccia and Wang [2018] show that it is not feasible.

We study a market of investments on networks, where each agent (vertex) can invest in any enterprise linked to her, and at the same time, raise capital for her firm’s enterprise from other agents she is linked to. Failing to raise sufficient capital results with the firm defaulting, being unable to invest in others. Our main objective is to examine the role of collateral contracts in handling the strategic risk that can propagate to a systemic risk throughout the network in a cascade of defaults. We take a mechanism-design approach and solve for the optimal scheme of collateral contracts that capital raisers offer their investors. These contracts aim at sustaining the efficient level of investment as a unique Nash equilibrium, while minimizing the total collateral.

Cloud computing customers often submit repeating jobs and computation pipelines on approximately regular schedules, with arrival and running times that exhibit variance. This pattern, typical of training tasks in machine learning, allows customers to partially predict future job requirements. We develop a model of cloud computing platforms that receive statements of work (SoWs) in an online fashion. The SoWs describe future jobs whose arrival times and durations are probabilistic, and whose utility to the submitting agents declines with completion time. The arrival and duration distributions, as well as the utility functions, are considered private customer information and are reported by strategic agents to a scheduler that is optimizing for social welfare.

We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties ex-post. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations.

Mechanisms with money are commonly designed under the assumption that agents are quasi-linear, meaning they have linear disutility for spending money. We study the implications when agents with non-linear (specifically, convex) disutility for payments participate in mechanisms designed for quasi-linear agents. We first show that any mechanism that is truthful for quasi-linear buyers has a simple best response function for buyers with non-linear disutility from payments, in which each bidder simply scales down her value for each potential outcome by a fixed factor, equal to her target return on investment (ROI). We call such a strategy ROI-optimal. We prove the existence of a Nash equilibrium in which agents use ROI-optimal strategies for a general class of allocation problems. Motivated by online marketplaces, we then focus on simultaneous second-price auctions for additive bidders and show that all ROI-optimal equilibria in this setting achieve constant-factor approximations to suitable welfare and revenue benchmarks.

We consider the problem of fair allocation of indivisible goods to n agents, with no transfers. When agents have equal entitlements, the well established notion of the maximin share (MMS) serves as an attractive fairness criterion, where to qualify as fair, an allocation needs to give every agent at least a substantial fraction of her MMS. In this paper we consider the case of arbitrary (unequal) entitlements. We explain shortcomings in previous attempts that extend the MMS to unequal entitlements. Our conceptual contribution is the introduction of a new notion of a share, the AnyPrice share (APS), that is appropriate for settings with arbitrary entitlements. The AnyPrice share of an agent is the value she can guarantee to herself if she is given a budget equal to her entitlement, and she buys her highest value affordable set when items are adversarially priced with a total price equal to the total entitlements. Even for the equal entitlements case, this notion is new, and satisfies APS ≥ MMS, where the inequality is sometimes strict. We also present an alternative definition for the APS as a maximization problem (a fractional version of the MMS), and provide comparisons between the APS and previous notions of fairness. Our main result concerns additive valuations and arbitrary entitlements, for which we provide a polynomial-time algorithm that gives every agent at least a 3/5-fraction of her APS. This algorithm can also be viewed as providing a strategy in a certain natural bidding game, and this strategy secures each agent that uses it at least a 3/5-fraction of her APS, regardless of the strategies used by other agents.

We consider a robust version of the revenue maximization problem, where a single seller wishes to sell n items to a single unit-demand buyer. In this robust version, the seller knows the buyer's marginal value distribution for each item separately, but not the joint distribution, and prices the items to maximize revenue in the worst case over all compatible correlation structures. We devise a computationally efficient (polynomial in the support size of the marginals) algorithm that computes the worst-case joint distribution for any choice of item prices. And yet, in sharp contrast to the additive buyer case [Carroll, 2017], we show that it is NP-hard to approximate the optimal choice of prices to within any factor better than n1/2-ε. For the special case of marginal distributions that satisfy the monotone hazard rate property, we show how to guarantee a constant fraction of the optimal worst-case revenue using item pricing; this pricing equates revenue across all possible correlations and can be computed efficiently.

We consider the problem of welfare (and gains-from-trade) maximization in two-sided markets using simple mechanisms that are prior-independent. The seminal impossibility result of Myerson and Satterthwaite [1983] shows that even for bilateral trade, there is no feasible (individually rational, truthful, and budget balanced) mechanism that has welfare as high as the optimal-yet-infeasible VCG mechanism, which attains maximal welfare but runs a deficit. On the other hand, the optimal feasible mechanism needs to be carefully tailored to the Bayesian prior, and even worse, it is known to be extremely complex, eluding a precise description. In this paper we present Bulow-Klemperer-style results to circumvent these hurdles in double-auction market settings. We suggest using the Buyer Trade Reduction (BTR) mechanism, a variant of McAfee's mechanism, which is feasible and simple (in particular, it is deterministic, truthful, prior-independent, and anonymous). First, in the setting in which the values of the buyers and of the sellers are sampled independently and identically from the same distribution, we show that for any such market of any size, BTR with one additional buyer whose value is sampled from the same distribution has expected welfare at least as high as the optimal-yet-infeasible VCG mechanism in the original market. We then move to a more general setting in which the values of the buyers are sampled from one distribution, and those of the sellers from another, focusing on the case where the buyers' distribution first-order stochastically dominates the sellers' distribution. We present both upper bounds and lower bounds on the number of buyers that, when added, guarantees that BTR in the augmented market achieve welfare at least as high as the optimal in the original market. Our lower bounds extend to a large class of mechanisms, and all of our positive and negative results extend to adding sellers instead of buyers. In addition, we present positive results about the usefulness of pricing at a sample for welfare maximization (and more precisely, for gains-from-trade approximation) in two-sided markets under the above two settings, which to the best of our knowledge are the first sampling results in this context.

We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and her value for a set of items is additive. The seller aims to maximize his revenue. We suggest using the a priori better of two simple pricing methods: selling the items separately , each at its optimal price, and bundling together , in which the entire set of items is sold as one bundle at its optimal price. We show that for any distribution, this mechanism achieves a constant-factor approximation to the optimal revenue. Beyond its simplicity, this is the first computationally tractable mechanism to obtain a constant-factor approximation for this multi-parameter problem. We additionally discuss extensions to multiple buyers and to valuations that are correlated across items.

The seminal impossibility result of Myerson and Satterthwaite [1983] states that for bilateral trade, there is no mechanism that is individually rational (IR), incentive compatible (IC), weakly budget balanced, and efficient. This has led follow-up work on two-sided trade settings to weaken the efficiency requirement and consider approximately efficient simple mechanisms, while still demanding the other properties. The current state-of-the-art of such mechanisms for two-sided markets can be categorized as giving one (but not both) of the following two types of approximation guarantees on the gains from trade : a constant ex-ante guarantee, measured with respect to the second-best efficiency benchmark, or an asymptotically optimal ex-post guarantee, measured with respect to the first-best efficiency benchmark. Here the second-best efficiency benchmark refers to the highest gains from trade attainable by any IR, IC and weakly budget balanced mechanism, while the first-best efficiency benchmark refers to the maximum gains from trade (attainable by the VCG mechanism, which is not weakly budget balanced).

We study combinatorial auctions with bidders that exhibit endowment effect. In most of the previous work on cognitive biases in algorithmic game theory (e.g., [Kleinberg and Oren, EC'14] and its follow-ups) the focus was on analyzing the implications and mitigating their negative consequences. In contrast, in this paper we show how in some cases cognitive biases can be harnessed to obtain better outcomes. Specifically, we study Walrasian equilibria in combinatorial markets. It is well known that Walrasian equilibria exist only in limited settings, e.g., when all valuations are gross substitutes, but fails to exist in more general settings, e.g., when the valuations are submodular. We consider combinatorial settings in which bidders exhibit the endowment effect, that is, their value for items increases with ownership. Our main result shows that when the valuations are submodular, even a mild degree of endowment effect is sufficient to guarantee the existence of Walrasian equilibria. In fact, we show that in contrast to Walrasian equilibria with standard utility maximizing bidders -- in which the equilibrium allocation must be efficient -- when bidders exhibit endowment effect any local optimum can be an equilibrium allocation. Our techniques reveal interesting connections between the LP relaxation of combinatorial auctions and local maxima. We also provide lower bounds on the intensity of the endowment effect that the bidders must have in order to guarantee the existence of a Walrasian equilibrium in various settings.

The literature on "mechanism design from samples," which has flourished in recent years at the interface of economics and computer science, offers a bridge between the classic computer-science approach of worst-case analysis (corresponding to "no samples") and the classic economic approach of average-case analysis for a given Bayesian prior (conceptually corresponding to the number of samples tending to infinity). Nonetheless, the two directions studied so far are two extreme and almost diametrically opposed directions: that of asymptotic results where the number of samples grows large, and that where only a single sample is available. In this paper, we take a first step toward understanding the middle ground that bridges these two approaches: that of a fixed number of samples greater than one. In a variety of contexts, we ask what is possibly the most fundamental question in this direction: are two samples really better than one sample?. We present a few surprising negative results, and complement them with our main result: showing that the worst-case, over all regular distributions, expected-revenue guarantee of the Empirical Revenue Maximization algorithm given two samples is greater than that of this algorithm given one sample. The proof is technically challenging, and provides the first result that shows that some deterministic mechanism constructed using two samples can guarantee more than one half of the optimal revenue.

We study revenue maximization by deterministic mechanisms for the simplest case for which Myerson's characterization does not hold: a single seller selling two items, with independently distributed values, to a single additive buyer. We prove that optimal mechanisms are submodular and hence monotone. Furthermore, we show that in the IID case, optimal mechanisms are symmetric. Our characterizations are surprisingly non-trivial, and we show that they fail to extend in several natural ways, e.g. for correlated distributions or more than two items. In particular, this shows that the optimality of symmetric mechanisms does not follow from the symmetry of the IID distribution.

We define a generalization of the classical secretary problem called the matroid secretary problem . In this problem, the elements of a matroid are presented to an online algorithm in uniformly random order. When an element arrives, the algorithm observes its value and must make an irrevocable decision whether or not to accept it. The accepted elements must form an independent set, and the objective is to maximize the combined value of these elements. We present an O (log k )-competitive algorithm for general matroids (where k is the rank of the matroid), and constant-competitive algorithms for several special cases including graphic matroids, truncated partition matroids, and bounded degree transversal matroids. We leave as an open question the existence of constant-competitive algorithms for general matroids. Our results have applications in welfare-maximizing online mechanism design for domains in which the sets of simultaneously satisfiable agents form a matroid.

We consider a price competition between two sellers of perfect-complement goods. Each seller posts a price for the good it sells, but the demand is determined according to the sum of prices. This is a classic model by Cournot (1838), who showed that in this setting a monopoly that sells both goods is better for the society than two competing sellers. We show that non-trivial pure Nash equilibria always exist in this game. We also quantify Cournot's observation with respect to both the optimal welfare and the monopoly revenue. We then prove a series of mostly negative results regarding the convergence of best response dynamics to equilibria in such games.

In this work we derive a variant of the classic Glivenko-Cantelli Theorem, which asserts uniform convergence of the empirical Cumulative Distribution Function (CDF) to the CDF of the underlying distribution. Our variant allows for tighter convergence bounds for extreme values of the CDF. We apply our bound in the context of revenue learning, which is a well-studied problem in economics and algorithmic game theory. We derive sample-complexity bounds on the uniform convergence rate of the empirical revenues to the true revenues, assuming a bound on the k'th moment of the valuations, for any (possibly fractional) k > 1. For uniform convergence in the limit, we give a complete characterization and a zero-one law: if the first moment of the valuations is finite, then uniform convergence almost surely occurs; conversely, if the first moment is infinite, then uniform convergence almost never occurs.

We consider a monopolist that is selling n items to a single additive buyer, where the buyer's values for the items are drawn according to independent distributions F1,F2,…,Fn that possibly have unbounded support. It is well known that - unlike in the single item case - the revenue-optimal auction (a pricing scheme) may be complex, sometimes requiring a continuum of menu entries. It is also known that simple auctions with a finite bounded number of menu entries can extract a constant fraction of the optimal revenue. Nonetheless, the question of the possibility of extracting an arbitrarily high fraction of the optimal revenue via a finite menu size remained open.

We consider a network of sellers, each selling a single product, where the graph structure represents pair-wise complementarities between products. We study how the network structure affects revenue and social welfare of equilibria of the pricing game between the sellers. We prove positive and negative results, both of "Price of Anarchy" and of "Price of Stability" type, for special families of graphs (paths, cycles) as well as more general ones (trees, graphs). We describe best-reply dynamics that converge to non-trivial equilibrium in several families of graphs, and we use these dynamics to prove the existence of approximately-efficient equilibria.

We consider the problem of designing mechanisms that interact with strategic agents through strategic intermediaries (or mediators), and investigate the cost to society due to the mediators' strategic behavior. Selfish agents with private information are each associated with exactly one strategic mediator, and can interact with the mechanism exclusively through that mediator. Each mediator aims to optimize the combined utility of his agents, while the mechanism aims to optimize the combined utility of all agents. We focus on the problem of facility location on a metric induced by a publicly known tree. With non-strategic mediators, there is a dominant strategy mechanism that is optimal. We show that when both agents and mediators act strategically, there is no dominant strategy mechanism that achieves any approximation. We, thus, slightly relax the incentive constraints, and define the notion of a two-sided incentive compatible mechanism. We show that the 3-competitive deterministic mechanism suggested by Procaccia and Tennenholtz (2009) and Dekel et al. (2010) for lines extends naturally to trees, and is still 3-competitive as well as two-sided incentive compatible. This is essentially the best possible. We then show that by allowing randomization one can construct a 2-competitive randomized mechanism that is two-sided incentive compatible, and this is also essentially tight. This result also closes a gap left in the work of Procaccia and Tennenholtz (2009) and Lu et al. (2009) for the simpler problem of designing strategy-proof mechanisms for weighted agents with no mediators on a line, while extending to the more general model of trees. We also investigate a further generalization of the above setting where there are multiple levels of mediators.

In various markets where sellers compete in price, price oscillations are observed rather than convergence to equilibrium. Such fluctuations have been empirically observed in the retail market for gasoline, in airline pricing and in the online sale of consumer goods. Motivated by this, we study a model of price competition in which equilibria rarely exist. We seek to analyze the welfare, despite the nonexistence of equilibria, and present welfare guarantees as a function of the market power of the sellers. We first study best response dynamics in markets with sellers that provide a homogeneous good, and show that except for a modest number of initial rounds, the welfare is guaranteed to be high. We consider two variations: in the first the sellers have full information about the buyer's valuation. Here we show that if there are n items available across all sellers and nmax is the maximum number of items controlled by any given seller, then the ratio of the optimal welfare to the achieved welfare will be at most log n/(n-nmax + 1))+1. As the market power of the largest seller diminishes, the welfare becomes closer to optimal. In the second variation we consider an extended model in which sellers have uncertainty about the buyer's valuation. Here we similarly show that the welfare improves as the market power of the larger seller decreases, yet with a worse ratio of n/(n-nmax + 1). Our welfare bounds in both cases are essentially tight. The exponential gap in welfare between the two variations quantifies the value of accurately learning the buyer's valuation in such settings.

It is widely believed that computing payments needed to induce truthful bidding is somehow harder than simply computing the allocation. We show that the opposite is true: creating a randomized truthful mechanism is essentially as easy as a single call to a monotone allocation rule. Our main result is a general procedure to take a monotone allocation rule for a single-parameter domain and transform it (via a black-box reduction) into a randomized mechanism that is truthful in expectation and individually rational for every realization. The mechanism implements the same outcome as the original allocation rule with probability arbitrarily close to 1, and requires evaluating that allocation rule only once. We also provide an extension of this result to multiparameter domains and cycle-monotone allocation rules, under mild star-convexity and nonnegativity hypotheses on the type space and allocation rule, respectively. Because our reduction is simple, versatile, and general, it has many applications to mechanism design problems in which re-evaluating the allocation rule is either burdensome or informationally impossible. Applying our result to the multiarmed bandit problem, we obtain truthful randomized mechanisms whose regret matches the information-theoretic lower bound up to logarithmic factors, even though prior work showed this is impossible for truthful deterministic mechanisms. We also present applications to offline mechanism design, showing that randomization can circumvent a communication complexity lower bound for deterministic payments computation, and that it can also be used to create truthful shortest path auctions that approximate the welfare of the VCG allocation arbitrarily well, while having the same running time complexity as Dijkstra's algorithm.

We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer hasa value for each item drawn independently according to(non-identical) distributions, and his value for a set ofitems is additive. The seller aims to maximize his revenue.It is known that an optimal mechanism in this setting maybe quite complex, requiring randomization [19] and menusof infinite size [15]. Hart and Nisan [17] have initiated astudy of two very simple pricing schemes for this setting:item pricing, in which each item is priced at its monopolyreserve; and bundle pricing, in which the entire set ofitems is priced and sold as one bundle. Hart and Nisan [17]have shown that neither scheme can guarantee more thana vanishingly small fraction of the optimal revenue. Insharp contrast, we show that for any distributions, thebetter of item and bundle pricing is a constant-factorapproximation to the optimal revenue. We further discussextensions to multiple buyers and to valuations that arecorrelated across items.

Central results in economics guarantee the existence of efficient equilibria for various classes of markets. An underlying assumption in early work is that agents are price-takers, i.e., agents honestly report their true demand in response to prices. A line of research in economics, initiated by Hurwicz (1972), is devoted to understanding how such markets perform when agents are strategic about their demands. This is captured by the Walrasian Mechanism that proceeds by collecting reported demands, finding clearing prices in the reported market via an ascending price tatonnement procedure, and returns the resulting allocation. Similar mechanisms are used, for example, in the daily opening of the New York Stock Exchange and the call market for copper and gold in London.

We study the complexity required for the implementation of multi-agent contracts under a variety of solution concepts. A contract is a mapping from strategy profiles to outcomes. Practical implementation of a contract requires it to be ''simple'', an illusive concept that needs to be formalized. A major source of complexity is the burden involving verifying the contract fulfillment (for example in a court of law). Contracts which specify a small number of outcomes are easier to verify and are less prone to disputes. We therefore measure the complexity of a contract by the number of outcomes it specifies. Our approach is general in the sense that all strategic interaction represented by a normal form game are allowed. The class of solution concepts we consider is rather exhaustive and includes Nash equilibrium with both pure and mixed strategies, dominant strategy implementation, iterative elimination of dominated strategies and strong equilibria.

We consider a single buyer with a combinatorial preference that would like to purchase related products and services from different vendors,where each vendor supplies exactly one product. We study the general case where subsets of products can be substitutes as well as complementary and analyze the game that is induced on the vendors, where a vendor's strategy is the price that he asks for his product. This model generalizes both Bertrand competition (where vendors are perfect substitutes) and Nash bargaining (where they are perfect complements), and captures a wide variety of scenarios that can appear in complex crowd sourcing or in automatic pricing of related products.

We consider a multiround auction setting motivated by pay-per-click auctions for Internet advertising. In each round the auctioneer selects an advertiser and shows her ad, which is then either clicked or not. An advertiser derives value from clicks; the value of a click is her private information. Initially, neither the auctioneer nor the advertisers have any information about the likelihood of clicks on the advertisements. The auctioneer's goal is to design a (dominant strategies) truthful mechanism that (approximately) maximizes the social welfare. If the advertisers bid their true private values, our problem is equivalent to the multi-armed bandit problem, and thus can be viewed as a strategic version of the latter. In particular, for both problems the quality of an algorithm can be characterized by regret, the difference in social welfare between the algorithm and the benchmark which always selects the same “best” advertisement. We investigate how the design of multi-armed bandit algorithms is affected by the restriction that the resulting mechanism must be truthful. We find that deterministic truthful mechanisms have certain strong structural properties---essentially, they must separate exploration from exploitation---and they incur much higher regret than the optimal multi-armed bandit algorithms. Moreover, we provide a truthful mechanism which (essentially) matches our lower bound on regret.

This paper studies the role of information asymmetries in second price, common value auctions. Motivated by information structures that arise commonly in applications such as online advertising, we seek to understand what types of information asymmetries lead to substantial reductions in revenue for the auctioneer. One application of our results concerns online advertising auctions in the presence of "cookies," which allow individual advertisers to recognize advertising opportunities for users who, for example, are customers of their websites. Cookies create substantial information asymmetries both ex ante and at the interim stage, when advertisers form their beliefs. The paper proceeds by first introducing a new refinement of Nash equilibrium, which we call "tremble robust equilibrium" (TRE), which overcomes the problem of multiplicity of equilibria in many domains of interest. Second, we consider a special information structure, where only one bidder has access to superior information, and show that the seller's revenue in the unique TRE is equal to the expected value of the object conditional on the lowest possible signal, no matter how unlikely it is that this signal is realized. Thus, if cookies identify especially good users, revenue may not be affected much, but if cookies can (even occasionally) be used to identify very poor users, the revenue consequences are severe. In the third part of the paper, we study the case where multiple bidders may be informed, providing additional characterizations of the impact of information structure on revenue. Finally, we consider richer market designs that ensure greater revenue for the auctioneer, for example by auctioning the right to participate in the mechanism.

In this paper we show that payment computation essentially does not present any obstacle in designing truthful mechanisms, even for multi-parameter domains, and even when we can only call the allocation rule once. We present a general reduction that takes any allocation rule which satisfies "cyclic monotonicity" (a known necessary and sufficient condition for truthfulness) and converts it to a truthful mechanism using a single call to the allocation rule, with arbitrarily small loss to the expected social welfare.

We study scenarios where multiple sellers of a homogeneous good compete on prices, where each seller can only sell to some subset of the buyers. Crucially, sellers cannot price-discriminate between buyers. We model the structure of the competition by a graph (or hyper-graph), with nodes representing the sellers and edges representing populations of buyers. We study equilibria in the game between the sellers, prove that they always exist, and present various structural, quantitative, and computational results about them. We also analyze the equilibria completely for a few cases. Many questions are left open.

Complements between goods--where one good takes on added value in the presence of another--have been a thorn in the side of algorithmic mechanism designers. On the one hand, complements are common in the standard motivating applications for combinatorial auctions, like spectrum license auctions. On the other, welfare maximization in the presence of complements is notoriously difficult, and this intractability has stymied theoretical progress in the area. For example, there are no known positive results for combinatorial auctions in which bidder valuations are multi-parameter and non-complement-free, other than the relatively weak results known for general valuations.

We study sequential voting with two alternatives, in a setting with utility externalities: as usual, each voter has a private preference over the candidates and likes her favorite candidate to win, but additionally, a voter values voting for the chosen winner (which is determined by the majority or super-majority of votes). This model aims to capture voting behavior ("likes") in social networks which are publicly observed and sequential, and in which people care about their "public image" as determined by their votes and the socially accepted outcome (the chosen winner). Unlike in voting with no externalities, voters act strategically although there are only two alternatives, as they rather vote against their preferred candidate if the other is to win. We present two rather surprising results that are derived from the strategic behavior of the voters. First, we show that in sequential voting in which a winner is declared when the gap in votes is at least some large value $M$, increasing $M$ does not result in the aggregation of preferences of more voters in the decision, as voters start a herd on one candidate once a small lead in votes for that candidate develops. Furthermore, the threshold lead for such a herd to start is independent of M. Secondly, we show that there are cases in which sequential voting is strictly better than simultaneous voting, in the sense that it chooses the most preferred alternative with higher probability.

We consider the problem of designing revenue maximizing online posted-price mechanisms when the seller has limited supply. A seller has k identical items for sale and is facing n potential buyers ("agents") that are arriving sequentially. Each agent is interested in buying one item. Each agent's value for an item is an independent sample from some fixed (but unknown) distribution with support [0,1]. The seller offers a take-it-or-leave-it price to each arriving agent (possibly different for different agents), and aims to maximize his expected revenue.

Many large decentralized systems rely on information propagation to ensure their proper function. We examine a common scenario in which only participants that are aware of the information can compete for some reward, and thus informed participants have an incentive not to propagate information to others. One recent example in which such tension arises is the 2009 DARPA Network Challenge (finding red balloons). We focus on another prominent example: Bitcoin, a decentralized electronic currency system.

The buying and selling of information is taking place at a scale unprecedented in the history of commerce, thanks to the formation of online marketplaces for user data. Data providing agencies sell user information to advertisers to allow them to match ads to viewers more effectively. In this paper we study the design of optimal mechanisms for a monopolistic data provider to sell information to a buyer, in a model where both parties have (possibly correlated) private signals about a state of the world, and the buyer uses information learned from the seller, along with his own signal, to choose an action (e.g., displaying an ad) whose payoff depends on the state of the world.

No abstract available.

We study the problem of selling identical items to n unit-demand bidders in a setting in which the total supply of items is unknown to the mechanism. Items arrive dynamically, and the seller must make the allocation and payment decisions online with the goal of maximizing social welfare. We consider two models of unknown supply: the adversarial supply model, in which the mechanism must produce a welfare guarantee for any arbitrary supply, and the stochastic supply model, in which supply is drawn from a distribution known to the mechanism, and the mechanism need only provide a welfare guarantee in expectation.

It is widely believed that computing payments needed to induce truthful bidding is somehow harder than simply computing the allocation. We show that the opposite is true for single-parameter domains: creating a randomized truthful mechanism is essentially as easy as a single call to a monotone allocation function. Our main result is a general procedure to take a monotone allocation rule and transform it (via a black-box reduction) into a randomized mechanism that is truthful in expectation and individually rational for every realization. Moreover, the mechanism implements the same outcome as the original allocation rule with probability arbitrarily close to 1, and requires evaluating that allocation rule only once.

In many multiagent domains a set of agents exert effort towards a joint outcome, yet the individual effort levels cannot be easily observed. A typical example for such a scenario is routing in communication networks, where the sender can only observe whether the packet reached its destination, but often has no information about the actions of the intermediate routers, which influences the final outcome. We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome. In a companion paper we devise and study a basic ''combinatorial agency'' model for this setting, where the principal is restricted to inducing a pure Nash equilibrium. Here we study various implications of this restriction. First, we show that, in contrast to the case of observable efforts, inducing a mixed-strategies equilibrium may be beneficial for the principal. Second, we present a sufficient condition for technologies for which no gain can be generated. Third, we bound the principal's gain for various families of technologies. Finally, we study the robustness of mixed equilibria to coalitional deviations and the computational hardness of the optimal mixed equilibria.

We study online pricing problems in markets with cancellations, i.e., markets in which prior allocation decisions can be revoked, but at a cost. In our model, a seller receives requests online and chooses which requests to accept, subject to constraints on the subsets of requests which may be accepted simultaneously. A request, once accepted, can be canceled at a cost which is a fixed fraction of the request value. This scenario models a market for web advertising campaigns, in which the buyback cost represents the cost of canceling an existing contract.

We consider a multi-round auction setting motivated by pay-per-click auctions for Internet advertising. In each round the auctioneer selects an advertiser and shows her ad, which is then either clicked or not. An advertiser derives value from clicks; the value of a click is her private information. Initially, neither the auctioneer nor the advertisers have any information about the likelihood of clicks on the advertisements. The auctioneer's goal is to design a (dominant strategies) truthful mechanism that (approximately) maximizes the social welfare.

The classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an element must be either selected or discarded upon its arrival, and this decision is irrevocable. Constant-competitive algorithms are known for the classical secretary problems (see, e.g., the survey of Freeman [7]) and several variants. We study the following two extensions of the secretary problem: In the discounted secretary problem, there is a time-dependent “discount” factor d(t), and the benefit derived from selecting an element/secretary e at time t is d(t)·v(e). For this problem with arbitrary (not necessarily decreasing) functions d(t), we show a constant-competitive algorithm when the expected optimum is known in advance. With no prior knowledge, we exhibit a lower bound of , and give a nearly-matching O (log n)-competitive algorithm. In the weighted secretary problem, up to K secretaries can be selected; when a secretary is selected (s)he must be irrevocably assigned to one of K positions, with position k having weight w(k), and assigning object/secretary e to position k has benefit w(k) · v(e). The goal is to select secretaries and assign them to positions to maximize Σe,k w(k) · v(e) · xek where xek is an indicator variable that secretary e is assigned position k. We give constant-competitive algorithms for this problem. Most of these results can also be extended to the matroid secretary case (Babaioff et al. [2]) for a large family of matroids with a constant-factor loss, and an O(log rank) loss for general matroids. These results are based on a reduction from various matroids to partition matroids which present a unified approach to many of the upper bounds of Babaioff et al. These problems have connections to online mechanism design (see, e.g., Hajiaghayi et al. [9]). All our algorithms are monotone, and hence lead to truthful mechanisms for the corresponding online auction problems.

In this article, we are interested in general techniques for designing mechanisms that approximate the social welfare in the presence of selfish rational behavior. We demonstrate our results in the setting of Combinatorial Auctions (CA). Our first result is a general deterministic technique to decouple the algorithmic allocation problem from the strategic aspects, by a procedure that converts any algorithm to a dominant-strategy ascending mechanism . This technique works for any single value domain, in which each agent has the same value for each desired outcome, and this value is the only private information. In particular, for “single-value CAs”, where each player desires any one of several different bundles but has the same value for each of them, our technique converts any approximation algorithm to a dominant strategy mechanism that almost preserves the original approximation ratio. Our second result provides the first computationally efficient deterministic mechanism for the case of single-value multi-minded bidders (with private value and private desired bundles). The mechanism achieves an approximation to the social welfare which is close to the best possible in polynomial time (unless P=NP). This mechanism is an algorithmic implementation in undominated strategies , a notion that we define and justify, and is of independent interest.

In the presence of self-interested parties, mechanism designers typically aim to achieve their goals (or social-choice functions) in an equilibrium. In this paper, we study the cost of such equilibrium requirements in terms of communication, a problem that was recently raised by Fadel and Segal. While a certain amount of information x needs to be communicated just for computing the outcome of a certain social-choice function, an additional amount of communication may be required for computing the equilibrium-supporting prices (even if such prices are known to exist).

The Valiant Load-Balancing (VLB) design has been proposed for a backbone network architecture that can efficiently provide predictable performance under changing traffic matrices [1]. In this paper we show that the VLB network hasoptimalperformance when nodes can fail, in the sense that it can support the maximal homogeneous flow for any number of node failures. We generalize the VLB design to enable interconnection of multiple VLB networks, and study interconnection via bilateral peering agreements as well as transit agreements. We show that using VLB as a transit scheme yields the lowest possible network and interconnection capacities, while VLB peering can also achieve near-optimal use of capacity.

We study the equilibria of non-atomic congestion games in which there are two types of players: rational players, who seek to minimize their own delay, and malicious players, who seek to maximize the average delay experienced by the rational players. We study the existence of pure and mixed Nash equilibria for these games, and we seek to quantify the impact of the malicious players on the equilibrium. One counter intuitive phenomenon which we demonstrate is the "windfall of malice": paradoxically, when a myopically malicious player gains control of a fraction of the flow, a fraction of the players change from rational to malicious, the new equilibrium may be more favorable for the remaining rational players than the previous equilibrium.

Much recent research concerns systems, such as the Internet, whose components are owned and operated by different parties, each with his own "selfish" goal. The field of Algorithmic Mechanism Design handles the issue of private information held by the different parties in such computational settings. This paper deals with a complementary problem in such settings: handling the "hidden actions" that are performed by the different parties.Our model is a combinatorial variant of the classical principalagent problem from economic theory. In our setting a principal must motivate a team of strategic agents to exert costly effort on his behalf, but their actions are hidden from him. Our focus is on cases where complex combinations of the efforts of the agents influence the outcome. The principal motivates the agents by offering to them a set of contracts, which together put the agents in an equilibrium point of the induced game. We present formal models for this setting, suggest and embark on an analysis of some basic issues, but leave many questions open.

We consider the problem of a spatially distributed market with strategic agents. In this problem a single good is traded in a set of independent markets, where shipment between markets is possible but incurs a cost. The problem has previously been studied in the non-strategic case, inwhich it can be analyzed and solved as a min-cost-flow problem. We considerthe case where buyers and sellers are strategic. Our first result gives adouble characterization of the VCG prices, first as distances in acertain residue graph and second as the minimal (for buyers) and maximal (forsellers) equilibrium prices. This provides a computationally efficient, individually rational and incentive compatible welfare maximizing mechanism. This mechanism is, necessarily, not budget balanced and we provide alsoa budget-balanced mechanism (which is also computationally efficient,incentive compatible, and individually rational) that achieves highwelfare. Some of our results extend to the cases where buyers andsellers have arbitrary convex demand and supply functions and to the case where transportation is controlled by strategic agents as well.

With the recent technological feasibility of electronic commerce over the Internet, much attention has been given to the design of electronic markets for various types of electronically-tradable goods. Such markets, however, will normally need to function in some relationship with markets for other related goods, usually those downstream or upstream in the supply chain. Thus, for example, an electronic market for rubber tires for trucks will likely need to be strongly influenced by the rubber market as well as by the truck market. In this paper we design protocols for exchange of information between a sequence of markets along a single supply chain. These protocols allow each of these markets to function separately, while the information exchanged ensures efficient global behavior across the supply chain. Each market that forms a link in the supply chain operates as a double auction, where the bids on one side of the double auction come from bidders in the corresponding segment of the industry, and the bids on the other side are synthetically generated by the protocol to express the combined information from all other links in the chain. The double auctions in each of the markets can be of several types, and we study several variants of incentive compatible double auctions, comparing them in terms of their efficiency and of the market revenue.

Engineering automated negotiation across the supply chain is a central research challenge for the important problem of supply chain formation. The difficult problem of designing negotiation strategies is greatly simplified if the negotiation mechanism is incentive compatible, in which case the agents' dominant strategy is to simply report their private information truthfully. Unfortunately, with twosided negotiation it is impossible to simultaneously achieve perfect efficiency, budget balance, and individual rationality with incentive compatibility. This bears directly on the mechanism design problem for supply chain formation---the problem of designing auctions to coordinate the buying and selling of goods in multiple markets across a supply chain. We introduce incentive compatible, budget balanced, and individually rational auctions for supply chain formation inspired by previous work of Babaioff and Nisan, but extended to a broader class of supply chain topologies. The auctions explicitly discard profitable trades, thus giving up perfect efficiency to maintain budget balance and individual rationality. We use a novel payment rule analogous to Vickrey-Clarke-Groves payments, but adapted to our allocation rule. The first auction we present is incentive compatible when each agent desires only a single bundle of goods, the auction correctly knows all agents' bundles of interest, but the monetary valuations are private to the agents. We introduce extensions to maintain incentive compatibility when the auction does not know the agents' bundles of interest. We establish a good worst case bound on efficiency when the bundles of interest are known, which also applies in some cases when the bundles are not known. Our auctions produce higher efficiency for a broader class of su...

With the recent technological feasibility of electronic commerce over the Internet, much attention has been given to the design of electronic markets for various types of electronically-tradable goods. Such markets, however, will normally need to function in some relationship with markets for other related goods, usually those downstream or upstream in the supply chain. Thus, for example, an electronic market for rubber tires for trucks, will likely need to be strongly influenced by the rubber market as well as by the truck market.In this paper we design protocols for exchange of information between a sequence of markets along a single supply chain. These protocols allow each of these markets to function separately, while the information exchanged guarantees efficient global behavior across the supply chain. Each market form a link in the supply chain operates as a double auction, where the bids on one side of the double auction come from bidders in the corresponding segment of the industry, and the bids on the other side are synthetically generated by the protocol to express the combined information from all other links in the chain. The double auctions in each of the markets can be of several types, and we study several variants of incentive compatible double auctions, comparing them in terms of their efficiency and of the market revenue.