%%% -*-BibTeX-*-
%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nelson H. F. Beebe",
%%% version = "1.02",
%%% date = "09 June 2014",
%%% time = "16:43:06 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 = "32362 1353 7484 69216",
%%% 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.02, the COMPLETE journal
%%% coverage looked like this:
%%%
%%% 2013 ( 21) 2014 ( 8)
%%%
%%% Article: 29
%%%
%%% Total entries: 29
%%%
%%% 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",
}