Search

We study envy freeness up to any good (EFX) in settings where valuations can be represented via a graph of arbitrary size where vertices correspond to agents and edges to items. An item (edge) has zero marginal value to all agents (vertices) not incident to the edge. Each vertex may have an arbitrary monotone valuation on the set of incident edges. We first consider allocations that correspond to orientations of the edges, where we show that EFX does not always exist, and furthermore that it is NP-complete to decide whether an EFX orientation exists. Our main result is that (EFX) allocations exist for this setting. This is one of the few cases where EFX allocations are known to exist for more than 3 agents. [ABSTRACT FROM AUTHOR]

The Bitcoin protocol induces miners, through monetary rewards, to expend energy in order to add blocks to the chain. We show that, when energy costs are substantial and taken into account, counterintuitive and unintended strategic behavior results: In a simple bounded-horizon setting with two identical miners there is a unique pure symmetric equilibrium in which both miners first "slow down" in order to decrease the crypto complexity and then take advantage of this decrease. If miners have different energy efficiencies and are restricted to choose the same hash rate for many epochs, there is a unique pure equilibrium in which miners either participate at low levels that depend in intricate ways on all the other miners' efficiencies, or choose to abstain from mining if their efficiency is too low. In the general setting in which miners can adapt their hash rates over time, we show that, unless the number of miners is very small, the only possible pure equilibria are rather chaotic, with miners quitting and starting again periodically -- or there is no pure equilibrium at all. We discuss the implications of these results for the stability of proof-of-work protocols. [ABSTRACT FROM AUTHOR]

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 social cost of a candidate is the sum of its distances to each voter. Some of our work assumes that these points can be modeled on the real line, but other results of ours are more general. A question closely related to candidate selection is that of minimizing the sum of distances for facility location. The difference is that in our setting there is a fixed set of candidates, whereas the large body of work on facility location considers every point in the metric space to be a possible candidate. This setting gives rise to three types of candidate selection mechanisms which differ in the granularity of their input space (single candidate, ranking and location mechanisms). We study the relationships between these three classes of mechanisms. While it may seem that Black's 1948 median algorithm is optimal for candidate selection on the line, this is not the case. We give matching upper and lower bounds for a variety of settings. In particular, when candidates and voters are on the line, our universally truthful spike mechanism gives a [tight] approximation of two. When assessing candidate selection mechanisms, we seek several desirable properties: (a) efficiency (minimizing the social cost) (b) truthfulness (dominant strategy incentive compatibility) and (c) simplicity (a smaller input space). We quantify the effect that truthfulness and simplicity impose on the efficiency. [ABSTRACT FROM AUTHOR]

We extend the notion of Combinatorial Walrasian Equilibrium, as defined by Feldman et al. [2013], to settings with budgets. When agents have budgets, the maximum social welfare as traditionally defined is not a suitable benchmark since it is overly optimistic. This motivated the liquid welfare of [Dobzinski and Paes Leme 2014] as an alternative. Observing that no combinatorial Walrasian equilibrium guarantees a non-zero fraction of the maximum liquid welfare in the absence of randomization, we instead work with randomized allocations and extend the notions of liquid welfare and Combinatorial Walrasian Equilibrium accordingly. Our generalization of the Combinatorial Walrasian Equilibrium prices lotteries over bundles of items rather than bundles, and we term it a lottery pricing equilibrium. Our results are two-fold. First, we exhibit an efficient algorithm which turns a randomized allocation with liquid expected welfare W into a lottery pricing equilibrium with liquid expected welfare 3-√5/2 .W (≈ 0:3819.W). Next, given access to a demand oracle and an -approximate oblivious rounding algorithm for the configuration linear program for the welfare maximization problem, we show how to efficiently compute a randomized allocation which is (a) supported on polynomially-many deterministic allocations and (b) obtains [nearly] an α fraction of the optimal liquid expected welfare. In the case of subadditive valuations, combining both results yields an efficient algorithm which computes a lottery pricing equilibrium obtaining a constant fraction of the optimal liquid expected welfare. [ABSTRACT FROM AUTHOR]

Walrasian prices, if they exist, have the property that one can assign every buyer some bundle in her demand set, such that the resulting assignment will maximize social welfare. Unfortunately, this assumes carefully breaking ties amongst different bundles in the buyer demand set. Presumably, the shopkeeper cleverly convinces the buyer to break ties in a manner consistent with maximizing social welfare. Lacking such a shopkeeper, if buyers arrive sequentially and simply choose some arbitrary bundle in their demand set, the social welfare may be arbitrarily bad. In the context of matching markets, we show how to compute dynamic prices, based upon the current inventory, that guarantee that social welfare is maximized. Such prices are set without knowing the identity of the next buyer to arrive. We also show that this is impossible in general (e.g., for coverage valuations), but consider other scenarios where this can be done. We further extend our results to Bayesian and bounded rationality models. [ABSTRACT FROM AUTHOR]

We study envy-free (EF) mechanisms for multi-unit auctions with budgeted agents that approximately maximize revenue. In an EF auction, prices are set so that every bidder receives a bundle that maximizes her utility amongst all bundles; We show that the problem of revenue-maximizing EF auctions is NP-hard, even for the case of identical items and additive valuations (up to the budget). The main result of our paper is a novel EF auction that runs in polynomial time and provides a approximation of 1/2 with respect to the revenue-maximizing EF auction. A slight variant of our mechanism will produce an allocation and pricing that is more restrictive (so called item pricing) and gives a 1/2 approximation to the optimal revenue within this more restrictive class. [ABSTRACT FROM AUTHOR]

We consider budget constrained combinatorial auctions where each bidder has a private value for each of the items in some subset of the items and an overall budget constraint. Such auctions capture adword auctions, where advertisers offer a bid for those adwords that (hopefully) target their intended audience, and advertisers also have budgets. It is known that even if all items are identical and all budgets are public it is not possible to be truthful and efficient. Our main result is a novel auction that runs in polynomial time, is incentive compatible, and ensures Pareto-optimality. The auction is incentive compatible with respect to the private valuations whereas the budgets and the sets of interest are assumed to be public knowledge. This extends the result of Dobzinski, Lavi and Nisan (FOCS 2008) for auctions of multiple identical items with bugets to single-valued combinatorial auctions and address one of the basic challenges on auctioning web ads (see Nisan et al, 2009, Google auctions for tv ads). [ABSTRACT FROM AUTHOR]

We study envy-free mechanisms for scheduling tasks on unrelated machines (agents) that approximately minimize the makespan. For indivisible tasks, we put forward an envy-free poly-time mechanism that approximates the minimal makespan to within a factor of O(logm), where m is the number of machines. We also show a lower bound of Ω(log m/log logm). This improves the recent result of Mu'alem [22] who give an upper bound of (m + 1)/2, and a lower bound of 2 - 1/m. For divisible tasks, we show that there always exists an envy-free poly-time mechanism with optimal makespan. Finally, we demonstrate how our mechanism for envy free makespan minimization can be interpreted as a market clearing problem. [ABSTRACT FROM AUTHOR]