%%% -*-BibTeX-*- %%% ==================================================================== %%% BibTeX-file{ %%% author = "Nelson H. F. Beebe", %%% version = "1.04", %%% date = "28 October 2014", %%% time = "16:51:29 MDT", %%% filename = "teac.bib", %%% address = "University of Utah %%% Department of Mathematics, 110 LCB %%% 155 S 1400 E RM 233 %%% Salt Lake City, UT 84112-0090 %%% USA", %%% telephone = "+1 801 581 5254", %%% FAX = "+1 801 581 4148", %%% URL = "http://www.math.utah.edu/~beebe", %%% checksum = "26073 1791 10094 92773", %%% email = "beebe at math.utah.edu, beebe at acm.org, %%% beebe at computer.org (Internet)", %%% codetable = "ISO/ASCII", %%% keywords = "bibliography; BibTeX; ACM Transactions on %%% Economics and Computation (TEAC)", %%% license = "public domain", %%% supported = "no", %%% docstring = "This is a COMPLETE BibTeX bibliography for %%% the journal ACM Transactions on Economics and %%% Computation (no CODEN, ISSN 2167-8375 %%% (print), 2167-8383 (electronic)), for %%% 2013--date. %%% %%% Publication began with volume 1, number 1, %%% in January 2013. The journal appears %%% quarterly, in January, May, September, and %%% December. %%% %%% The journal has a World-Wide Web site at: %%% %%% http://teac.acm.org/ %%% %%% Tables-of-contents of all issues are %%% available at: %%% %%% http://dl.acm.org/citation.cfm?id=2542174 %%% %%% Qualified subscribers can retrieve the full %%% text of recent articles in PDF form. %%% %%% At version 1.04, the COMPLETE journal %%% coverage looked like this: %%% %%% 2013 ( 21) 2014 ( 17) %%% %%% Article: 38 %%% %%% Total entries: 38 %%% %%% Spelling has been verified with the UNIX %%% spell and GNU ispell programs using the %%% exception dictionary stored in the %%% companion file with extension .sok. %%% %%% BibTeX citation tags are uniformly chosen %%% as name:year:abbrev, where name is the %%% family name of the first author or editor, %%% year is a 4-digit number, and abbrev is a %%% 3-letter condensation of important title %%% words. Citation tags were automatically %%% generated by software developed for the %%% BibNet Project. %%% %%% In this bibliography, entries are sorted in %%% publication order, using ``bibsort -byvolume.'' %%% %%% The checksum field above contains a CRC-16 %%% checksum as the first value, followed by the %%% equivalent of the standard UNIX wc (word %%% count) utility output of lines, words, and %%% characters. This is produced by Robert %%% Solovay's checksum utility.", %%% } %%% ==================================================================== @Preamble{"\input bibnames.sty"} %%% ==================================================================== %%% Acknowledgement abbreviations: @String{ack-nhfb= "Nelson H. F. Beebe, University of Utah, Department of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@computer.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|"} %%% ==================================================================== %%% Journal abbreviations: @String{j-TEAC= "ACM Transactions on Economics and Computation"} %%% ==================================================================== %%% Publisher abbreviations: @String{pub-ACM= "ACM Press"} @String{pub-ACM:adr= "New York, NY 10036, USA"} %%% ==================================================================== %%% Bibliography entries: @Article{Conitzer:2013:ATE, author = "Vincent Conitzer and R. Preston Mcafee", title = "The {ACM Transactions on Economics and Computation}: an introduction", journal = j-TEAC, volume = "1", number = "1", pages = "1:1--1:??", month = jan, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2399187.2399188", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:51 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", acknowledgement = ack-nhfb, articleno = "1", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Gradwohl:2013:SRC, author = "Ronen Gradwohl and Noam Livne and Alon Rosen", title = "Sequential rationality in cryptographic protocols", journal = j-TEAC, volume = "1", number = "1", pages = "2:1--2:??", month = jan, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2399187.2399189", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:51 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/cryptography2010.bib; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "Much of the literature on rational cryptography focuses on analyzing the strategic properties of cryptographic protocols. However, due to the presence of computationally-bounded players and the asymptotic nature of cryptographic security, a definition of sequential rationality for this setting has thus far eluded researchers. We propose a new framework for overcoming these obstacles, and provide the first definitions of computational solution concepts that guarantee sequential rationality. We argue that natural computational variants of subgame perfection are too strong for cryptographic protocols. As an alternative, we introduce a weakening called threat-free Nash equilibrium that is more permissive but still eliminates the undesirable ``empty threats'' of nonsequential solution concepts. To demonstrate the applicability of our framework, we revisit the problem of implementing a mediator for correlated equilibria [Dodis et al 2000], and propose a variant of their protocol that is sequentially rational for a nontrivial class of correlated equilibria. Our treatment provides a better understanding of the conditions under which mediators in a correlated equilibrium can be replaced by a stable protocol.", acknowledgement = ack-nhfb, articleno = "2", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Jain:2013:GTA, author = "Shaili Jain and David C. Parkes", title = "A game-theoretic analysis of the {ESP} game", journal = j-TEAC, volume = "1", number = "1", pages = "3:1--3:??", month = jan, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2399187.2399190", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:51 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "``Games with a Purpose'' are interactive games that users play because they are fun, with the added benefit that the outcome of play is useful work. The ESP game, developed by von Ahn and Dabbish [2004], is an example of such a game devised to label images on the web. Since labeling images is a hard problem for computer vision algorithms and can be tedious and time-consuming for humans, the ESP game provides humans with incentive to do useful work by being enjoyable to play. We present a simple game-theoretic model of the ESP game and characterize the equilibrium behavior in our model. Our equilibrium analysis supports the fact that users appear to coordinate on low effort words. We provide an alternate model of user preferences, modeling a change that could be induced through a different scoring method, and show that equilibrium behavior in this model coordinates on high-effort words. We also give sufficient conditions for coordinating on high-effort words to be a Bayesian-Nash equilibrium. Our results suggest the possibility of formal incentive design in achieving desirable system-wide outcomes for the purpose of human computation, complementing existing considerations of robustness against cheating and human factors.", acknowledgement = ack-nhfb, articleno = "3", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Naroditskiy:2013:OPD, author = "Victor Naroditskiy and Maria Polukarov and Nicholas R. Jennings", title = "Optimal payments in dominant-strategy mechanisms for single-parameter domains", journal = j-TEAC, volume = "1", number = "1", pages = "4:1--4:??", month = jan, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2399187.2399191", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:51 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We study dominant-strategy mechanisms in allocation domains where agents have one-dimensional types and quasilinear utilities. Taking an allocation function as an input, we present an algorithmic technique for finding optimal payments in a class of mechanism design problems, including utilitarian and egalitarian allocation of homogeneous items with nondecreasing marginal costs. Our results link optimality of payment functions to a geometric condition involving triangulations of polytopes. When this condition is satisfied, we constructively show the existence of an optimal payment function that is piecewise linear in agent types.", acknowledgement = ack-nhfb, articleno = "4", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Feldman:2013:ISI, author = "Michal Feldman and Noam Nisan", title = "Introduction to the {Special Issue on Algorithmic Game Theory}", journal = j-TEAC, volume = "1", number = "2", pages = "5:1--5:??", month = may, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2465769.2465770", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:52 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", acknowledgement = ack-nhfb, articleno = "5", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Blume:2013:NFP, author = "Lawrence Blume and David Easley and Jon Kleinberg and Robert Kleinberg and {\'E}va Tardos", title = "Network Formation in the Presence of Contagious Risk", journal = j-TEAC, volume = "1", number = "2", pages = "6:1--6:??", month = may, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2465769.2465771", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:52 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "There are a number of domains where agents must collectively form a network in the face of the following trade-off: each agent receives benefits from the direct links it forms to others, but these links expose it to the risk of being hit by a cascading failure that might spread over multistep paths. Financial contagion, epidemic disease, the exposure of covert organizations to discovery, and electrical power networks are all settings in which such issues have been articulated. Here we formulate the problem in terms of strategic network formation, and provide asymptotically tight bounds on the welfare of both optimal and stable networks. We find that socially optimal networks are, in a precise sense, situated just beyond a phase transition in the behavior of the cascading failures, and that stable graphs lie slightly further beyond this phase transition, at a point where most of the available welfare has been lost. Our analysis enables us to explore such issues as the trade-offs between clustered and anonymous market structures, and it exposes a fundamental sense in which very small amounts of ``over-linking'' in networks with contagious risk can have strong consequences for the welfare of the participants.", acknowledgement = ack-nhfb, articleno = "6", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Karlin:2013:SEM, author = "Anna R. Karlin and C. Thach Nguyen and Yuval Peres", title = "Selling in Exclusive Markets: Some Observations on Prior-Free Mechanism Design", journal = j-TEAC, volume = "1", number = "2", pages = "7:1--7:??", month = may, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2465769.2465772", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:52 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We consider prior-free benchmarks in non-matroid settings. In particular, we show that a very desirable benchmark proposed by Hartline and Roughgarden is too strong, in the sense that no truthful mechanism can compete with it even in a very simple non-matroid setting where there are two exclusive markets and the seller can only sell to agents in one of them. On the other hand, we show that there is a mechanism that competes with a symmetrized version of this benchmark. We further investigate the more traditional best fixed price profit benchmark and show that there are mechanisms that compete with it in any downward-closed settings.", acknowledgement = ack-nhfb, articleno = "7", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Ha:2013:MDC, author = "Bach Q. Ha and Jason D. Hartline", title = "Mechanism Design via Consensus Estimates, Cross Checking, and Profit Extraction", journal = j-TEAC, volume = "1", number = "2", pages = "8:1--8:??", month = may, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2465769.2465773", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:52 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "There is only one technique for prior-free optimal mechanism design that generalizes beyond the structurally benevolent setting of digital goods. This technique uses random sampling to estimate the distribution of agent values and then employs the Bayesian optimal mechanism for this estimated distribution on the remaining players. Though quite general, even for digital goods, this random sampling auction has a complicated analysis and is known to be suboptimal. To overcome these issues we generalize the consensus and profit extraction techniques from Goldberg and Hartline [2003] to structurally rich environments that include, for example, single-minded combinatorial auctions.", acknowledgement = ack-nhfb, articleno = "8", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Goldberg:2013:CHM, author = "Paul W. Goldberg and Christos H. Papadimitriou and Rahul Savani", title = "The Complexity of the Homotopy Method, Equilibrium Selection, and {Lemke--Howson} Solutions", journal = j-TEAC, volume = "1", number = "2", pages = "9:1--9:??", month = may, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2465769.2465774", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:52 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We show that the widely used homotopy method for solving fixpoint problems, as well as the Harsanyi-Selten equilibrium selection process for games, are PSPACE-complete to implement. Extending our result for the Harsanyi-Selten process, we show that several other homotopy-based algorithms for finding equilibria of games are also PSPACE-complete to implement. A further application of our techniques yields the result that it is PSPACE-complete to compute any of the equilibria that could be found via the classical Lemke--Howson algorithm, a complexity-theoretic strengthening of the result in Savani and von Stengel [2006]. These results show that our techniques can be widely applied and suggest that the PSPACE-completeness of implementing homotopy methods is a general principle.", acknowledgement = ack-nhfb, articleno = "9", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Koutsoupias:2013:CRO, author = "Elias Koutsoupias and George Pierrakos", title = "On the Competitive Ratio of Online Sampling Auctions", journal = j-TEAC, volume = "1", number = "2", pages = "10:1--10:??", month = may, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2465769.2465775", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:52 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We study online profit-maximizing auctions for digital goods with adversarial bid selection and uniformly random arrivals; in this sense, our model lies at the intersection of prior-free mechanism design and secretary problems. Our goal is to design auctions that are constant competitive with F$^{(2)}$. We give a generic reduction that transforms any offline auction to an online one with only a loss of a factor of 2 in the competitive ratio. We also present some natural auctions, both randomized and deterministic, and study their competitive ratio. Our analysis reveals some interesting connections of one of these auctions with RSOP.", acknowledgement = ack-nhfb, articleno = "10", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Candogan:2013:NPG, author = "Ozan Candogan and Asuman Ozdaglar and Pablo A. Parrilo", title = "Near-Potential Games: Geometry and Dynamics", journal = j-TEAC, volume = "1", number = "2", pages = "11:1--11:??", month = may, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2465769.2465776", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:52 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "Potential games are a special class of games for which many adaptive user dynamics converge to a Nash equilibrium. In this article, we study properties of near-potential games, that is, games that are close in terms of payoffs to potential games, and show that such games admit similar limiting dynamics. We first focus on finite games in strategic form. We introduce a distance notion in the space of games and study the geometry of potential games and sets of games that are equivalent, with respect to various equivalence relations, to potential games. We discuss how, given an arbitrary game, one can find a nearby game in these sets. We then study dynamics in near-potential games by focusing on continuous-time perturbed best response dynamics. We characterize the limiting behavior of this dynamics in terms of the upper contour sets of the potential function of a close potential game and approximate equilibria of the game. Exploiting structural properties of approximate equilibrium sets, we strengthen our result and show that for games that are sufficiently close to a potential game, the sequence of mixed strategies generated by this dynamics converges to a small neighborhood of equilibria whose size is a function of the distance from the set of potential games. In the second part of the article, we study continuous games and show that our approach for characterizing the limiting sets in near-potential games extends to continuous games. In particular, we consider continuous-time best response dynamics and a variant of it (where players update their strategies only if there is at least $ \epsilon $ utility improvement opportunity) in near-potential games where the strategy sets are compact and convex subsets of a Euclidean space. We show that these update rules converge to a neighborhood of equilibria (or the maximizer of the potential function), provided that the potential function of the nearby potential game satisfies some structural properties. Our results generalize the known convergence results for potential games to near-potential games.", acknowledgement = ack-nhfb, articleno = "11", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Abernethy:2013:EMM, author = "Jacob Abernethy and Yiling Chen and Jennifer Wortman Vaughan", title = "Efficient Market Making via Convex Optimization, and a Connection to Online Learning", journal = j-TEAC, volume = "1", number = "2", pages = "12:1--12:??", month = may, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2465769.2465777", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:52 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We propose a general framework for the design of securities markets over combinatorial or infinite state or outcome spaces. The framework enables the design of computationally efficient markets tailored to an arbitrary, yet relatively small, space of securities with bounded payoff. We prove that any market satisfying a set of intuitive conditions must price securities via a convex cost function, which is constructed via conjugate duality. Rather than deal with an exponentially large or infinite outcome space directly, our framework only requires optimization over a convex hull. By reducing the problem of automated market making to convex optimization, where many efficient algorithms exist, we arrive at a range of new polynomial-time pricing mechanisms for various problems. We demonstrate the advantages of this framework with the design of some particular markets. We also show that by relaxing the convex hull we can gain computational tractability without compromising the market institution's bounded budget. Although our framework was designed with the goal of deriving efficient automated market makers for markets with very large outcome spaces, this framework also provides new insights into the relationship between market design and machine learning, and into the complete market setting. Using our framework, we illustrate the mathematical parallels between cost-function-based markets and online learning and establish a correspondence between cost-function-based markets and market scoring rules for complete markets.", acknowledgement = ack-nhfb, articleno = "12", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Haghpanah:2013:OAP, author = "Nima Haghpanah and Nicole Immorlica and Vahab Mirrokni and Kamesh Munagala", title = "Optimal Auctions with Positive Network Externalities", journal = j-TEAC, volume = "1", number = "2", pages = "13:1--13:??", month = may, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2465769.2465778", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:52 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We consider the problem of designing auctions in social networks for goods that exhibit single-parameter submodular network externalities in which a bidder's value for an outcome is a fixed private type times a known submodular function of the allocation of his friends. Externalities pose many issues that are hard to address with traditional techniques; our work shows how to resolve these issues in a specific setting of particular interest. We operate in a Bayesian environment and so assume private values are drawn according to known distributions. We prove that the optimal auction is NP-hard to approximate pointwise, and APX-hard on average. Thus we instead design auctions whose revenue approximates that of the optimal auction. Our main result considers step-function externalities in which a bidder's value for an outcome is either zero, or equal to his private type if at least one friend has the good. For these settings, we provide a e / e + 1-approximation. We also give a 0.25-approximation auction for general single-parameter submodular network externalities, and discuss optimizing over a class of simple pricing strategies.", acknowledgement = ack-nhfb, articleno = "13", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Othman:2013:PLS, author = "Abraham Othman and David M. Pennock and Daniel M. Reeves and Tuomas Sandholm", title = "A Practical Liquidity-Sensitive Automated Market Maker", journal = j-TEAC, volume = "1", number = "3", pages = "14:1--14:??", month = sep, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2509413.2509414", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:54 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "Automated market makers are algorithmic agents that enable participation and information elicitation in electronic markets. They have been widely and successfully applied in artificial-money settings, like some Internet prediction markets. Automated market makers from the literature suffer from two problems that contribute to their impracticality and impair their use beyond artificial-money settings: first, they are unable to adapt to liquidity, so that trades cause prices to move the same amount in both heavily and lightly traded markets, and second, in typical circumstances, they run at a deficit. In this article, we construct a market maker that is both sensitive to liquidity and can run at a profit. Our market maker has bounded loss for any initial level of liquidity and, as the initial level of liquidity approaches zero, worst-case loss approaches zero. For any level of initial liquidity we can establish a boundary in market state space such that, if the market terminates within that boundary, the market maker books a profit regardless of the realized outcome.", acknowledgement = ack-nhfb, articleno = "14", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Balcan:2013:PU, author = "Maria-Florina Balcan and Avrim Blum and Yishay Mansour", title = "The Price of Uncertainty", journal = j-TEAC, volume = "1", number = "3", pages = "15:1--15:??", month = sep, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2509413.2509415", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:54 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "In this work, we study the degree to which small fluctuations in costs in well-studied potential games can impact the result of natural best-response and improved-response dynamics. We call this the Price of Uncertainty and study it in a wide variety of potential games including fair cost-sharing games, set-cover games, routing games, and job-scheduling games. We show that in certain cases, even extremely small fluctuations can have the ability to cause these dynamics to spin out of control and move to states of much higher social cost, whereas in other cases these dynamics are much more stable even to large degrees of fluctuation. We also consider the resilience of these dynamics to a small number of Byzantine players about which no assumptions are made. We show again a contrast between different games. In certain cases (e.g., fair cost-sharing, set-cover, job-scheduling) even a single Byzantine player can cause best-response dynamics to transition from low-cost states to states of substantially higher cost, whereas in others (e.g., the class of $ \beta $-nice games, which includes routing, market-sharing and many others) these dynamics are much more resilient. Overall, our work can be viewed as analyzing the inherent resilience or safety of games to different kinds of imperfections in player behavior, player information, or in modeling assumptions made.", acknowledgement = ack-nhfb, articleno = "15", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Ben-Yehuda:2013:DAE, author = "Orna Agmon Ben-Yehuda and Muli Ben-Yehuda and Assaf Schuster and Dan Tsafrir", title = "Deconstructing {Amazon EC2} Spot Instance Pricing", journal = j-TEAC, volume = "1", number = "3", pages = "16:1--16:??", month = sep, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2509413.2509416", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:54 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "Cloud providers possessing large quantities of spare capacity must either incentivize clients to purchase it or suffer losses. Amazon is the first cloud provider to address this challenge, by allowing clients to bid on spare capacity and by granting resources to bidders while their bids exceed a periodically changing spot price. Amazon publicizes the spot price but does not disclose how it is determined. By analyzing the spot price histories of Amazon's EC2 cloud, we reverse engineer how prices are set and construct a model that generates prices consistent with existing price traces. Our findings suggest that usually prices are not market-driven, as sometimes previously assumed. Rather, they are likely to be generated most of the time at random from within a tight price range via a dynamic hidden reserve price mechanism. Our model could help clients make informed bids, cloud providers design profitable systems, and researchers design pricing algorithms.", acknowledgement = ack-nhfb, articleno = "16", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Sarne:2013:CSM, author = "David Sarne", title = "Competitive Shopbots-Mediated Markets", journal = j-TEAC, volume = "1", number = "3", pages = "17:1--17:??", month = sep, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2509413.2509417", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:54 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "This article considers markets mediated by autonomous self-interested comparison-shopping agents. As in today's markets, the agents do not charge buyers for their services but rather benefit from payments obtained from sellers upon the execution of a transaction. The agents aim at maximizing their expected benefit, taking into consideration the cost incurred by the search and competition dynamics that arise in the multi-agent setting. This article provides a comprehensive analysis of such models, based on search theory principles. The analysis results in a characterization of the buyers' and agents' search strategies in equilibrium. The main result of this article is that the use of self-interested comparison-shopping agents can result in a beneficial equilibrium, where both buyers and sellers benefit, in comparison to the case where buyers control the comparison-shopping agent, and the comparison-shopping agents necessarily do not lose. This, despite the fact that the service is offered for free to buyers and its cost is essentially covered by sellers. The analysis generalizes to any setting where buyers can use self-interested agents capable of effectively performing the search (e.g., evaluating opportunities) on their behalf.", acknowledgement = ack-nhfb, articleno = "17", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Procaccia:2013:AMD, author = "Ariel D. Procaccia and Moshe Tennenholtz", title = "Approximate Mechanism Design without Money", journal = j-TEAC, volume = "1", number = "4", pages = "18:1--18:??", month = dec, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2542174.2542175", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:56 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "The literature on algorithmic mechanism design is mostly concerned with game-theoretic versions of optimization problems to which standard economic money-based mechanisms cannot be applied efficiently. Recent years have seen the design of various truthful approximation mechanisms that rely on payments. In this article, we advocate the reconsideration of highly structured optimization problems in the context of mechanism design. We explicitly argue for the first time that, in such domains, approximation can be leveraged to obtain truthfulness without resorting to payments. This stands in contrast to previous work where payments are almost ubiquitous and (more often than not) approximation is a necessary evil that is required to circumvent computational complexity. We present a case study in approximate mechanism design without money. In our basic setting, agents are located on the real line and the mechanism must select the location of a public facility; the cost of an agent is its distance to the facility. We establish tight upper and lower bounds for the approximation ratio given by strategy-proof mechanisms without payments, with respect to both deterministic and randomized mechanisms, under two objective functions: the social cost and the maximum cost. We then extend our results in two natural directions: a domain where two facilities must be located and a domain where each agent controls multiple locations.", acknowledgement = ack-nhfb, articleno = "18", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Yildiz:2013:BOD, author = "Ercan Yildiz and Asuman Ozdaglar and Daron Acemoglu and Amin Saberi and Anna Scaglione", title = "Binary Opinion Dynamics with Stubborn Agents", journal = j-TEAC, volume = "1", number = "4", pages = "19:1--19:??", month = dec, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2538508", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:56 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We study binary opinion dynamics in a social network with stubborn agents who influence others but do not change their opinions. We focus on a generalization of the classical voter model by introducing nodes (stubborn agents) that have a fixed state. We show that the presence of stubborn agents with opposing opinions precludes convergence to consensus; instead, opinions converge in distribution with disagreement and fluctuations. In addition to the first moment of this distribution typically studied in the literature, we study the behavior of the second moment in terms of network properties and the opinions and locations of stubborn agents. We also study the problem of optimal placement of stubborn agents where the location of a fixed number of stubborn agents is chosen to have the maximum impact on the long-run expected opinions of agents.", acknowledgement = ack-nhfb, articleno = "19", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Mossel:2013:MCT, author = "Elchanan Mossel and Omer Tamuz", title = "Making Consensus Tractable", journal = j-TEAC, volume = "1", number = "4", pages = "20:1--20:??", month = dec, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2542174.2542176", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:56 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We study a model of consensus decision making in which a finite group of Bayesian agents has to choose between one of two courses of action. Each member of the group has a private and independent signal at his or her disposal, giving some indication as to which action is optimal. To come to a common decision, the participants perform repeated rounds of voting. In each round, each agent casts a vote in favor of one of the two courses of action, reflecting his or her current belief, and observes the votes of the rest. We provide an efficient algorithm for the calculation the agents have to perform and show that consensus is always reached and that the probability of reaching a wrong decision decays exponentially with the number of agents.", acknowledgement = ack-nhfb, articleno = "20", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Hoefer:2013:AAC, author = "Martin Hoefer and Alexander Skopalik", title = "Altruism in Atomic Congestion Games", journal = j-TEAC, volume = "1", number = "4", pages = "21:1--21:??", month = dec, year = "2013", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2542174.2542177", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 14 06:10:56 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "This article studies the effects of altruism, a phenomenon widely observed in practice, in the model of atomic congestion games. Altruistic behavior is modeled by a linear trade-off between selfish and social objectives. Our model can be embedded in the framework of congestion games with player-specific latency functions. Stable states are the pure Nash equilibria of these games, and we examine their existence and the convergence of sequential best-response dynamics. In general, pure Nash equilibria are often absent, and existence is NP-hard to decide. Perhaps surprisingly, if all delay functions are affine, the games remain potential games, even when agents are arbitrarily altruistic. The construction underlying this result can be extended to a class of general potential games and social cost functions, and we study a number of prominent examples. These results give important insights into the robustness of multi-agent systems with heterogeneous altruistic incentives. Furthermore, they yield a general technique to prove that stabilization is robust, even with partly altruistic agents, which is of independent interest. In addition to these results for uncoordinated dynamics, we consider a scenario with a central altruistic institution that can set incentives for the agents. We provide constructive and hardness results for finding the minimum number of altruists to stabilize an optimal congestion profile and more general mechanisms to incentivize agents to adopt favorable behavior. These results are closely related to Stackelberg routing and answer open questions raised recently in the literature.", acknowledgement = ack-nhfb, articleno = "21", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Polevoy:2014:SCS, author = "Gleb Polevoy and Rann Smorodinsky and Moshe Tennenholtz", title = "Signaling Competition and Social Welfare", journal = j-TEAC, volume = "2", number = "1", pages = "1:1--1:??", month = mar, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2560766", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 21 18:00:43 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We consider an environment where sellers compete over buyers. All sellers are a-priori identical and strategically signal buyers about the product they sell. In a setting motivated by online advertising in display ad exchanges, where firms use second price auctions, a firm's strategy is a decision about its signaling scheme for a stream of goods (e.g., user impressions), and a buyer's strategy is a selection among the firms. In this setting, a single seller will typically provide partial information, and consequently, a product may be allocated inefficiently. Intuitively, competition among sellers may induce sellers to provide more information in order to attract buyers and thus increase efficiency. Surprisingly, we show that such a competition among firms may yield significant loss in consumers' social welfare with respect to the monopolistic setting. Although we also show that in some cases, the competitive setting yields gain in social welfare, we provide a tight bound on that gain, which is shown to be small with respect to the preceding possible loss. Our model is tightly connected with the literature on bundling in auctions.", acknowledgement = ack-nhfb, articleno = "1", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Albers:2014:NEN, author = "Susanne Albers and Stefan Eilts and Eyal Even-Dar and Yishay Mansour and Liam Roditty", title = "On {Nash} Equilibria for a Network Creation Game", journal = j-TEAC, volume = "2", number = "1", pages = "2:1--2:??", month = mar, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2560767", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 21 18:00:43 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We study a basic network creation game proposed by Fabrikant et al. [2003]. In this game, each player (vertex) can create links (edges) to other players at a cost of \alpha per edge. The goal of every player is to minimize the sum consisting of (a) the cost of the links he has created and (b) the sum of the distances to all other players. Fabrikant et al. conjectured that there exists a constant $A$ such that, for any $\alpha > A$, all nontransient Nash equilibria graphs are trees. They showed that if a Nash equilibrium is a tree, the price of anarchy is constant. In this article, we disprove the tree conjecture. More precisely, we show that for any positive integer $n_0$, there exists a graph built by $n \geq n_0$ players which contains cycles and forms a nontransient Nash equilibrium, for any $\alpha$ with $1 < \alpha \leq \sqrt n / 2$. Our construction makes use of some interesting results on finite affine planes. On the other hand, we show that, for $\alpha \geq 12 n \lceil log n \rceil$, every Nash equilibrium forms a tree. Without relying on the tree conjecture, Fabrikant et al. proved an upper bound on the price of anarchy of $O(\sqrt{\alpha})$, where $\alpha \in [2, n^2]$. We improve this bound. Specifically, we derive a constant upper bound for $\alpha \in O(\sqrt{n})$ and for $\alpha \geq 12 n \lceil log n \rceil$. For the intermediate values, we derive an improved bound of $O(1 + (\min\{\alpha^2 / n, n^2 / \alpha \})^{1 / 3})$. Additionally, we develop characterizations of Nash equilibria and extend our results to a weighted network creation game as well as to scenarios with cost sharing.", acknowledgement = ack-nhfb, articleno = "2", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Smeulders:2014:GFM, author = "Bart Smeulders and Frits C. R. Spieksma and Laurens Cherchye and Bram {De Rock}", title = "Goodness-of-Fit Measures for Revealed Preference Tests: Complexity Results and Algorithms", journal = j-TEAC, volume = "2", number = "1", pages = "3:1--3:??", month = mar, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2560793", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 21 18:00:43 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We provide results on the computational complexity of goodness-of-fit measures (i.e., Afriat's efficiency index, Varian's efficiency vector-index, and the Houtman-Maks index) associated with several revealed preference axioms (i.e., WARP, SARP, GARP, and HARP). These results explain the computational difficulties that have been observed in literature when computing these indices. Our NP-hardness results are obtained by reductions from the independent set problem. We also show that this reduction can be used to prove that no approximation algorithm achieving a ratio of $O(n^{1 - \delta})$, $\delta;> 0$ exists for Varian's index, nor for Houtman-Maks' index (unless P = NP). Finally, we give an exact polynomial-time algorithm for finding Afriat's efficiency index.", acknowledgement = ack-nhfb, articleno = "3", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Zhang:2014:RPO, author = "Yu Zhang and Jaeok Park and Mihaela van der Schaar", title = "Rating Protocols in Online Communities", journal = j-TEAC, volume = "2", number = "1", pages = "4:1--4:??", month = mar, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2560794", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Mar 21 18:00:43 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "Sustaining cooperation among self-interested agents is critical for the proliferation of emerging online communities. Providing incentives for cooperation in online communities is particularly challenging because of their unique features: a large population of anonymous agents having asymmetric interests and dynamically joining and leaving the community, operation errors, and agents trying to whitewash when they have a low standing in the community. In this article, we take these features into consideration and propose a framework for designing and analyzing a class of incentive schemes based on rating protocols, which consist of a rating scheme and a recommended strategy. We first define the concept of sustainable rating protocols under which every agent has the incentive to follow the recommended strategy given the deployed rating scheme. We then formulate the problem of designing an optimal rating protocol, which selects the protocol that maximizes the overall social welfare among all sustainable rating protocols. Using the proposed framework, we study the structure of optimal rating protocols and explore the impact of one-sided rating, punishment lengths, and whitewashing on optimal rating protocols. Our results show that optimal rating protocols are capable of sustaining cooperation, with the amount of cooperation varying depending on the community characteristics.", acknowledgement = ack-nhfb, articleno = "4", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Emek:2014:SSR, author = "Yuval Emek and Michal Feldman and Iftah Gamzu and Renato PaesLeme and Moshe Tennenholtz", title = "Signaling Schemes for Revenue Maximization", journal = j-TEAC, volume = "2", number = "2", pages = "5:1--5:??", month = jun, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2594564", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Mon Jun 9 16:42:02 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "Signaling is an important topic in the study of asymmetric information in economic settings. In particular, the transparency of information available to a seller in an auction setting is a question of major interest. We introduce the study of signaling when conducting a second price auction of a probabilistic good whose actual instantiation is known to the auctioneer but not to the bidders. This framework can be used to model impressions selling in display advertising. We establish several results within this framework. First, we study the problem of computing a signaling scheme that maximizes the auctioneer's revenue in a Bayesian setting. We show that this problem is polynomially solvable for some interesting special cases, but computationally hard in general. Second, we establish a tight bound on the minimum number of signals required to implement an optimal signaling scheme. Finally, we show that at least half of the maximum social welfare can be preserved within such a scheme.", acknowledgement = ack-nhfb, articleno = "5", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Chen:2014:EPR, author = "Yiling Chen and Ian A. Kash and Michael Ruberry and Victor Shnayder", title = "Eliciting Predictions and Recommendations for Decision Making", journal = j-TEAC, volume = "2", number = "2", pages = "6:1--6:??", month = jun, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2556271", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Mon Jun 9 16:42:02 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "When making a decision, a decision maker selects one of several possible actions and hopes to achieve a desirable outcome. To make a better decision, the decision maker often asks experts for advice. In this article, we consider two methods of acquiring advice for decision making. We begin with a method where one or more experts predict the effect of each action and the decision maker then selects an action based on the predictions. We characterize strictly proper decision making, where experts have an incentive to accurately reveal their beliefs about the outcome of each action. However, strictly proper decision making requires the decision maker use a completely mixed strategy to choose an action. To address this limitation, we consider a second method where the decision maker asks a single expert to recommend an action. We show that it is possible to elicit the decision maker's most preferred action for a broad class of preferences of the decision maker, including when the decision maker is an expected value maximizer.", acknowledgement = ack-nhfb, articleno = "6", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Rozen:2014:EPE, author = "Rakefet Rozen and Rann Smorodinsky", title = "Ex-Post Equilibrium and {VCG} Mechanisms", journal = j-TEAC, volume = "2", number = "2", pages = "7:1--7:??", month = jun, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2594565", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Mon Jun 9 16:42:02 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "Consider an abstract social choice setting with incomplete information, where the number of alternatives is large. Albeit natural, implementing VCG mechanisms is infeasible due to the prohibitive communication constraints. However, if players restrict attention to a subset of the alternatives, feasibility may be recovered. This article characterizes the class of subsets that induce an ex-post equilibrium in the original game. It turns out that a crucial condition for such subsets to exist is the availability of a type-independent optimal social alternative for each player. We further analyze the welfare implications of these restrictions. This work follows that of Holzman et al. [2004] and Holzman and Monderer [2004] where similar analysis is done for combinatorial auctions.", acknowledgement = ack-nhfb, articleno = "7", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Chen:2014:PAS, author = "Xujin Chen and Benjamin Doerr and Carola Doerr and Xiaodong Hu and Weidong Ma and Rob van Stee", title = "The Price of Anarchy for Selfish Ring Routing is Two", journal = j-TEAC, volume = "2", number = "2", pages = "8:1--8:??", month = jun, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2548545", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Mon Jun 9 16:42:02 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We analyze the network congestion game with atomic players, asymmetric strategies, and the maximum latency among all players as social cost. This important social cost function is much less understood than the average latency. We show that the price of anarchy is at most two, when the network is a ring and the link latencies are linear. Our bound is tight. This is the first sharp bound for the maximum latency objective.", acknowledgement = ack-nhfb, articleno = "8", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Cary:2014:CPA, author = "Matthew Cary and Aparna Das and Benjamin Edelman and Ioannis Giotis and Kurtis Heimerl and Anna R. Karlin and Scott Duke Kominers and Claire Mathieu and Michael Schwarz", title = "Convergence of Position Auctions under Myopic Best-Response Dynamics", journal = j-TEAC, volume = "2", number = "3", pages = "9:1--9:??", month = jul, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2632226", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Oct 17 12:45:12 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We study the dynamics of multiround position auctions, considering both the case of exogenous click-through rates and the case in which click-through rates are determined by an endogenous consumer search process. In both contexts, we demonstrate that dynamic position auctions converge to their associated static, envy-free equilibria. Furthermore, convergence is efficient, and the entry of low-quality advertisers does not slow convergence. Because our approach predominantly relies on assumptions common in the sponsored search literature, our results suggest that dynamic position auctions converge more generally.", acknowledgement = ack-nhfb, articleno = "9", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Azar:2014:QCS, author = "Pablo Daniel Azar and Silvio Micali", title = "The Query Complexity of Scoring Rules", journal = j-TEAC, volume = "2", number = "3", pages = "10:1--10:??", month = jul, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2632228", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Oct 17 12:45:12 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "Proper scoring rules are crucial tools to elicit truthful information from experts. A scoring rule maps X, an expert-provided distribution over the set of all possible states of the world, and $ \omega $, a realized state of the world, to a real number representing the expert's reward for his provided information. To compute this reward, a scoring rule queries the distribution X at various states. The number of these queries is thus a natural measure of the complexity of the scoring rule. We prove that any bounded and strictly proper scoring rule that is deterministic must make a number of queries to its input distribution that is a quarter of the number of states of the world. When the state space is very large, this makes the computation of such scoring rules impractical. We also show a new stochastic scoring rule that is bounded, strictly proper, and which makes only two queries to its input distribution. Thus, using randomness allows us to have significant savings when computing scoring rules.", acknowledgement = ack-nhfb, articleno = "10", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Alaei:2014:RSA, author = "Saeed Alaei and Azarakhsh Malekian and Aravind Srinivasan", title = "On Random Sampling Auctions for Digital Goods", journal = j-TEAC, volume = "2", number = "3", pages = "11:1--11:??", month = jul, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2517148", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Oct 17 12:45:12 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "In the context of auctions for digital goods, an interesting random sampling auction has been proposed by Goldberg et al. [2001]. This auction has been analyzed by Feige et al. [2005], who have shown that it obtains in expectation at least 1/15 fraction of the optimal revenue, which is substantially better than the previously proven constant bounds but still far from the conjectured lower bound of 1/4. In this article, we prove that the aforementioned random sampling auction obtains at least 1/4 fraction of the optimal revenue for a large class of instances where the number of bids above (or equal to) the optimal sale price is at least 6. We also show that this auction obtains at least 1/4.68 fraction of the optimal revenue for the small class of remaining instances, thus leaving a negligible gap between the lower and upper bound. We employ a mix of probabilistic techniques and dynamic programming to compute these bounds.", acknowledgement = ack-nhfb, articleno = "11", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Dandekar:2014:PAR, author = "Pranav Dandekar and Nadia Fawaz and Stratis Ioannidis", title = "Privacy Auctions for Recommender Systems", journal = j-TEAC, volume = "2", number = "3", pages = "12:1--12:??", month = jul, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2629665", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Fri Oct 17 12:45:12 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We study a market for private data in which a data analyst publicly releases a statistic over a database of private information. Individuals that own the data incur a cost for their loss of privacy proportional to the differential privacy guarantee given by the analyst at the time of the release. The analyst incentivizes individuals by compensating them, giving rise to a privacy auction. Motivated by recommender systems, the statistic we consider is a linear predictor function with publicly known weights. The statistic can be viewed as a prediction of the unknown data of a new individual, based on the data of individuals in the database. We formalize the trade-off between privacy and accuracy in this setting, and show that a simple class of estimates achieves an order-optimal trade-off. It thus suffices to focus on auction mechanisms that output such estimates. We use this observation to design a truthful, individually rational, proportional-purchase mechanism under a fixed budget constraint. We show that our mechanism is 5-approximate in terms of accuracy compared to the optimal mechanism, and that no truthful mechanism can achieve a $ 2 - \epsilon $ approximation, for any $\epsilon > 0$.", acknowledgement = ack-nhfb, articleno = "12", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Balcan:2014:NOC, author = "Maria-Florina Balcan and Sara Krehbiel and Georgios Piliouras and Jinwoo Shin", title = "Near-Optimality in Covering Games by Exposing Global Information", journal = j-TEAC, volume = "2", number = "4", pages = "13:1--13:??", month = oct, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2597890", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Tue Oct 28 16:50:26 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "Mechanism design for distributed systems is fundamentally concerned with aligning individual incentives with social welfare to avoid socially inefficient outcomes that can arise from agents acting autonomously. One simple and natural approach is to centrally broadcast nonbinding advice intended to guide the system to a socially near-optimal state while still harnessing the incentives of individual agents. The analytical challenge is proving fast convergence to near optimal states, and in this article we give the first results that carefully constructed advice vectors yield stronger guarantees. We apply this approach to a broad family of potential games modeling vertex cover and set cover optimization problems in a distributed setting. This class of problems is interesting because finding exact solutions to their optimization problems is NP-hard yet highly inefficient equilibria exist, so a solution in which agents simply locally optimize is not satisfactory. We show that with an arbitrary advice vector, a set cover game quickly converges to an equilibrium with cost of the same order as the square of the social cost of the advice vector. More interestingly, we show how to efficiently construct an advice vector with a particular structure with cost O (log n ) times the optimal social cost, and we prove that the system quickly converges to an equilibrium with social cost of this same order.", acknowledgement = ack-nhfb, articleno = "13", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Bhawalkar:2014:WCG, author = "Kshipra Bhawalkar and Martin Gairing and Tim Roughgarden", title = "Weighted Congestion Games: The Price of Anarchy, Universal Worst-Case Examples, and Tightness", journal = j-TEAC, volume = "2", number = "4", pages = "14:1--14:??", month = oct, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2629666", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Tue Oct 28 16:50:26 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We characterize the Price of Anarchy (POA) in weighted congestion games, as a function of the allowable resource cost functions. Our results provide as thorough an understanding of this quantity as is already known for nonatomic and unweighted congestion games, and take the form of universal (cost function-independent) worst-case examples. One noteworthy by-product of our proofs is the fact that weighted congestion games are ``tight,'' which implies that the worst-case price of anarchy with respect to pure Nash equilibria, mixed Nash equilibria, correlated equilibria, and coarse correlated equilibria are always equal (under mild conditions on the allowable cost functions). Another is the fact that, like nonatomic but unlike atomic (unweighted) congestion games, weighted congestion games with trivial structure already realize the worst-case POA, at least for polynomial cost functions. We also prove a new result about unweighted congestion games: the worst-case price of anarchy in symmetric games is as large as in their more general asymmetric counterparts.", acknowledgement = ack-nhfb, articleno = "14", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Fotakis:2014:PDM, author = "Dimitris Fotakis and Christos Tzamos", title = "On the Power of Deterministic Mechanisms for Facility Location Games", journal = j-TEAC, volume = "2", number = "4", pages = "15:1--15:??", month = oct, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2665005", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Tue Oct 28 16:50:26 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We consider $K$-Facility Location games, where n strategic agents report their locations in a metric space and a mechanism maps them to $K$ facilities. The agents seek to minimize their connection cost, namely the distance of their true location to the nearest facility, and may misreport their location. We are interested in deterministic mechanisms that are strategyproof, that is, ensure that no agent can benefit from misreporting her location, do not resort to monetary transfers, and achieve a bounded approximation ratio to the total connection cost of the agents (or to the $ L_p $ norm of the connection costs, for some $ p \in [1, \infty) $ or for $ p = \infty) $. Our main result is an elegant characterization of deterministic strategyproof mechanisms with a bounded approximation ratio for $2$-Facility Location on the line. In particular, we show that for instances with $ n \geq 5 $ agents, any such mechanism either admits a unique dictator or always places the facilities at the leftmost and the rightmost location of the instance. As a corollary, we obtain that the best approximation ratio achievable by deterministic strategyproof mechanisms for the problem of locating $2$ facilities on the line to minimize the total connection cost is precisely $ n - 2$. Another rather surprising consequence is that the Two-Extremes mechanism of Procaccia and Tennenholtz [2009] is the only deterministic anonymous strategyproof mechanism with a bounded approximation ratio for $2$-Facility Location on the line. The proof of the characterization employs several new ideas and technical tools, which provide new insights into the behavior of deterministic strategyproof mechanisms for $K$-Facility Location games and may be of independent interest. Employing one of these tools, we show that for every $ K \geq 3$, there do not exist any deterministic anonymous strategyproof mechanisms with a bounded approximation ratio for $K$-Facility Location on the line, even for simple instances with $ K + 1$ agents. Moreover, building on the characterization for the line, we show that there do not exist any deterministic strategy proof mechanisms with a bounded approximation ratio for $2$-Facility Location and instances with $ n \geq 3$ agents located in a star.", acknowledgement = ack-nhfb, articleno = "15", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Michalak:2014:ICV, author = "Tomasz P. Michalak and Piotr L. Szczepa{\'n}ski and Talal Rahwan and Agata Chrobak and Simina Br{\^a}nzei and Michael Wooldridge and Nicholas R. Jennings", title = "Implementation and Computation of a Value for Generalized Characteristic Function Games", journal = j-TEAC, volume = "2", number = "4", pages = "16:1--16:??", month = oct, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2665007", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Tue Oct 28 16:50:26 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "Generalized characteristic function games are a variation of characteristic function games, in which the value of a coalition depends not only on the identities of its members, but also on the order in which the coalition is formed. This class of games is a useful abstraction for a number of realistic settings and economic situations, such as modeling relationships in social networks. To date, two main extensions of the Shapley value have been proposed for generalized characteristic function games: the Nowak--Radzik [1994] value and the S{\'a}nchez--Berganti{\~n}os [1997] value. In this context, the present article studies generalized characteristic function games from the point of view of implementation and computation. Specifically, the article makes two key contributions. First, building upon the mechanism by Dasgupta and Chiu [1998], we present a non-cooperative mechanism that implements both the Nowak--Radzik value and the S{\'a}nchez-Berganti{\~n}os value in Subgame-Perfect Nash Equilibria in expectations. Second, in order to facilitate an efficient computation supporting the implementation mechanism, we propose the Generalized Marginal-Contribution Nets representation for this type of game. This representation extends the results of Ieong and Shoham [2005] and Elkind et al. [2009] for characteristic function games and retains their attractive computational properties.", acknowledgement = ack-nhfb, articleno = "16", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", } @Article{Chen:2014:AIP, author = "Po-An Chen and Bart {De Keijzer} and David Kempe and Guido Sch{\"a}fer", title = "Altruism and Its Impact on the Price of Anarchy", journal = j-TEAC, volume = "2", number = "4", pages = "17:1--17:??", month = oct, year = "2014", CODEN = "????", DOI = "http://dx.doi.org/10.1145/2597893", ISSN = "2167-8375 (print), 2167-8383 (electronic)", ISSN-L = "1539-9087", bibdate = "Tue Oct 28 16:50:26 MDT 2014", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/teac.bib", abstract = "We study the inefficiency of equilibria for congestion games when players are (partially) altruistic. We model altruistic behavior by assuming that player $i$'s perceived cost is a convex combination of $\alpha_i$ times his direct cost and $\alpha_i$ times the social cost. Tuning the parameters $\alpha_i$ allows smooth interpolation between purely selfish and purely altruistic behavior. Within this framework, we study primarily altruistic extensions of (atomic and nonatomic) congestion games, but also obtain some results on fair cost-sharing games and valid utility games. We derive (tight) bounds on the price of anarchy of these games for several solution concepts. Thereto, we suitably adapt the smoothness notion introduced by Roughgarden and show that it captures the essential properties to determine the robust price of anarchy of these games. Our bounds show that for atomic congestion games and cost-sharing games, the robust price of anarchy gets worse with increasing altruism, while for valid utility games, it remains constant and is not affected by altruism. However, the increase in the price of anarchy is not a universal phenomenon: For general nonatomic congestion games with uniform altruism, the price of anarchy improves with increasing altruism. For atomic and nonatomic symmetric singleton congestion games, we derive bounds on the pure price of anarchy that improve as the average level of altruism increases. (For atomic games, we only derive such bounds when cost functions are linear.) Since the bounds are also strictly lower than the robust price of anarchy, these games exhibit natural examples in which pure Nash equilibria are more efficient than more permissive notions of equilibrium.", acknowledgement = ack-nhfb, articleno = "17", fjournal = "ACM Transactions on Economics and Computation", journal-URL = "http://dl.acm.org/citation.cfm?id=2542174", }