%%% -*-BibTeX-*-
%%% ====================================================================
%%%  BibTeX-file{
%%%     author          = "Nelson H. F. Beebe",
%%%     version         = "1.06",
%%%     date            = "21 April 2015",
%%%     time            = "11:27:04 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        = "02538 2414 13807 126647",
%%%     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.06, the COMPLETE journal
%%%                        coverage looked like this:
%%%
%%%                             2013 (  21)    2014 (  17)    2015 (  12)
%%%
%%%                             Article:         50
%%%
%%%                             Total entries:   50
%%%
%%%                        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",
}

@Article{Leyton-Brown:2015:ISI,
  author =       "Kevin Leyton-Brown and Panos Ipeirotis",
  title =        "Introduction to the Special Issue on {EC'12}",
  journal =      j-TEAC,
  volume =       "3",
  number =       "1",
  pages =        "1:1--1:??",
  month =        mar,
  year =         "2015",
  CODEN =        "????",
  DOI =          "http://dx.doi.org/10.1145/2742678",
  ISSN =         "2167-8375 (print), 2167-8383 (electronic)",
  ISSN-L =       "1539-9087",
  bibdate =      "Fri Mar 27 17:58:56 MDT 2015",
  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{Caragiannis:2015:APN,
  author =       "Ioannis Caragiannis and Angelo Fanelli and Nick Gravin
                 and Alexander Skopalik",
  title =        "Approximate Pure {Nash} Equilibria in Weighted
                 Congestion Games: Existence, Efficient Computation, and
                 Structure",
  journal =      j-TEAC,
  volume =       "3",
  number =       "1",
  pages =        "2:1--2:??",
  month =        mar,
  year =         "2015",
  CODEN =        "????",
  DOI =          "http://dx.doi.org/10.1145/2614687",
  ISSN =         "2167-8375 (print), 2167-8383 (electronic)",
  ISSN-L =       "1539-9087",
  bibdate =      "Fri Mar 27 17:58:56 MDT 2015",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/teac.bib",
  abstract =     "We consider structural and algorithmic questions
                 related to the Nash dynamics of weighted congestion
                 games. In weighted congestion games with linear latency
                 functions, the existence of pure Nash equilibria is
                 guaranteed by a potential function argument.
                 Unfortunately, this proof of existence is inefficient
                 and computing pure Nash equilibria in such games is a
                 PLS-hard problem even when all players have unit
                 weights. The situation gets worse when superlinear
                 (e.g., quadratic) latency functions come into play; in
                 this case, the Nash dynamics of the game may contain
                 cycles and pure Nash equilibria may not even exist.
                 Given these obstacles, we consider approximate pure
                 Nash equilibria as alternative solution concepts. A $
                 \rho $-approximate pure Nash equilibrium is a state of
                 a (weighted congestion) game from which no player has
                 any incentive to deviate in order to improve her cost
                 by a multiplicative factor higher than $ \rho $. Do
                 such equilibria exist for small values of $ \rho $ ?
                 And if so, can we compute them efficiently? We provide
                 positive answers to both questions for weighted
                 congestion games with polynomial latency functions by
                 exploiting an ``approximation'' of such games by a new
                 class of potential games that we call $ \Psi $-games.
                 This allows us to show that these games have $
                 d!$-approximate pure Nash equilibria, where $d$ is the
                 maximum degree of the latency functions. Our main
                 technical contribution is an efficient algorithm for
                 computing O(1)-approximate pure Nash equilibria when
                 $d$ is a constant. For games with linear latency
                 functions, the approximation guarantee is $ 3 + \sqrt 5
                 / 2 + O(\gamma)$ for arbitrarily small $ \gamma > 0$;
                 for latency functions with maximum degree $ d \geq 2$,
                 it is $ d 2 d + o (d)$. The running time is polynomial
                 in the number of bits in the representation of the game
                 and $ 1 / \gamma $. As a byproduct of our techniques,
                 we also show the following interesting structural
                 statement for weighted congestion games with polynomial
                 latency functions of maximum degree $ d \geq 2 $:
                 polynomially-long sequences of best-response moves from
                 any initial state to a $ d O (d 2)$-approximate pure
                 Nash equilibrium exist and can be efficiently
                 identified in such games as long as $d$ is a constant.
                 To the best of our knowledge, these are the first
                 positive algorithmic results for approximate pure Nash
                 equilibria in weighted congestion games. Our techniques
                 significantly extend our recent work on unweighted
                 congestion games through the use of $ \Psi $-games. The
                 concept of approximating nonpotential games by
                 potential ones is interesting in itself and might have
                 further applications.",
  acknowledgement = ack-nhfb,
  articleno =    "2",
  fjournal =     "ACM Transactions on Economics and Computation",
  journal-URL =  "http://dl.acm.org/citation.cfm?id=2542174",
}

@Article{Parkes:2015:BDR,
  author =       "David C. Parkes and Ariel D. Procaccia and Nisarg
                 Shah",
  title =        "Beyond Dominant Resource Fairness: Extensions,
                 Limitations, and Indivisibilities",
  journal =      j-TEAC,
  volume =       "3",
  number =       "1",
  pages =        "3:1--3:??",
  month =        mar,
  year =         "2015",
  CODEN =        "????",
  DOI =          "http://dx.doi.org/10.1145/2739040",
  ISSN =         "2167-8375 (print), 2167-8383 (electronic)",
  ISSN-L =       "1539-9087",
  bibdate =      "Fri Mar 27 17:58:56 MDT 2015",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/teac.bib",
  abstract =     "We study the problem of allocating multiple resources
                 to agents with heterogeneous demands. Technological
                 advances such as cloud computing and data centers
                 provide a new impetus for investigating this problem
                 under the assumption that agents demand the resources
                 in fixed proportions, known in economics as Leontief
                 preferences. In a recent paper, Ghodsi et al. [2011]
                 introduced the dominant resource fairness (DRF)
                 mechanism, which was shown to possess highly desirable
                 theoretical properties under Leontief preferences. We
                 extend their results in three directions. First, we
                 show that DRF generalizes to more expressive settings,
                 and leverage a new technical framework to formally
                 extend its guarantees. Second, we study the relation
                 between social welfare and properties such as
                 truthfulness; DRF performs poorly in terms of social
                 welfare, but we show that this is an unavoidable
                 shortcoming that is shared by every mechanism that
                 satisfies one of three basic properties. Third, and
                 most importantly, we study a realistic setting that
                 involves indivisibilities. We chart the boundaries of
                 the possible in this setting, contributing a new
                 relaxed notion of fairness and providing both
                 possibility and impossibility results.",
  acknowledgement = ack-nhfb,
  articleno =    "3",
  fjournal =     "ACM Transactions on Economics and Computation",
  journal-URL =  "http://dl.acm.org/citation.cfm?id=2542174",
}

@Article{Babaioff:2015:DPL,
  author =       "Moshe Babaioff and Shaddin Dughmi and Robert Kleinberg
                 and Aleksandrs Slivkins",
  title =        "Dynamic Pricing with Limited Supply",
  journal =      j-TEAC,
  volume =       "3",
  number =       "1",
  pages =        "4:1--4:??",
  month =        mar,
  year =         "2015",
  CODEN =        "????",
  DOI =          "http://dx.doi.org/10.1145/2559152",
  ISSN =         "2167-8375 (print), 2167-8383 (electronic)",
  ISSN-L =       "1539-9087",
  bibdate =      "Fri Mar 27 17:58:56 MDT 2015",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/teac.bib",
  abstract =     "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. We
                 focus on mechanisms that do not use any information
                 about the distribution; such mechanisms are called
                 detail-free (or prior-independent). They are desirable
                 because knowing the distribution is unrealistic in many
                 practical scenarios. We study how the revenue of such
                 mechanisms compares to the revenue of the optimal
                 offline mechanism that knows the distribution
                 (``offline benchmark''). We present a detail-free
                 online posted-price mechanism whose revenue is at most
                 $ O((k \log n)2 / 3) $ less than the offline benchmark,
                 for every distribution that is regular. In fact, this
                 guarantee holds without any assumptions if the
                 benchmark is relaxed to fixed-price mechanisms.
                 Further, we prove a matching lower bound. The
                 performance guarantee for the same mechanism can be
                 improved to $ O (\sqrt k \log n) $, with a
                 distribution-dependent constant, if the ratio $ k / n $
                 is sufficiently small. We show that, in the worst case
                 over all demand distributions, this is essentially the
                 best rate that can be obtained with a
                 distribution-specific constant. On a technical level,
                 we exploit the connection to multiarmed bandits (MAB).
                 While dynamic pricing with unlimited supply can easily
                 be seen as an MAB problem, the intuition behind MAB
                 approaches breaks when applied to the setting with
                 limited supply. Our high-level conceptual contribution
                 is that even the limited supply setting can be
                 fruitfully treated as a bandit problem.",
  acknowledgement = ack-nhfb,
  articleno =    "4",
  fjournal =     "ACM Transactions on Economics and Computation",
  journal-URL =  "http://dl.acm.org/citation.cfm?id=2542174",
}

@Article{Dutting:2015:PRT,
  author =       "Paul D{\"u}tting and Felix Fischer and Pichayut
                 Jirapinyo and John K. Lai and Benjamin Lubin and David
                 C. Parkes",
  title =        "Payment Rules through Discriminant-Based Classifiers",
  journal =      j-TEAC,
  volume =       "3",
  number =       "1",
  pages =        "5:1--5:??",
  month =        mar,
  year =         "2015",
  CODEN =        "????",
  DOI =          "http://dx.doi.org/10.1145/2559049",
  ISSN =         "2167-8375 (print), 2167-8383 (electronic)",
  ISSN-L =       "1539-9087",
  bibdate =      "Fri Mar 27 17:58:56 MDT 2015",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/teac.bib",
  abstract =     "In mechanism design it is typical to impose incentive
                 compatibility and then derive an optimal mechanism
                 subject to this constraint. By replacing the incentive
                 compatibility requirement with the goal of minimizing
                 expected ex post regret, we are able to adapt
                 statistical machine learning techniques to the design
                 of payment rules. This computational approach to
                 mechanism design is applicable to domains with
                 multi-dimensional types and situations where
                 computational efficiency is a concern. Specifically,
                 given an outcome rule and access to a type
                 distribution, we train a support vector machine with a
                 specific structure imposed on the discriminant
                 function, such that it implicitly learns a
                 corresponding payment rule with desirable incentive
                 properties. We extend the framework to adopt succinct
                 $k$-wise dependent valuations, leveraging a connection
                 with maximum a posteriori assignment on Markov networks
                 to enable training to scale up to settings with a large
                 number of items; we evaluate this construction in the
                 case where $ k = 2 $. We present applications to
                 multiparameter combinatorial auctions with approximate
                 winner determination, and the assignment problem with
                 an egalitarian outcome rule. Experimental results
                 demonstrate that the construction produces payment
                 rules with low ex post regret, and that penalizing
                 classification error is effective in preventing
                 failures of ex post individual rationality.",
  acknowledgement = ack-nhfb,
  articleno =    "5",
  fjournal =     "ACM Transactions on Economics and Computation",
  journal-URL =  "http://dl.acm.org/citation.cfm?id=2542174",
}

@Article{Roughgarden:2015:PAG,
  author =       "Tim Roughgarden",
  title =        "The Price of Anarchy in Games of Incomplete
                 Information",
  journal =      j-TEAC,
  volume =       "3",
  number =       "1",
  pages =        "6:1--6:??",
  month =        mar,
  year =         "2015",
  CODEN =        "????",
  DOI =          "http://dx.doi.org/10.1145/2737816",
  ISSN =         "2167-8375 (print), 2167-8383 (electronic)",
  ISSN-L =       "1539-9087",
  bibdate =      "Fri Mar 27 17:58:56 MDT 2015",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/teac.bib",
  abstract =     "We define smooth games of incomplete information. We
                 prove an ``extension theorem'' for such games: price of
                 anarchy bounds for pure Nash equilibria for all induced
                 full-information games extend automatically, without
                 quantitative degradation, to all mixed-strategy
                 Bayes--Nash equilibria with respect to a product prior
                 distribution over players' preferences. We also note
                 that, for Bayes--Nash equilibria in games with
                 correlated player preferences, there is no general
                 extension theorem for smooth games. We give several
                 applications of our definition and extension theorem.
                 First, we show that many games of incomplete
                 information for which the price of anarchy has been
                 studied are smooth in our sense. Our extension theorem
                 unifies much of the known work on the price of anarchy
                 in games of incomplete information. Second, we use our
                 extension theorem to prove new bounds on the price of
                 anarchy of Bayes--Nash equilibria in routing games with
                 incomplete information.",
  acknowledgement = ack-nhfb,
  articleno =    "6",
  fjournal =     "ACM Transactions on Economics and Computation",
  journal-URL =  "http://dl.acm.org/citation.cfm?id=2542174",
}

@Article{Goldstein:2015:IET,
  author =       "Daniel G. Goldstein and R. Preston McAfee and
                 Siddharth Suri",
  title =        "Improving the Effectiveness of Time-Based Display
                 Advertising",
  journal =      j-TEAC,
  volume =       "3",
  number =       "2",
  pages =        "7:1--7:??",
  month =        apr,
  year =         "2015",
  CODEN =        "????",
  DOI =          "http://dx.doi.org/10.1145/2716323",
  ISSN =         "2167-8375 (print), 2167-8383 (electronic)",
  ISSN-L =       "1539-9087",
  bibdate =      "Tue Apr 21 11:23:36 MDT 2015",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/teac.bib",
  abstract =     "Display advertisements are typically sold by the
                 impression, where one impression is simply one download
                 of an ad. Previous work has shown that the longer an ad
                 is in view, the more likely a user is to remember it
                 and that there are diminishing returns to increased
                 exposure time [Goldstein et al. 2011]. Since a pricing
                 scheme that is at least partially based on time is more
                 exact than one based solely on impressions, time-based
                 advertising may become an industry standard. We answer
                 an open question concerning time-based pricing schemes:
                 how should time slots for advertisements be divided? We
                 provide evidence that ads can be scheduled in a way
                 that leads to greater total recollection, which
                 advertisers value, and increased revenue, which
                 publishers value. We document two main findings. First,
                 we show that displaying two shorter ads results in more
                 total recollection than displaying one longer ad of
                 twice the duration. Second, we show that this effect
                 disappears as the duration of these ads increases. We
                 conclude with a theoretical prediction regarding the
                 circumstances under which the display advertising
                 industry would benefit if it moved to a partially or
                 fully time-based standard.",
  acknowledgement = ack-nhfb,
  articleno =    "7",
  fjournal =     "ACM Transactions on Economics and Computation",
  journal-URL =  "http://dl.acm.org/citation.cfm?id=2542174",
}

@Article{Ganzfried:2015:SOE,
  author =       "Sam Ganzfried and Tuomas Sandholm",
  title =        "Safe Opponent Exploitation",
  journal =      j-TEAC,
  volume =       "3",
  number =       "2",
  pages =        "8:1--8:??",
  month =        apr,
  year =         "2015",
  CODEN =        "????",
  DOI =          "http://dx.doi.org/10.1145/2716322",
  ISSN =         "2167-8375 (print), 2167-8383 (electronic)",
  ISSN-L =       "1539-9087",
  bibdate =      "Tue Apr 21 11:23:36 MDT 2015",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/teac.bib",
  abstract =     "We consider the problem of playing a repeated
                 two-player zero-sum game safety: that is, guaranteeing
                 at least the value of the game per period in
                 expectation regardless of the strategy used by the
                 opponent. Playing a stage-game equilibrium strategy at
                 each time step clearly guarantees safety, and prior
                 work has (incorrectly) stated that it is impossible to
                 simultaneously deviate from a stage-game equilibrium
                 (in hope of exploiting a suboptimal opponent) and to
                 guarantee safety. We show that such profitable
                 deviations are indeed possible specifically in games
                 where certain types of ``gift'' strategies exist, which
                 we define formally. We show that the set of strategies
                 constituting such gifts can be strictly larger than the
                 set of iteratively weakly-dominated strategies; this
                 disproves another recent assertion which states that
                 all noniteratively weakly dominated strategies are best
                 responses to each equilibrium strategy of the other
                 player. We present a full characterization of safe
                 strategies, and develop efficient algorithms for
                 exploiting suboptimal opponents while guaranteeing
                 safety. We also provide analogous results for
                 extensive-form games of perfect and imperfect
                 information, and present safe exploitation algorithms
                 and full characterizations of safe strategies for those
                 settings as well. We present experimental results in
                 Kuhn poker, a canonical test problem for game-theoretic
                 algorithms. Our experiments show that (1) aggressive
                 safe exploitation strategies significantly outperform
                 adjusting the exploitation within stage-game
                 equilibrium strategies only and (2) all the safe
                 exploitation strategies significantly outperform a
                 (nonsafe) best response strategy against strong dynamic
                 opponents.",
  acknowledgement = ack-nhfb,
  articleno =    "8",
  fjournal =     "ACM Transactions on Economics and Computation",
  journal-URL =  "http://dl.acm.org/citation.cfm?id=2542174",
}

@Article{Hoefer:2015:SSA,
  author =       "Martin Hoefer and Thomas Kesselheim",
  title =        "Secondary Spectrum Auctions for Symmetric and
                 Submodular Bidders",
  journal =      j-TEAC,
  volume =       "3",
  number =       "2",
  pages =        "9:1--9:??",
  month =        apr,
  year =         "2015",
  CODEN =        "????",
  DOI =          "http://dx.doi.org/10.1145/2739041",
  ISSN =         "2167-8375 (print), 2167-8383 (electronic)",
  ISSN-L =       "1539-9087",
  bibdate =      "Tue Apr 21 11:23:36 MDT 2015",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/teac.bib",
  abstract =     "We study truthful auctions for secondary spectrum
                 usage in wireless networks. In this scenario, $n$
                 communication requests need to be allocated to $k$
                 available channels that are subject to interference and
                 noise. We present the first truthful mechanisms for
                 secondary spectrum auctions with symmetric or
                 submodular valuations. Our approach to model
                 interference uses an edge-weighted conflict graph, and
                 our algorithms provide asymptotically almost optimal
                 approximation bounds for conflict graphs with a small
                 inductive independence number $ \rho \ll n $. This
                 approach covers a large variety of interference models
                 such as, for instance, the protocol model or the
                 recently popular physical model of interference. For
                 unweighted conflict graphs and symmetric valuations we
                 use LP-rounding to obtain $ O(\rho)$-approximate
                 mechanisms; for weighted conflict graphs we get a
                 factor of $ O(\rho \cdot (\log n + \log k))$. For
                 submodular users we combine the convex rounding
                 framework of Dughmi et al. [2011] with randomized
                 metarounding to obtain $ O(\rho)$-approximate
                 mechanisms for matroid-rank-sum valuations; for
                 weighted conflict graphs we can fully drop the
                 dependence on $k$ to get $ O(\rho \cdot \log n)$. We
                 conclude with promising initial results for
                 deterministically truthful mechanisms that allow
                 approximation factors based on $ \rho $.",
  acknowledgement = ack-nhfb,
  articleno =    "9",
  fjournal =     "ACM Transactions on Economics and Computation",
  journal-URL =  "http://dl.acm.org/citation.cfm?id=2542174",
}

@Article{Wilkens:2015:SCM,
  author =       "Christopher A. Wilkens and Balasubramanian Sivan",
  title =        "Single-Call Mechanisms",
  journal =      j-TEAC,
  volume =       "3",
  number =       "2",
  pages =        "10:1--10:??",
  month =        apr,
  year =         "2015",
  CODEN =        "????",
  DOI =          "http://dx.doi.org/10.1145/2741027",
  ISSN =         "2167-8375 (print), 2167-8383 (electronic)",
  ISSN-L =       "1539-9087",
  bibdate =      "Tue Apr 21 11:23:36 MDT 2015",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/teac.bib",
  abstract =     "Truthfulness is fragile and demanding. It is
                 oftentimes harder to guarantee truthfulness when
                 solving a problem than it is to solve the problem
                 itself. Even worse, truthfulness can be utterly
                 destroyed by small uncertainties in a mechanism's
                 outcome. One obstacle is that truthful payments depend
                 on outcomes other than the one realized, such as the
                 lengths of non-shortest-paths in a shortest-path
                 auction. Single-call mechanisms are a powerful tool
                 that circumvents this obstacle: they implicitly charge
                 truthful payments, guaranteeing truthfulness in
                 expectation using only the outcome realized by the
                 mechanism. The cost of such truthfulness is a trade-off
                 between the expected quality of the outcome and the
                 risk of large payments. We study two of the most
                 general domains for truthful mechanisms and largely
                 settle when and to what extent single-call mechanisms
                 are possible. The first single-call construction was
                 discovered by Babaioff et al. [2010] in
                 single-parameter domains. They give a transformation
                 that turns any monotone, single-parameter allocation
                 rule into a truthful-in-expectation single-call
                 mechanism. Our first result is a natural complement to
                 Babaioff et al. [2010]: we give a new transformation
                 that produces a single-call VCG mechanism from any
                 allocation rule for which VCG payments are truthful.
                 Second, in both the single-parameter and VCG settings,
                 we precisely characterize the possible transformations,
                 showing that a wide variety of transformations are
                 possible but that all take a very simple form. Finally,
                 we study the inherent trade-off between the expected
                 quality of the outcome and the risk of large payments.
                 We show that our construction and that of Babaioff et
                 al. [2010] simultaneously optimize a variety of metrics
                 in their respective domains. Our study is motivated by
                 settings where uncertainty in a mechanism renders other
                 known techniques untruthful, and we offer a variety of
                 examples where such uncertainty can arise. In
                 particular, we analyze pay-per-click advertising
                 auctions, where the truthfulness of the standard
                 VCG-based auction is easily broken when the
                 auctioneer's estimated click-through-rates are
                 imprecise.",
  acknowledgement = ack-nhfb,
  articleno =    "10",
  fjournal =     "ACM Transactions on Economics and Computation",
  journal-URL =  "http://dl.acm.org/citation.cfm?id=2542174",
}

@Article{Chakrabarti:2015:TSO,
  author =       "Deepayan Chakrabarti and Erik Vee",
  title =        "Traffic Shaping to Optimize Ad Delivery",
  journal =      j-TEAC,
  volume =       "3",
  number =       "2",
  pages =        "11:1--11:??",
  month =        apr,
  year =         "2015",
  CODEN =        "????",
  DOI =          "http://dx.doi.org/10.1145/2739010",
  ISSN =         "2167-8375 (print), 2167-8383 (electronic)",
  ISSN-L =       "1539-9087",
  bibdate =      "Tue Apr 21 11:23:36 MDT 2015",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/teac.bib",
  abstract =     "Web publishers must balance two objectives: how to
                 keep users engaged by directing them to relevant
                 content, and how to properly monetize this user
                 traffic. The standard approach is to solve each problem
                 in isolation, for example, by displaying content that
                 is tailored to the user's interests so as to maximize
                 clickthrough rates (CTR), and also by building a
                 standalone ad serving system that displays ads
                 depending on the user's characteristics, the article
                 being viewed by the user, and advertiser-specified
                 constraints. However, showing the user only those
                 articles with highest expected CTR precludes the
                 display of some ads; if the publisher had previously
                 guaranteed the delivery of a certain volume of
                 impressions to such ads, then underdelivery penalties
                 might have to be paid. We propose a joint optimization
                 of article selection and ad serving that minimizes
                 underdelivery by shaping some of the incoming traffic
                 to pages where underperforming ads can be displayed,
                 while incurring only minor drops in CTR. In addition to
                 formulating the problem, we design an online
                 optimization algorithm that can find the optimal
                 traffic shaping probabilities for each new user using
                 only a cache of one number per ad contract. Experiments
                 on a large real-world ad-serving Web portal demonstrate
                 significant advantages over the standalone approach: a
                 threefold reduction in underdelivery with only 10\%
                 drop in CTR, or a 2.6-fold reduction with a 4\% CTR
                 drop, and similar results over a wide range.",
  acknowledgement = ack-nhfb,
  articleno =    "11",
  fjournal =     "ACM Transactions on Economics and Computation",
  journal-URL =  "http://dl.acm.org/citation.cfm?id=2542174",
}

@Article{Ghosh:2015:MME,
  author =       "Arpita Ghosh and Mohammad Mahdian and R. Preston
                 McAfee and Sergei Vassilvitskii",
  title =        "To Match or Not to Match: Economics of Cookie Matching
                 in Online Advertising",
  journal =      j-TEAC,
  volume =       "3",
  number =       "2",
  pages =        "12:1--12:??",
  month =        apr,
  year =         "2015",
  CODEN =        "????",
  DOI =          "http://dx.doi.org/10.1145/2745801",
  ISSN =         "2167-8375 (print), 2167-8383 (electronic)",
  ISSN-L =       "1539-9087",
  bibdate =      "Tue Apr 21 11:23:36 MDT 2015",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/teac.bib",
  abstract =     "Modern online advertising increasingly relies on the
                 ability to follow the same user across the Internet
                 using technology called cookie matching to increase
                 efficiency in ad allocation. Web publishers today use
                 this technology to share information about the websites
                 a user has visited, making it possible to target
                 advertisements to users based on their prior history.
                 This begs the question: do publishers (who are
                 competitors for advertising money) always have the
                 incentive to share online information? Intuitive
                 arguments as well as anecdotal evidence suggest that
                 sometimes a premium publisher might suffer information
                 sharing through an effect called information leakage:
                 by sharing user information with the advertiser, the
                 advertiser will be able to target the same user
                 elsewhere on cheaper publishers, leading to a dilution
                 of the value of the supply on the premium publishers.
                 The goal of this article is to explore this aspect of
                 online information sharing. We show that, when
                 advertisers are homogeneous in the sense that their
                 relative valuations of users are consistent, publishers
                 always agree about the benefits of cookie matching in
                 equilibrium: either all publishers' revenues benefit,
                 or all suffer, from cookie matching. We also show using
                 a simple model that, when advertisers are not
                 homogeneous, the information leakage indeed can occur,
                 with cookie matching helping one publisher's revenues
                 while harming the other.",
  acknowledgement = ack-nhfb,
  articleno =    "12",
  fjournal =     "ACM Transactions on Economics and Computation",
  journal-URL =  "http://dl.acm.org/citation.cfm?id=2542174",
}