%%% -*-BibTeX-*-
%%% ====================================================================
%%%  BibTeX-file{
%%%     author          = "Nelson H. F. Beebe",
%%%     version         = "1.04",
%%%     date            = "28 October 2014",
%%%     time            = "16:51:29 MDT",
%%%     filename        = "teac.bib",
%%%     address         = "University of Utah
%%%                        Department of Mathematics, 110 LCB
%%%                        155 S 1400 E RM 233
%%%                        Salt Lake City, UT 84112-0090
%%%                        USA",
%%%     telephone       = "+1 801 581 5254",
%%%     FAX             = "+1 801 581 4148",
%%%     URL             = "http://www.math.utah.edu/~beebe",
%%%     checksum        = "26073 1791 10094 92773",
%%%     email           = "beebe at math.utah.edu, beebe at acm.org,
%%%                        beebe at computer.org (Internet)",
%%%     codetable       = "ISO/ASCII",
%%%     keywords        = "bibliography; BibTeX; ACM Transactions on
%%%                        Economics and Computation (TEAC)",
%%%     supported       = "no",
%%%     docstring       = "This is a COMPLETE BibTeX bibliography for
%%%                        the journal ACM Transactions on Economics and
%%%                        Computation (no CODEN, ISSN 2167-8375
%%%                        (print), 2167-8383 (electronic)), for
%%%                        2013--date.
%%%
%%%                        Publication began with volume 1, number 1,
%%%                        in January 2013.  The journal appears
%%%                        quarterly, in January, May, September, and
%%%                        December.
%%%
%%%                        The journal has a World-Wide Web site at:
%%%
%%%                            http://teac.acm.org/
%%%
%%%                        Tables-of-contents of all issues are
%%%                        available at:
%%%
%%%                            http://dl.acm.org/citation.cfm?id=2542174
%%%
%%%                        Qualified subscribers can retrieve the full
%%%                        text of recent articles in PDF form.
%%%
%%%                        At version 1.04, the COMPLETE journal
%%%                        coverage looked like this:
%%%
%%%                             2013 (  21)    2014 (  17)
%%%
%%%                             Article:         38
%%%
%%%                             Total entries:   38
%%%
%%%                        Spelling has been verified with the UNIX
%%%                        spell and GNU ispell programs using the
%%%                        exception dictionary stored in the
%%%                        companion file with extension .sok.
%%%
%%%                        BibTeX citation tags are uniformly chosen
%%%                        as name:year:abbrev, where name is the
%%%                        family name of the first author or editor,
%%%                        year is a 4-digit number, and abbrev is a
%%%                        3-letter condensation of important title
%%%                        words. Citation tags were automatically
%%%                        generated by software developed for the
%%%                        BibNet Project.
%%%
%%%                        In this bibliography, entries are sorted in
%%%                        publication order, using bibsort -byvolume.''
%%%
%%%                        The checksum field above contains a CRC-16
%%%                        checksum as the first value, followed by the
%%%                        equivalent of the standard UNIX wc (word
%%%                        count) utility output of lines, words, and
%%%                        characters.  This is produced by Robert
%%%                        Solovay's checksum utility.",
%%%  }
%%% ====================================================================

@Preamble{"\input bibnames.sty"}

%%% ====================================================================
%%% Acknowledgement abbreviations:

@String{ack-nhfb = "Nelson H. F. Beebe,
University of Utah,
Department of Mathematics, 110 LCB,
155 S 1400 E RM 233,
Salt Lake City, UT 84112-0090, USA,
Tel: +1 801 581 5254,
FAX: +1 801 581 4148,
e-mail: \path|beebe@math.utah.edu|,
\path|beebe@acm.org|,
\path|beebe@computer.org| (Internet),
URL: \path|http://www.math.utah.edu/~beebe/|"}

%%% ====================================================================
%%% Journal abbreviations:

@String{j-TEAC                  = "ACM Transactions on Economics and
Computation"}

%%% ====================================================================
%%% Publisher abbreviations:

@String{pub-ACM                 = "ACM Press"}
@String{pub-ACM:adr             = "New York, NY 10036, USA"}

%%% ====================================================================
%%% Bibliography entries:

@Article{Conitzer:2013:ATE,
author =       "Vincent Conitzer and R. Preston Mcafee",
title =        "The {ACM Transactions on Economics and Computation}:
an introduction",
journal =      j-TEAC,
volume =       "1",
number =       "1",
pages =        "1:1--1:??",
month =        jan,
year =         "2013",
CODEN =        "????",
DOI =          "http://dx.doi.org/10.1145/2399187.2399188",
ISSN =         "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L =       "1539-9087",
bibdate =      "Fri Mar 14 06:10:51 MDT 2014",
bibsource =    "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
acknowledgement = ack-nhfb,
articleno =    "1",
fjournal =     "ACM Transactions on Economics and Computation",
journal-URL =  "http://dl.acm.org/citation.cfm?id=2542174",
}

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
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
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
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
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
prices to move the same amount in both heavily and
lightly traded markets, and second, in typical
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",
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
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
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",
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
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
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
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
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
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
the system to a socially near-optimal state while still
harnessing the incentives of individual agents. The
analytical challenge is proving fast convergence to
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",
}