%%% -*-BibTeX-*-
%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nelson H. F. Beebe",
%%% version = "1.16",
%%% date = "03 February 2020",
%%% time = "08:55:05 MST",
%%% 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 = "21242 7152 41224 375570",
%%% 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.16, the COMPLETE journal
%%% coverage looked like this:
%%%
%%% 2013 ( 21) 2016 ( 27) 2019 ( 17)
%%% 2014 ( 17) 2017 ( 17) 2020 ( 4)
%%% 2015 ( 32) 2018 ( 21)
%%%
%%% Article: 156
%%%
%%% Total entries: 156
%%%
%%% 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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://doi.org/10.1145/2517148",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Oct 17 12:45:12 MDT 2014",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "In the context of auctions for digital goods, an
interesting random sampling auction has been proposed
by Goldberg et al. [2001]. This auction has been
analyzed by Feige et al. [2005], who have shown that it
obtains in expectation at least 1/15 fraction of the
optimal revenue, which is substantially better than the
previously proven constant bounds but still far from
the conjectured lower bound of 1/4. In this article, we
prove that the aforementioned random sampling auction
obtains at least 1/4 fraction of the optimal revenue
for a large class of instances where the number of bids
above (or equal to) the optimal sale price is at least
6. We also show that this auction obtains at least
1/4.68 fraction of the optimal revenue for the small
class of remaining instances, thus leaving a negligible
gap between the lower and upper bound. We employ a mix
of probabilistic techniques and dynamic programming to
compute these bounds.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Dandekar:2014:PAR,
author = "Pranav Dandekar and Nadia Fawaz and Stratis
Ioannidis",
title = "Privacy Auctions for Recommender Systems",
journal = j-TEAC,
volume = "2",
number = "3",
pages = "12:1--12:??",
month = jul,
year = "2014",
CODEN = "????",
DOI = "https://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 = "https://doi.org/10.1145/2597890",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Tue Oct 28 16:50:26 MDT 2014",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Mechanism design for distributed systems is
fundamentally concerned with aligning individual
incentives with social welfare to avoid socially
inefficient outcomes that can arise from agents acting
autonomously. One simple and natural approach is to
centrally broadcast nonbinding advice intended to guide
the system to a socially near-optimal state while still
harnessing the incentives of individual agents. The
analytical challenge is proving fast convergence to
near optimal states, and in this article we give the
first results that carefully constructed advice vectors
yield stronger guarantees. We apply this approach to a
broad family of potential games modeling vertex cover
and set cover optimization problems in a distributed
setting. This class of problems is interesting because
finding exact solutions to their optimization problems
is NP-hard yet highly inefficient equilibria exist, so
a solution in which agents simply locally optimize is
not satisfactory. We show that with an arbitrary advice
vector, a set cover game quickly converges to an
equilibrium with cost of the same order as the square
of the social cost of the advice vector. More
interestingly, we show how to efficiently construct an
advice vector with a particular structure with cost O
(log n ) times the optimal social cost, and we prove
that the system quickly converges to an equilibrium
with social cost of this same order.",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Bhawalkar:2014:WCG,
author = "Kshipra Bhawalkar and Martin Gairing and Tim
Roughgarden",
title = "Weighted Congestion Games: The Price of Anarchy,
Universal Worst-Case Examples, and Tightness",
journal = j-TEAC,
volume = "2",
number = "4",
pages = "14:1--14:??",
month = oct,
year = "2014",
CODEN = "????",
DOI = "https://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 = "https://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 = "https://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 = "https://doi.org/10.1145/2597893",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Tue Oct 28 16:50:26 MDT 2014",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study the inefficiency of equilibria for congestion
games when players are (partially) altruistic. We model
altruistic behavior by assuming that player $i$'s
perceived cost is a convex combination of $\alpha_i$
times his direct cost and $\alpha_i$ times the social
cost. Tuning the parameters $\alpha_i$ allows smooth
interpolation between purely selfish and purely
altruistic behavior. Within this framework, we study
primarily altruistic extensions of (atomic and
nonatomic) congestion games, but also obtain some
results on fair cost-sharing games and valid utility
games. We derive (tight) bounds on the price of anarchy
of these games for several solution concepts. Thereto,
we suitably adapt the smoothness notion introduced by
Roughgarden and show that it captures the essential
properties to determine the robust price of anarchy of
these games. Our bounds show that for atomic congestion
games and cost-sharing games, the robust price of
anarchy gets worse with increasing altruism, while for
valid utility games, it remains constant and is not
affected by altruism. However, the increase in the
price of anarchy is not a universal phenomenon: For
general nonatomic congestion games with uniform
altruism, the price of anarchy improves with increasing
altruism. For atomic and nonatomic symmetric singleton
congestion games, we derive bounds on the pure price of
anarchy that improve as the average level of altruism
increases. (For atomic games, we only derive such
bounds when cost functions are linear.) Since the
bounds are also strictly lower than the robust price of
anarchy, these games exhibit natural examples in which
pure Nash equilibria are more efficient than more
permissive notions of equilibrium.",
acknowledgement = ack-nhfb,
articleno = "17",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Leyton-Brown:2015:ISI,
author = "Kevin Leyton-Brown and Panos Ipeirotis",
title = "Introduction to the Special Issue on {EC'12}",
journal = j-TEAC,
volume = "3",
number = "1",
pages = "1:1--1:??",
month = mar,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2742678",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Mar 27 17:58:56 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Caragiannis:2015:APN,
author = "Ioannis Caragiannis and Angelo Fanelli and Nick Gravin
and Alexander Skopalik",
title = "Approximate Pure {Nash} Equilibria in Weighted
Congestion Games: Existence, Efficient Computation, and
Structure",
journal = j-TEAC,
volume = "3",
number = "1",
pages = "2:1--2:??",
month = mar,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2614687",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Mar 27 17:58:56 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We consider structural and algorithmic questions
related to the Nash dynamics of weighted congestion
games. In weighted congestion games with linear latency
functions, the existence of pure Nash equilibria is
guaranteed by a potential function argument.
Unfortunately, this proof of existence is inefficient
and computing pure Nash equilibria in such games is a
PLS-hard problem even when all players have unit
weights. The situation gets worse when superlinear
(e.g., quadratic) latency functions come into play; in
this case, the Nash dynamics of the game may contain
cycles and pure Nash equilibria may not even exist.
Given these obstacles, we consider approximate pure
Nash equilibria as alternative solution concepts. A $
\rho $-approximate pure Nash equilibrium is a state of
a (weighted congestion) game from which no player has
any incentive to deviate in order to improve her cost
by a multiplicative factor higher than $ \rho $. Do
such equilibria exist for small values of $ \rho $ ?
And if so, can we compute them efficiently? We provide
positive answers to both questions for weighted
congestion games with polynomial latency functions by
exploiting an ``approximation'' of such games by a new
class of potential games that we call $ \Psi $-games.
This allows us to show that these games have $
d!$-approximate pure Nash equilibria, where $d$ is the
maximum degree of the latency functions. Our main
technical contribution is an efficient algorithm for
computing O(1)-approximate pure Nash equilibria when
$d$ is a constant. For games with linear latency
functions, the approximation guarantee is $ 3 + \sqrt 5
/ 2 + O(\gamma)$ for arbitrarily small $ \gamma > 0$;
for latency functions with maximum degree $ d \geq 2$,
it is $ d 2 d + o (d)$. The running time is polynomial
in the number of bits in the representation of the game
and $ 1 / \gamma $. As a byproduct of our techniques,
we also show the following interesting structural
statement for weighted congestion games with polynomial
latency functions of maximum degree $ d \geq 2 $:
polynomially-long sequences of best-response moves from
any initial state to a $ d O (d 2)$-approximate pure
Nash equilibrium exist and can be efficiently
identified in such games as long as $d$ is a constant.
To the best of our knowledge, these are the first
positive algorithmic results for approximate pure Nash
equilibria in weighted congestion games. Our techniques
significantly extend our recent work on unweighted
congestion games through the use of $ \Psi $-games. The
concept of approximating nonpotential games by
potential ones is interesting in itself and might have
further applications.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Parkes:2015:BDR,
author = "David C. Parkes and Ariel D. Procaccia and Nisarg
Shah",
title = "Beyond Dominant Resource Fairness: Extensions,
Limitations, and Indivisibilities",
journal = j-TEAC,
volume = "3",
number = "1",
pages = "3:1--3:??",
month = mar,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2739040",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Mar 27 17:58:56 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study the problem of allocating multiple resources
to agents with heterogeneous demands. Technological
advances such as cloud computing and data centers
provide a new impetus for investigating this problem
under the assumption that agents demand the resources
in fixed proportions, known in economics as Leontief
preferences. In a recent paper, Ghodsi et al. [2011]
introduced the dominant resource fairness (DRF)
mechanism, which was shown to possess highly desirable
theoretical properties under Leontief preferences. We
extend their results in three directions. First, we
show that DRF generalizes to more expressive settings,
and leverage a new technical framework to formally
extend its guarantees. Second, we study the relation
between social welfare and properties such as
truthfulness; DRF performs poorly in terms of social
welfare, but we show that this is an unavoidable
shortcoming that is shared by every mechanism that
satisfies one of three basic properties. Third, and
most importantly, we study a realistic setting that
involves indivisibilities. We chart the boundaries of
the possible in this setting, contributing a new
relaxed notion of fairness and providing both
possibility and impossibility results.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Babaioff:2015:DPL,
author = "Moshe Babaioff and Shaddin Dughmi and Robert Kleinberg
and Aleksandrs Slivkins",
title = "Dynamic Pricing with Limited Supply",
journal = j-TEAC,
volume = "3",
number = "1",
pages = "4:1--4:??",
month = mar,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2559152",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Mar 27 17:58:56 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We consider the problem of designing
revenue-maximizing online posted-price mechanisms when
the seller has limited supply. A seller has k identical
items for sale and is facing n potential buyers
(``agents'') that are arriving sequentially. Each agent
is interested in buying one item. Each agent's value
for an item is an independent sample from some fixed
(but unknown) distribution with support [0,1]. The
seller offers a take-it-or-leave-it price to each
arriving agent (possibly different for different
agents), and aims to maximize his expected revenue. We
focus on mechanisms that do not use any information
about the distribution; such mechanisms are called
detail-free (or prior-independent). They are desirable
because knowing the distribution is unrealistic in many
practical scenarios. We study how the revenue of such
mechanisms compares to the revenue of the optimal
offline mechanism that knows the distribution
(``offline benchmark''). We present a detail-free
online posted-price mechanism whose revenue is at most
$ O((k \log n)2 / 3) $ less than the offline benchmark,
for every distribution that is regular. In fact, this
guarantee holds without any assumptions if the
benchmark is relaxed to fixed-price mechanisms.
Further, we prove a matching lower bound. The
performance guarantee for the same mechanism can be
improved to $ O (\sqrt k \log n) $, with a
distribution-dependent constant, if the ratio $ k / n $
is sufficiently small. We show that, in the worst case
over all demand distributions, this is essentially the
best rate that can be obtained with a
distribution-specific constant. On a technical level,
we exploit the connection to multiarmed bandits (MAB).
While dynamic pricing with unlimited supply can easily
be seen as an MAB problem, the intuition behind MAB
approaches breaks when applied to the setting with
limited supply. Our high-level conceptual contribution
is that even the limited supply setting can be
fruitfully treated as a bandit problem.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Dutting:2015:PRT,
author = "Paul D{\"u}tting and Felix Fischer and Pichayut
Jirapinyo and John K. Lai and Benjamin Lubin and David
C. Parkes",
title = "Payment Rules through Discriminant-Based Classifiers",
journal = j-TEAC,
volume = "3",
number = "1",
pages = "5:1--5:??",
month = mar,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2559049",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Mar 27 17:58:56 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "In mechanism design it is typical to impose incentive
compatibility and then derive an optimal mechanism
subject to this constraint. By replacing the incentive
compatibility requirement with the goal of minimizing
expected ex post regret, we are able to adapt
statistical machine learning techniques to the design
of payment rules. This computational approach to
mechanism design is applicable to domains with
multi-dimensional types and situations where
computational efficiency is a concern. Specifically,
given an outcome rule and access to a type
distribution, we train a support vector machine with a
specific structure imposed on the discriminant
function, such that it implicitly learns a
corresponding payment rule with desirable incentive
properties. We extend the framework to adopt succinct
$k$-wise dependent valuations, leveraging a connection
with maximum a posteriori assignment on Markov networks
to enable training to scale up to settings with a large
number of items; we evaluate this construction in the
case where $ k = 2 $. We present applications to
multiparameter combinatorial auctions with approximate
winner determination, and the assignment problem with
an egalitarian outcome rule. Experimental results
demonstrate that the construction produces payment
rules with low ex post regret, and that penalizing
classification error is effective in preventing
failures of ex post individual rationality.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Roughgarden:2015:PAG,
author = "Tim Roughgarden",
title = "The Price of Anarchy in Games of Incomplete
Information",
journal = j-TEAC,
volume = "3",
number = "1",
pages = "6:1--6:??",
month = mar,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2737816",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Mar 27 17:58:56 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We define smooth games of incomplete information. We
prove an ``extension theorem'' for such games: price of
anarchy bounds for pure Nash equilibria for all induced
full-information games extend automatically, without
quantitative degradation, to all mixed-strategy
Bayes--Nash equilibria with respect to a product prior
distribution over players' preferences. We also note
that, for Bayes--Nash equilibria in games with
correlated player preferences, there is no general
extension theorem for smooth games. We give several
applications of our definition and extension theorem.
First, we show that many games of incomplete
information for which the price of anarchy has been
studied are smooth in our sense. Our extension theorem
unifies much of the known work on the price of anarchy
in games of incomplete information. Second, we use our
extension theorem to prove new bounds on the price of
anarchy of Bayes--Nash equilibria in routing games with
incomplete information.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Goldstein:2015:IET,
author = "Daniel G. Goldstein and R. Preston McAfee and
Siddharth Suri",
title = "Improving the Effectiveness of Time-Based Display
Advertising",
journal = j-TEAC,
volume = "3",
number = "2",
pages = "7:1--7:??",
month = apr,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2716323",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Tue Apr 21 11:23:36 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Display advertisements are typically sold by the
impression, where one impression is simply one download
of an ad. Previous work has shown that the longer an ad
is in view, the more likely a user is to remember it
and that there are diminishing returns to increased
exposure time [Goldstein et al. 2011]. Since a pricing
scheme that is at least partially based on time is more
exact than one based solely on impressions, time-based
advertising may become an industry standard. We answer
an open question concerning time-based pricing schemes:
how should time slots for advertisements be divided? We
provide evidence that ads can be scheduled in a way
that leads to greater total recollection, which
advertisers value, and increased revenue, which
publishers value. We document two main findings. First,
we show that displaying two shorter ads results in more
total recollection than displaying one longer ad of
twice the duration. Second, we show that this effect
disappears as the duration of these ads increases. We
conclude with a theoretical prediction regarding the
circumstances under which the display advertising
industry would benefit if it moved to a partially or
fully time-based standard.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Ganzfried:2015:SOE,
author = "Sam Ganzfried and Tuomas Sandholm",
title = "Safe Opponent Exploitation",
journal = j-TEAC,
volume = "3",
number = "2",
pages = "8:1--8:??",
month = apr,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2716322",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Tue Apr 21 11:23:36 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We consider the problem of playing a repeated
two-player zero-sum game safety: that is, guaranteeing
at least the value of the game per period in
expectation regardless of the strategy used by the
opponent. Playing a stage-game equilibrium strategy at
each time step clearly guarantees safety, and prior
work has (incorrectly) stated that it is impossible to
simultaneously deviate from a stage-game equilibrium
(in hope of exploiting a suboptimal opponent) and to
guarantee safety. We show that such profitable
deviations are indeed possible specifically in games
where certain types of ``gift'' strategies exist, which
we define formally. We show that the set of strategies
constituting such gifts can be strictly larger than the
set of iteratively weakly-dominated strategies; this
disproves another recent assertion which states that
all noniteratively weakly dominated strategies are best
responses to each equilibrium strategy of the other
player. We present a full characterization of safe
strategies, and develop efficient algorithms for
exploiting suboptimal opponents while guaranteeing
safety. We also provide analogous results for
extensive-form games of perfect and imperfect
information, and present safe exploitation algorithms
and full characterizations of safe strategies for those
settings as well. We present experimental results in
Kuhn poker, a canonical test problem for game-theoretic
algorithms. Our experiments show that (1) aggressive
safe exploitation strategies significantly outperform
adjusting the exploitation within stage-game
equilibrium strategies only and (2) all the safe
exploitation strategies significantly outperform a
(nonsafe) best response strategy against strong dynamic
opponents.",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Hoefer:2015:SSA,
author = "Martin Hoefer and Thomas Kesselheim",
title = "Secondary Spectrum Auctions for Symmetric and
Submodular Bidders",
journal = j-TEAC,
volume = "3",
number = "2",
pages = "9:1--9:??",
month = apr,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2739041",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Tue Apr 21 11:23:36 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study truthful auctions for secondary spectrum
usage in wireless networks. In this scenario, $n$
communication requests need to be allocated to $k$
available channels that are subject to interference and
noise. We present the first truthful mechanisms for
secondary spectrum auctions with symmetric or
submodular valuations. Our approach to model
interference uses an edge-weighted conflict graph, and
our algorithms provide asymptotically almost optimal
approximation bounds for conflict graphs with a small
inductive independence number $ \rho \ll n $. This
approach covers a large variety of interference models
such as, for instance, the protocol model or the
recently popular physical model of interference. For
unweighted conflict graphs and symmetric valuations we
use LP-rounding to obtain $ O(\rho)$-approximate
mechanisms; for weighted conflict graphs we get a
factor of $ O(\rho \cdot (\log n + \log k))$. For
submodular users we combine the convex rounding
framework of Dughmi et al. [2011] with randomized
metarounding to obtain $ O(\rho)$-approximate
mechanisms for matroid-rank-sum valuations; for
weighted conflict graphs we can fully drop the
dependence on $k$ to get $ O(\rho \cdot \log n)$. We
conclude with promising initial results for
deterministically truthful mechanisms that allow
approximation factors based on $ \rho $.",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Wilkens:2015:SCM,
author = "Christopher A. Wilkens and Balasubramanian Sivan",
title = "Single-Call Mechanisms",
journal = j-TEAC,
volume = "3",
number = "2",
pages = "10:1--10:??",
month = apr,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2741027",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Tue Apr 21 11:23:36 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Truthfulness is fragile and demanding. It is
oftentimes harder to guarantee truthfulness when
solving a problem than it is to solve the problem
itself. Even worse, truthfulness can be utterly
destroyed by small uncertainties in a mechanism's
outcome. One obstacle is that truthful payments depend
on outcomes other than the one realized, such as the
lengths of non-shortest-paths in a shortest-path
auction. Single-call mechanisms are a powerful tool
that circumvents this obstacle: they implicitly charge
truthful payments, guaranteeing truthfulness in
expectation using only the outcome realized by the
mechanism. The cost of such truthfulness is a trade-off
between the expected quality of the outcome and the
risk of large payments. We study two of the most
general domains for truthful mechanisms and largely
settle when and to what extent single-call mechanisms
are possible. The first single-call construction was
discovered by Babaioff et al. [2010] in
single-parameter domains. They give a transformation
that turns any monotone, single-parameter allocation
rule into a truthful-in-expectation single-call
mechanism. Our first result is a natural complement to
Babaioff et al. [2010]: we give a new transformation
that produces a single-call VCG mechanism from any
allocation rule for which VCG payments are truthful.
Second, in both the single-parameter and VCG settings,
we precisely characterize the possible transformations,
showing that a wide variety of transformations are
possible but that all take a very simple form. Finally,
we study the inherent trade-off between the expected
quality of the outcome and the risk of large payments.
We show that our construction and that of Babaioff et
al. [2010] simultaneously optimize a variety of metrics
in their respective domains. Our study is motivated by
settings where uncertainty in a mechanism renders other
known techniques untruthful, and we offer a variety of
examples where such uncertainty can arise. In
particular, we analyze pay-per-click advertising
auctions, where the truthfulness of the standard
VCG-based auction is easily broken when the
auctioneer's estimated click-through-rates are
imprecise.",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Chakrabarti:2015:TSO,
author = "Deepayan Chakrabarti and Erik Vee",
title = "Traffic Shaping to Optimize Ad Delivery",
journal = j-TEAC,
volume = "3",
number = "2",
pages = "11:1--11:??",
month = apr,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2739010",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Tue Apr 21 11:23:36 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Web publishers must balance two objectives: how to
keep users engaged by directing them to relevant
content, and how to properly monetize this user
traffic. The standard approach is to solve each problem
in isolation, for example, by displaying content that
is tailored to the user's interests so as to maximize
clickthrough rates (CTR), and also by building a
standalone ad serving system that displays ads
depending on the user's characteristics, the article
being viewed by the user, and advertiser-specified
constraints. However, showing the user only those
articles with highest expected CTR precludes the
display of some ads; if the publisher had previously
guaranteed the delivery of a certain volume of
impressions to such ads, then underdelivery penalties
might have to be paid. We propose a joint optimization
of article selection and ad serving that minimizes
underdelivery by shaping some of the incoming traffic
to pages where underperforming ads can be displayed,
while incurring only minor drops in CTR. In addition to
formulating the problem, we design an online
optimization algorithm that can find the optimal
traffic shaping probabilities for each new user using
only a cache of one number per ad contract. Experiments
on a large real-world ad-serving Web portal demonstrate
significant advantages over the standalone approach: a
threefold reduction in underdelivery with only 10\%
drop in CTR, or a 2.6-fold reduction with a 4\% CTR
drop, and similar results over a wide range.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Ghosh:2015:MME,
author = "Arpita Ghosh and Mohammad Mahdian and R. Preston
McAfee and Sergei Vassilvitskii",
title = "To Match or Not to Match: Economics of Cookie Matching
in Online Advertising",
journal = j-TEAC,
volume = "3",
number = "2",
pages = "12:1--12:??",
month = apr,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2745801",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Tue Apr 21 11:23:36 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Modern online advertising increasingly relies on the
ability to follow the same user across the Internet
using technology called cookie matching to increase
efficiency in ad allocation. Web publishers today use
this technology to share information about the websites
a user has visited, making it possible to target
advertisements to users based on their prior history.
This begs the question: do publishers (who are
competitors for advertising money) always have the
incentive to share online information? Intuitive
arguments as well as anecdotal evidence suggest that
sometimes a premium publisher might suffer information
sharing through an effect called information leakage:
by sharing user information with the advertiser, the
advertiser will be able to target the same user
elsewhere on cheaper publishers, leading to a dilution
of the value of the supply on the premium publishers.
The goal of this article is to explore this aspect of
online information sharing. We show that, when
advertisers are homogeneous in the sense that their
relative valuations of users are consistent, publishers
always agree about the benefits of cookie matching in
equilibrium: either all publishers' revenues benefit,
or all suffer, from cookie matching. We also show using
a simple model that, when advertisers are not
homogeneous, the information leakage indeed can occur,
with cookie matching helping one publisher's revenues
while harming the other.",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Kash:2015:EAS,
author = "Ian A. Kash and Eric J. Friedman and Joseph Y.
Halpern",
title = "An Equilibrium Analysis of Scrip Systems",
journal = j-TEAC,
volume = "3",
number = "3",
pages = "13:1--13:??",
month = jun,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2659006",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:16 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "A game-theoretic model of scrip (artificial currency)
systems is analyzed. It is shown that relative entropy
can be used to characterize the distribution of agent
wealth when all agents use threshold strategies -that
is, they volunteer to do work if and only if they have
below a threshold amount of money. Monotonicity of
agents' best-reply functions is used to show that scrip
systems have pure strategy equilibria where all agents
use threshold strategies. An algorithm is given that
can compute such an equilibrium and the resulting
distribution of wealth.",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Immorlica:2015:ILR,
author = "Nicole Immorlica and Mohammad Mahdian",
title = "Incentives in Large Random Two-Sided Markets",
journal = j-TEAC,
volume = "3",
number = "3",
pages = "14:1--14:??",
month = jun,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2656202",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:16 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Many centralized two-sided markets form a matching
between participants by running a stable matching
algorithm. It is a well-known fact that no matching
mechanism based on a stable matching algorithm can
guarantee truthfulness as a dominant strategy for
participants. However, we show that in a probabilistic
setting where the preference lists on one side of the
market are composed of only a constant (independent of
the size of the market) number of entries, each drawn
from an arbitrary distribution, the number of
participants that have more than one stable partner is
vanishingly small. This proves (and generalizes) a
conjecture of Roth and Peranson [1999]. As a corollary
of this result, we show that, with high probability,
the truthful strategy is the best response for a random
player when the other players are truthful. We also
analyze equilibria of the deferred acceptance stable
matching game. We show that the game with complete
information has an equilibrium in which, in
expectation, a $ (1 - o(1)) $ fraction of the
strategies are truthful. In the more realistic setting
of a game of incomplete information, we will show that
the set of truthful strategies form a $ (1 +
o(1))$-approximate Bayesian--Nash equilibrium for
uniformly random preferences. Our results have
implications in many practical settings and are
inspired by the work of Roth and Peranson [1999] on the
National Residency Matching Program.",
acknowledgement = ack-nhfb,
articleno = "14",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Cavallo:2015:DAA,
author = "Ruggiero Cavallo and R. Preston Mcafee and Sergei
Vassilvitskii",
title = "Display Advertising Auctions with Arbitrage",
journal = j-TEAC,
volume = "3",
number = "3",
pages = "15:1--15:??",
month = jun,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2668033",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:16 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Online display advertising exchanges connect Web
publishers with advertisers seeking to place ads. In
many cases, the advertiser obtains value from an ad
impression (a viewing by a user) only if it is clicked,
and frequently advertisers prefer to pay contingent on
this occurring. But at the same time, many publishers
demand payment independent of clicks. Arbitragers with
good estimates of click-probabilities can resolve this
conflict by absorbing the risk and acting as an
intermediary, paying the publisher on allocation and
being paid only if a click occurs. This article
examines the incentives of advertisers and arbitragers
and contributes an efficient mechanism with truthful
bidding by the advertisers and truthful reporting of
click predictions by arbitragers as dominant strategies
while, given that a hazard rate condition is satisfied,
yielding increased revenue to the publisher. We provide
empirical evidence based on bid data from Yahoo's Right
Media Exchange suggesting that the mechanism would
increase revenue in practice.",
acknowledgement = ack-nhfb,
articleno = "15",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Bilo:2015:BDN,
author = "Davide Bil{\`o} and Luciano Gual{\`a} and Guido
Proietti",
title = "Bounded-Distance Network Creation Games",
journal = j-TEAC,
volume = "3",
number = "3",
pages = "16:1--16:??",
month = jun,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2770639",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:16 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "A network creation game simulates a decentralized and
noncooperative construction of a communication network.
Informally, there are $n$ players sitting on the
network nodes, which attempt to establish a reciprocal
communication by activating, thereby incurring a
certain cost, any of their incident links. The goal of
each player is to have all the other nodes as close as
possible in the resulting network, while buying as few
links as possible. According to this intuition, any
model of the game must then appropriately address a
balance between these two conflicting objectives.
Motivated by the fact that a player might have a strong
requirement about her centrality in the network, we
introduce a new setting in which a player who maintains
her (maximum or average) distance to the other nodes
within a given bound incurs a cost equal to the number
of activated edges; otherwise her cost is unbounded. We
study the problem of understanding the structure of
pure Nash equilibria of the resulting games, which we
call MaxBD and SumBD, respectively. For both games, we
show that when distance bounds associated with players
are nonuniform, then equilibria can be arbitrarily bad.
On the other hand, for MaxBD, we show that when nodes
have a uniform bound $ D \geq 3$ on the maximum
distance, then the price of anarchy (PoA) is lower and
upper bounded by 2 and $ O(n^{1 / \lfloor \log 3 D
\rfloor + 1})$, respectively (i.e., PoA is constant as
soon as $D$ is $ \Omega (n^\epsilon)$, for any $
\epsilon > 0$), while for the interesting case $ D =
2$, we are able to prove that the PoA is $ \Omega
(\sqrt {n})$ and $ O(\sqrt {n \log n})$. For the
uniform SumBD, we obtain similar (asymptotically)
results and moreover show that PoA becomes constant as
soon as the bound on the average distance is $ 2^{
\omega (\sqrt {\log n})}$.",
acknowledgement = ack-nhfb,
articleno = "16",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Chen:2015:ISI,
author = "Yiling Chen and Nicole Immorlica",
title = "Introduction to the Special Issue on {WINE'13}",
journal = j-TEAC,
volume = "3",
number = "4",
pages = "17:1--17:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2796538",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:18 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
acknowledgement = ack-nhfb,
articleno = "17",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Bateni:2015:RMN,
author = "Mohammadhossein Bateni and Nima Haghpanah and
Balasubramanian Sivan and Morteza Zadimoghaddam",
title = "Revenue Maximization with Nonexcludable Goods",
journal = j-TEAC,
volume = "3",
number = "4",
pages = "18:1--18:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2790131",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:18 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study the design of revenue-maximizing mechanisms
for selling nonexcludable public goods. In particular,
we study revenue-maximizing mechanisms in Bayesian
settings for facility location problems on graphs where
no agent can be excluded from using a facility that has
been constructed. We show that the pointwise
optimization problem involved in implementing the
revenue optimal mechanism, namely, optimizing over
arbitrary profiles of virtual values, is hard to
approximate within a factor of $ \Omega (n^{2 -
\epsilon }) $ (assuming P $ \neq $ NP) even in star
graphs. Furthermore, we show that optimizing the
expected revenue is APX-hard. However, in a relevant
special case, rooted version with identical
distributions, we construct polynomial time truthful
mechanisms that approximate the optimal expected
revenue within a constant factor. We also study the
effect of partially mitigating nonexcludability by
collecting tolls for using the facilities. We show that
such ``posted-price'' mechanisms obtain significantly
higher revenue and often approach the optimal revenue
obtainable with full excludability.",
acknowledgement = ack-nhfb,
articleno = "18",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Minooei:2015:NOR,
author = "Hadi Minooei and Chaitanya Swamy",
title = "Near-Optimal and Robust Mechanism Design for Covering
Problems with Correlated Players",
journal = j-TEAC,
volume = "3",
number = "4",
pages = "19:1--19:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2790133",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:18 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We consider the problem of designing
incentive-compatible, ex-post individually rational
(IR) mechanisms for covering problems in the Bayesian
setting, where players' types are drawn from an
underlying distribution and may be correlated, and the
goal is to minimize the expected total payment made by
the mechanism. We formulate a notion of incentive
compatibility (IC) that we call support-based IC that
is substantially more robust than Bayesian IC, and
develop black-box reductions from support-based-IC
mechanism design to algorithm design. For
single-dimensional settings, this black-box reduction
applies even when we only have an LP-relative
approximation algorithm for the algorithmic problem.
Thus, we obtain near-optimal mechanisms for various
covering settings, including single-dimensional
covering problems, multi-item procurement auctions, and
multidimensional facility location.",
acknowledgement = ack-nhfb,
articleno = "19",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Fotakis:2015:TFD,
author = "Dimitris Fotakis and Emmanouil Zampetakis",
title = "Truthfulness Flooded Domains and the Power of
Verification for Mechanism Design",
journal = j-TEAC,
volume = "3",
number = "4",
pages = "20:1--20:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2790086",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:18 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "In this work, we investigate the reasons that make
symmetric partial verification essentially useless in
virtually all domains. Departing from previous work, we
consider any possible (finite or infinite) domain and
general symmetric verification. We identify a natural
property, namely, that the correspondence graph of a
symmetric verification $M$ is strongly connected by
finite paths along which the preferences are consistent
with the preferences at the endpoints, and prove that
this property is sufficient for the equivalence of
truthfulness and $M$-truthfulness. In fact, defining
appropriate versions of this property, we obtain this
result for deterministic and randomized mechanisms with
and without money. Moreover, we show that a slightly
relaxed version of this property is also necessary for
the equivalence of truthfulness and $M$-truthfulness.
Our conditions provide a generic and convenient way of
checking whether truthful implementation can take
advantage of any symmetric verification scheme in any
(finite or infinite) domain. Since the simplest
symmetric verification is the local verification,
specific cases of our result are closely related, in
the case without money, to the research about the
equivalence of local truthfulness and global
truthfulness. To complete the picture, we consider
asymmetric verification and prove that a social choice
function is $M$-truthfully implementable by some
asymmetric verification $M$ if and only if $f$ does not
admit a cycle of profitable deviations.",
acknowledgement = ack-nhfb,
articleno = "20",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Kollias:2015:RPE,
author = "Konstantinos Kollias and Tim Roughgarden",
title = "Restoring Pure Equilibria to Weighted Congestion
Games",
journal = j-TEAC,
volume = "3",
number = "4",
pages = "21:1--21:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2781678",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:18 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Congestion games model several interesting
applications, including routing and network formation
games, and also possess attractive theoretical
properties, including the existence of and convergence
of natural dynamics to a pure Nash equilibrium.
Weighted variants of congestion games that rely on
sharing costs proportional to players' weights do not
generally have pure-strategy Nash equilibria. We
propose a new way of assigning costs to players with
weights in congestion games that recovers the important
properties of the unweighted model. This method is
derived from the Shapley value, and it always induces a
game with a (weighted) potential function. For the
special cases of weighted network cost-sharing and
weighted routing games with Shapley value-based cost
shares, we prove tight bounds on the worst-case
inefficiency of equilibria. For weighted network
cost-sharing games, we precisely calculate the price of
stability for any given player weight vector, while for
weighted routing games, we precisely calculate the
price of anarchy, as a parameter of the set of
allowable cost functions.",
acknowledgement = ack-nhfb,
articleno = "21",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Babichenko:2015:QCC,
author = "Yakov Babichenko and Siddharth Barman",
title = "Query Complexity of Correlated Equilibrium",
journal = j-TEAC,
volume = "3",
number = "4",
pages = "22:1--22:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2785668",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:18 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study lower bounds on the query complexity of
determining correlated equilibrium. In particular, we
consider a query model in which an $n$-player game is
specified via a black box that returns players'
utilities at pure action profiles. In this model, we
establish that in order to compute a correlated
equilibrium, any deterministic algorithm must query the
black box an exponential (in $n$) number of times.",
acknowledgement = ack-nhfb,
articleno = "22",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Aumann:2015:EFD,
author = "Yonatan Aumann and Yair Dombb",
title = "The Efficiency of Fair Division with Connected
Pieces",
journal = j-TEAC,
volume = "3",
number = "4",
pages = "23:1--23:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2781776",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:18 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "The cake-cutting setting, in which a single
heterogeneous good must be divided between multiple
parties with different tastes, is a classic model for
studying questions regarding fairness in resource
allocation. In this work, we turn our attention to
(economic) efficiency considerations in cake cutting,
examining the possible trade-offs between meeting the
fairness criteria, on the one hand, and maximizing
social welfare, on the other. We focus on divisions
that give each agent a single (contiguous) piece of the
cake and provide tight bounds (or, in some cases,
nearly tight) on the possible degradation in
utilitarian and egalitarian welfare resulting from
meeting the fairness requirements.",
acknowledgement = ack-nhfb,
articleno = "23",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Dimitrov:2015:SPM,
author = "Stanko Dimitrov and Rahul Sami and Marina A. Epelman",
title = "Subsidized Prediction Mechanisms for Risk-Averse
Agents",
journal = j-TEAC,
volume = "3",
number = "4",
pages = "24:1--24:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2716327",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:18 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "In this article, we study the design and
characterization of sequential prediction mechanisms in
the presence of agents with unknown risk aversion. We
formulate a collection of desirable properties for any
sequential forecasting mechanism. We present a
randomized mechanism that satisfies all of these
properties, including a guarantee that it is myopically
optimal for each agent to report honestly, regardless
of her degree of risk aversion. We observe, however,
that the mechanism has an undesirable side effect: each
agent's expected reward, normalized against the
inherent value of her private information, decreases
exponentially with the number of agents. We prove a
negative result showing that this is unavoidable: any
mechanism that is myopically strategyproof for agents
of all risk types, while also satisfying other natural
properties of sequential forecasting mechanisms, must
sometimes result in a player getting an exponentially
small expected normalized reward.",
acknowledgement = ack-nhfb,
articleno = "24",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Xiao:2015:SOD,
author = "Yuanzhang Xiao and Mihaela {Van Der Schaar}",
title = "Socially-Optimal Design of Service Exchange Platforms
with Imperfect Monitoring",
journal = j-TEAC,
volume = "3",
number = "4",
pages = "25:1--25:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2785627",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:18 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study the design of service exchange platforms in
which long-lived anonymous users exchange services with
each other. The users are randomly and repeatedly
matched into pairs of clients and servers, and each
server can choose to provide high-quality or
low-quality services to the client with whom it is
matched. Since the users are anonymous and incur high
costs (e.g., exert high effort) in providing
high-quality services, it is crucial that the platform
incentivizes users to provide high-quality services.
Rating mechanisms have been shown to work effectively
as incentive schemes in such platforms. A rating
mechanism labels each user by a rating, which
summarizes the user's past behaviors, recommends a
desirable behavior to each server (e.g., provide
higher-quality services for clients with higher
ratings), and updates each server's rating based on the
recommendation and its client's report on the service
quality. Based on this recommendation, a low-rating
user is less likely to obtain high-quality services,
thereby providing users with incentives to obtain high
ratings by providing high-quality services. However, if
monitoring or reporting is imperfect-clients do not
perfectly assess the quality or the reports are lost-a
user's rating may not be updated correctly. In the
presence of such errors, existing rating mechanisms
cannot achieve the social optimum. In this article, we
propose the first rating mechanism that does achieve
the social optimum, even in the presence of monitoring
or reporting errors. On one hand, the socially-optimal
rating mechanism needs to be complicated enough,
because the optimal recommended behavior depends not
only on the current rating distribution, but also
(necessarily) on the history of past rating
distributions in the platform. On the other hand, we
prove that the social optimum can be achieved by
``simple'' rating mechanisms that use binary rating
labels and a small set of (three) recommended
behaviors. We provide design guidelines of
socially-optimal rating mechanisms and a low-complexity
online algorithm for the rating mechanism to determine
the optimal recommended behavior.",
acknowledgement = ack-nhfb,
articleno = "25",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Nath:2015:AMD,
author = "Swaprava Nath and Arunava Sen",
title = "Affine Maximizers in Domains with Selfish Valuations",
journal = j-TEAC,
volume = "3",
number = "4",
pages = "26:1--26:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2786014",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Jul 31 19:26:18 MDT 2015",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We consider the domain of selfish and continuous
preferences over a ``rich'' allocation space and show
that onto, strategyproof and allocation non-bossy
social choice functions are affine maximizers. Roberts
[1979] proves this result for a finite set of
alternatives and an unrestricted valuation space. In
this article, we show that in a subdomain of the
unrestricted valuations with the additional assumption
of allocation non-bossiness, using the richness of the
allocations, the strategyproof social choice functions
can be shown to be affine maximizers. We provide an
example to show that allocation non-bossiness is indeed
critical for this result. This work shows that an
affine maximizer result needs a certain amount of
richness split across valuations and allocations.",
acknowledgement = ack-nhfb,
articleno = "26",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Dutting:2015:EMA,
author = "Paul D{\"u}tting and Monika Henzinger and Ingmar
Weber",
title = "An Expressive Mechanism for Auctions on the {Web}",
journal = j-TEAC,
volume = "4",
number = "1",
pages = "1:1--1:??",
month = dec,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2716312",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Feb 6 08:20:19 MST 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Auctions are widely used on the Web. Applications
range from sponsored search to platforms such as eBay.
In these and in many other applications the auctions in
use are single-/multi-item auctions with unit demand.
The main drawback of standard mechanisms for this type
of auctions, such as VCG and GSP, is the limited
expressiveness that they offer to the bidders. The
General Auction Mechanism (GAM) of Aggarwal et al.
[2009] takes a first step toward addressing the problem
of limited expressiveness by computing a bidder
optimal, envy-free outcome for linear utility functions
with identical slopes and a single discontinuity per
bidder-item pair. We show that in many practical
situations this does not suffice to adequately model
the preferences of the bidders, and we overcome this
problem by presenting the first mechanism for piecewise
linear utility functions with nonidentical slopes and
multiple discontinuities. Our mechanism runs in
polynomial time. Like GAM it is incentive compatible
for inputs that fulfill a certain nondegeneracy
assumption, but our requirement is more general than
the requirement of GAM. For discontinuous utility
functions that are nondegenerate as well as for
continuous utility functions the outcome of our
mechanism is a competitive equilibrium. We also show
how our mechanism can be used to compute approximately
bidder optimal, envy-free outcomes for a general class
of continuous utility functions via piecewise linear
approximation. Finally, we prove hardness results for
even more expressive settings.",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Colini-Baldeschi:2015:MKS,
author = "Riccardo Colini-Baldeschi and Stefano Leonardi and
Monika Henzinger and Martin Starnberger",
title = "On Multiple Keyword Sponsored Search Auctions with
Budgets",
journal = j-TEAC,
volume = "4",
number = "1",
pages = "2:1--2:??",
month = dec,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2818357",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Feb 6 08:20:19 MST 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study multiple keyword sponsored search auctions
with budgets. Each keyword has multiple ad slots with a
click-through rate. The bidders have additive
valuations, which are linear in the click-through
rates, and budgets, which are restricting their overall
payments. Additionally, the number of slots per keyword
assigned to a bidder is bounded. We show the following
results: (1) We give the first mechanism for multiple
keywords, where click-through rates differ among slots.
Our mechanism is incentive compatible in expectation,
individually rational in expectation, and Pareto
optimal. (2) We study the combinatorial setting, where
each bidder is only interested in a subset of the
keywords. We give an incentive compatible, individually
rational, Pareto-optimal, and deterministic mechanism
for identical click-through rates. (3) We give an
impossibility result for incentive compatible,
individually rational, Pareto-optimal, and
deterministic mechanisms for bidders with diminishing
marginal valuations.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Aumann:2015:ATT,
author = "Yonatan Aumann and Yair Dombb and Avinatan Hassidim",
title = "Auctioning Time: Truthful Auctions of Heterogeneous
Divisible Goods",
journal = j-TEAC,
volume = "4",
number = "1",
pages = "3:1--3:??",
month = dec,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2833086",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Feb 6 08:20:19 MST 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We consider the problem of auctioning time --- a
one-dimensional continuously-divisible heterogeneous
good --- among multiple agents. Applications include
auctioning time for using a shared device, auctioning
TV commercial slots, and more. Different agents may
have different valuations for the different possible
intervals; the goal is to maximize the aggregate
utility. Agents are self-interested and may
misrepresent their true valuation functions if this
benefits them. Thus, we seek auctions that are
truthful. Considering the case that each agent may
obtain a single interval, the challenge is twofold, as
we need to determine both where to slice the interval,
and who gets what slice. We consider two settings:
discrete and continuous. In the discrete setting, we
are given a sequence of m indivisible elements ( e$_1$,
..., e$_m$ ), and the auction must allocate each agent
a consecutive subsequence of the elements. In the
continuous setting, we are given a continuous,
infinitely divisible interval, and the auction must
allocate each agent a subinterval. The agents'
valuations are nonatomic measures on the interval. We
show that, for both settings, the associated
computational problem is NP-complete even under very
restrictive assumptions. Hence, we provide
approximation algorithms. For the discrete case, we
provide a truthful auctioning mechanism that
approximates the optimal welfare to within a log m
factor. The mechanism works for arbitrary monotone
valuations. For the continuous setting, we provide a
truthful auctioning mechanism that approximates the
optimal welfare to within an O (log n ) factor (where n
is the number of agents). Additionally, we provide a
truthful 2-approximation mechanism for the case that
all pieces must be of some fixed size.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Dutting:2015:AHI,
author = "Paul D{\"u}tting and Monika Henzinger and Martin
Starnberger",
title = "Auctions for Heterogeneous Items and Budget Limits",
journal = j-TEAC,
volume = "4",
number = "1",
pages = "4:1--4:??",
month = dec,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2818351",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Feb 6 08:20:19 MST 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study individual rational, Pareto-optimal, and
incentive compatible mechanisms for auctions with
heterogeneous items and budget limits. We consider
settings with multiunit demand and additive valuations.
For single-dimensional valuations we prove a positive
result for randomized mechanisms, and a negative result
for deterministic mechanisms. While the positive result
allows for private budgets, the negative result is for
public budgets. For multidimensional valuations and
public budgets we prove an impossibility result that
applies to deterministic and randomized mechanisms.
Taken together this shows the power of randomization in
certain settings with heterogeneous items, but it also
shows its limitations.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Alon:2015:HPT,
author = "Noga Alon and Robert Bredereck and Jiehua Chen and
Stefan Kratsch and Rolf Niedermeier and Gerhard J.
Woeginger",
title = "How to Put Through Your Agenda in Collective Binary
Decisions",
journal = j-TEAC,
volume = "4",
number = "1",
pages = "5:1--5:??",
month = dec,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2837467",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Feb 6 08:20:19 MST 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We consider the following decision-making scenario: a
society of voters has to find an agreement on a set of
proposals, and every single proposal is to be accepted
or rejected. Each voter supports a certain subset of
the proposals-the favorite ballot of this voter-and
opposes the remaining ones. He accepts a ballot if he
supports more than half of the proposals in this
ballot. The task is to decide whether there exists a
ballot approving a specified number of selected
proposals (agenda) such that all voters (or a strict
majority of them) accept this ballot. We show that, on
the negative side, both problems are NP-complete, and
on the positive side, they are fixed-parameter
tractable with respect to the total number of proposals
or with respect to the total number of voters. We look
into further natural parameters and study their
influence on the computational complexity of both
problems, thereby providing both tractability and
intractability results. Furthermore, we provide tight
combinatorial bounds on the worst-case size of an
accepted ballot in terms of the number of voters.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Fragiadakis:2015:SMM,
author = "Daniel Fragiadakis and Atsushi Iwasaki and Peter
Troyan and Suguru Ueda and Makoto Yokoo",
title = "Strategyproof Matching with Minimum Quotas",
journal = j-TEAC,
volume = "4",
number = "1",
pages = "6:1--6:??",
month = dec,
year = "2015",
CODEN = "????",
DOI = "https://doi.org/10.1145/2841226",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Feb 6 08:20:19 MST 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study matching markets in which institutions may
have minimum and maximum quotas. Minimum quotas are
important in many settings, such as hospital residency
matching, military cadet matching, and school choice,
but current mechanisms are unable to accommodate them,
leading to the use of ad hoc solutions. We introduce
two new classes of strategyproof mechanisms that allow
for minimum quotas as an explicit input and show that
our mechanisms improve welfare relative to existing
approaches. Because minimum quotas cause a theoretical
incompatibility between standard fairness and
nonwastefulness properties, we introduce new
second-best axioms and show that they are satisfied by
our mechanisms. Last, we use simulations to quantify
(1) the magnitude of the potential efficiency gains
from our mechanisms and (2) how far the resulting
assignments are from the first-best definitions of
fairness and nonwastefulness. Combining both the
theoretical and simulation results, we argue that our
mechanisms will improve the performance of matching
markets with minimum quota constraints in practice.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Babaioff:2016:MDS,
author = "Moshe Babaioff and Moran Feldman and Moshe
Tennenholtz",
title = "Mechanism Design with Strategic Mediators",
journal = j-TEAC,
volume = "4",
number = "2",
pages = "7:1--7:??",
month = feb,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2841227",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Feb 6 08:20:20 MST 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We consider the problem of designing mechanisms that
interact with strategic agents through strategic
intermediaries (or mediators), and investigate the cost
to society due to the mediators' strategic behavior.
Selfish agents with private information are each
associated with exactly one strategic mediator, and can
interact with the mechanism exclusively through that
mediator. Each mediator aims to optimize the combined
utility of his agents, while the mechanism aims to
optimize the combined utility of all agents. We focus
on the problem of facility location on a metric induced
by a publicly known tree. With nonstrategic mediators,
there is a dominant strategy mechanism that is optimal.
We show that when both agents and mediators act
strategically, there is no dominant strategy mechanism
that achieves any approximation. We, thus, slightly
relax the incentive constraints, and define the notion
of a two-sided incentive compatible mechanism. We show
that the 3-competitive deterministic mechanism
suggested by Procaccia and Tennenholtz [2013] and Dekel
et al. [2010] for lines extends naturally to trees, and
is still 3-competitive as well as two-sided incentive
compatible. This is essentially the best possible
(follows from Dekel et al. [2010] and Procaccia and
Tennenholtz [2013]). We then show that by allowing
randomization one can construct a 2-competitive
randomized mechanism that is two-sided incentive
compatible, and this is also essentially tight. This
result also reduces a gap left in the work of Procaccia
and Tennenholtz [2013] and Lu et al. [2009] for the
problem of designing strategy-proof mechanisms for
weighted agents with no mediators on a line. We also
investigate a generalization of the preceding setting
where there are multiple levels of mediators.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Roughgarden:2016:NCS,
author = "Tim Roughgarden and Okke Schrijvers",
title = "Network Cost-Sharing without Anonymity",
journal = j-TEAC,
volume = "4",
number = "2",
pages = "8:1--8:??",
month = feb,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2841228",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Feb 6 08:20:20 MST 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We consider network cost-sharing games with
nonanonymous cost functions, where the cost of each
edge is a submodular function of its users, and this
cost is shared using the Shapley value. Nonanonymous
cost functions model asymmetries between the players,
which can arise from different bandwidth requirements,
durations of use, services needed, and so on. These
games can possess multiple Nash equilibria of wildly
varying quality. The goal of this article is to
identify well-motivated equilibrium refinements that
admit good worst-case approximation bounds. Our primary
results are tight bounds on the cost of strong Nash
equilibria and potential function minimizers in network
cost-sharing games with nonanonymous cost functions,
parameterized by the set C of allowable submodular cost
functions. These two worst-case bounds coincide for
every set C, and equal the summability parameter
introduced in Roughgarden and Sundararajan [2009] to
characterize efficiency loss in a family of
cost-sharing mechanisms. Thus, a single parameter
simultaneously governs the worst-case inefficiency of
network cost-sharing games (in two incomparable senses)
and cost-sharing mechanisms. This parameter is always
at most the $k$th Harmonic number $H_k \approx \ln k$,
where $k$ is the number of players, and is constant for
many function classes of interest.",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Christodoulou:2016:TBP,
author = "George Christodoulou and Annam{\'a}ria Kov{\'a}cs and
Alkmini Sgouritsa and Bo Tang",
title = "Tight Bounds for the Price of Anarchy of Simultaneous
First-Price Auctions",
journal = j-TEAC,
volume = "4",
number = "2",
pages = "9:1--9:??",
month = feb,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2847520",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Feb 6 08:20:20 MST 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study the price of anarchy (PoA) of simultaneous
first-price auctions (FPAs) for buyers with submodular
and subadditive valuations. The current best upper
bounds for the Bayesian price of anarchy (BPoA) of
these auctions are e /( e --- 1) [Syrgkanis and Tardos
2013] and 2 [Feldman et al. 2013], respectively. We
provide matching lower bounds for both cases even for
the case of full information and for mixed Nash
equilibria via an explicit construction. We present an
alternative proof of the upper bound of e /( e --- 1)
for FPAs with fractionally subadditive valuations that
reveals the worst-case price distribution, which is
used as a building block for the matching lower bound
construction. We generalize our results to a general
class of item bidding auctions that we call
bid-dependent auctions (including FPAs and all-pay
auctions) where the winner is always the highest bidder
and each bidder's payment depends only on his own bid.
Finally, we apply our techniques to discriminatory
price multiunit auctions. We complement the results of
de Keijzer et al. [2013] for the case of subadditive
valuations by providing a matching lower bound of 2.
For the case of submodular valuations, we provide a
lower bound of 1.109. For the same class of valuations,
we were able to reproduce the upper bound of e /( e ---
1) using our nonsmooth approach.",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Christodoulou:2016:PSP,
author = "George Christodoulou and Martin Gairing",
title = "Price of Stability in Polynomial Congestion Games",
journal = j-TEAC,
volume = "4",
number = "2",
pages = "10:1--10:??",
month = feb,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2841229",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Feb 6 08:20:20 MST 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "The price of anarchy (PoA) in congestion games has
attracted a lot of research over the past decade. This
has resulted in a thorough understanding of this
concept. In contrast, the price of stability (PoS),
which is an equally interesting concept, is much less
understood. In this article, we consider congestion
games with polynomial cost functions with nonnegative
coefficients and maximum degree d. We give matching
bounds for the PoS in such games-that is, our technique
provides the exact value for any degree d. For linear
congestion games, tight bounds were previously known.
Those bounds hold even for the more restricted case of
dominant equilibria, which may not exist. We give a
separation result showing that this is not possible for
congestion games with quadratic cost functions-in other
words, the PoA for the subclass of games that admit a
dominant strategy equilibrium is strictly smaller than
the PoS for the general class.",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Hoefer:2016:TSD,
author = "Martin Hoefer and Thomas Kesselheim and Berthold
V{\"o}cking",
title = "Truthfulness and Stochastic Dominance with Monetary
Transfers",
journal = j-TEAC,
volume = "4",
number = "2",
pages = "11:1--11:??",
month = feb,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2847522",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Feb 6 08:20:20 MST 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We consider truthfulness concepts for auctions with
payments based on first- and second-order stochastic
dominance. We assume bidders consider wealth in
standard quasilinear form as valuation minus payments.
Additionally, they are sensitive to risk in the
distribution of wealth stemming from randomized
mechanisms. First- and second-order stochastic
dominance are well known to capture risk sensitivity,
and we apply these concepts to capture truth-telling
incentives for bidders. As our first main result, we
provide a complete characterization of all
social-choice functions over binary single-parameter
domains that can be implemented by a mechanism that is
truthful in first- and second-order stochastic
dominance. We show that these are exactly the
social-choice functions implementable by
truthful-in-expectation mechanisms, and we provide a
novel payment rule that guarantees stochastic
dominance. As our second main result we extend the
celebrated randomized metarounding approach for
truthful-in-expectation mechanisms in packing domains.
We design mechanisms that are truthful in first-order
stochastic dominance by spending only a logarithmic
factor in the approximation guarantee.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Mcafee:2016:I,
author = "Preston Mcafee and {\'E}va Tardos",
title = "Introduction",
journal = j-TEAC,
volume = "4",
number = "3",
pages = "12:1--12:??",
month = jun,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2916701",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Thu Jun 16 09:24:17 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Chen:2016:TMA,
author = "Yiling Chen and Stephen Chong and Ian A. Kash and Tal
Moran and Salil Vadhan",
title = "Truthful Mechanisms for Agents That Value Privacy",
journal = j-TEAC,
volume = "4",
number = "3",
pages = "13:1--13:??",
month = jun,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2892555",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Thu Jun 16 09:24:17 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Recent work has constructed economic mechanisms that
are both truthful and differentially private. In these
mechanisms, privacy is treated separately from
truthfulness; it is not incorporated in players'
utility functions (and doing so has been shown to lead
to nontruthfulness in some cases). In this work, we
propose a new, general way of modeling privacy in
players' utility functions. Specifically, we only
assume that if an outcome o has the property that any
report of player i would have led to o with
approximately the same probability, then o has a small
privacy cost to player i. We give three mechanisms that
are truthful with respect to our modeling of privacy:
for an election between two candidates, for a discrete
version of the facility location problem, and for a
general social choice problem with discrete utilities
(via a VCG-like mechanism). As the number n of players
increases, the social welfare achieved by our
mechanisms approaches optimal (as a fraction of n ).",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Devanur:2016:WPO,
author = "Nikhil R. Devanur and Zhiyi Huang and Nitish Korula
and Vahab S. Mirrokni and Qiqi Yan",
title = "Whole-Page Optimization and Submodular Welfare
Maximization with Online Bidders",
journal = j-TEAC,
volume = "4",
number = "3",
pages = "14:1--14:??",
month = jun,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2892563",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Thu Jun 16 09:24:17 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "In the context of online ad serving, display ads may
appear on different types of web pages, where each page
includes several ad slots and therefore multiple ads
can be shown on each page. The set of ads that can be
assigned to ad slots of the same page needs to satisfy
various prespecified constraints including exclusion
constraints, diversity constraints, and the like. Upon
arrival of a user, the ad serving system needs to
allocate a set of ads to the current webpage respecting
these per-page allocation constraints. Previous
slot-based settings ignore the important concept of a
page and may lead to highly suboptimal results in
general. In this article, motivated by these
applications in display advertising and inspired by the
submodular welfare maximization problem with online
bidders, we study a general class of page-based ad
allocation problems, present the first (tight)
constant-factor approximation algorithms for these
problems, and confirm the performance of our algorithms
experimentally on real-world datasets. A key technical
ingredient of our results is a novel primal-dual
analysis for handling free disposal, which updates dual
variables using a ``level function'' instead of a
single level and unifies with previous analyses of
related problems. This new analysis method allows us to
handle arbitrarily complicated allocation constraints
for each page. Our main result is an algorithm that
achieves a $1 - 1 / e - o(1)$-competitive
ratio. Moreover, our experiments on real-world datasets
show significant improvements of our page-based
algorithms compared to the slot-based
algorithms. Finally, we observe that our problem is
closely related to the submodular welfare maximization
(SWM) problem. In particular, we introduce a variant of
the SWM problem with online bidders and show how to
solve this problem using our algorithm for whole-page
optimization.",
acknowledgement = ack-nhfb,
articleno = "14",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Caragiannis:2016:WDN,
author = "Ioannis Caragiannis and Ariel D. Procaccia and Nisarg
Shah",
title = "When Do Noisy Votes Reveal the Truth?",
journal = j-TEAC,
volume = "4",
number = "3",
pages = "15:1--15:??",
month = jun,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2892565",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Thu Jun 16 09:24:17 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "A well-studied approach to the design of voting rules
views them as maximum likelihood estimators; given
votes that are seen as noisy estimates of a true
ranking of the alternatives, the rule must reconstruct
the most likely true ranking. We argue that this is too
stringent a requirement and instead ask: how many votes
does a voting rule need to reconstruct the true
ranking? We define the family of pairwise-majority
consistent rules and show that for all rules in this
family, the number of samples required from Mallows's
noise model is logarithmic in the number of
alternatives, and that no rule can do asymptotically
better (while some rules like plurality do much worse).
Taking a more normative point of view, we consider
voting rules that surely return the true ranking as the
number of samples tends to infinity (we call this
property accuracy in the limit ); this allows us to
move to a higher level of abstraction. We study
families of noise models that are parameterized by
distance functions and find voting rules that are
accurate in the limit for all noise models in such
general families. We characterize the distance
functions that induce noise models for which
pairwise-majority consistent rules are accurate in the
limit and provide a similar result for another novel
family of position-dominance consistent rules. These
characterizations capture three well-known distance
functions.",
acknowledgement = ack-nhfb,
articleno = "15",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Easley:2016:IGG,
author = "David Easley and Arpita Ghosh",
title = "Incentives, Gamification, and Game Theory: an Economic
Approach to Badge Design",
journal = j-TEAC,
volume = "4",
number = "3",
pages = "16:1--16:??",
month = jun,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2910575",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Thu Jun 16 09:24:17 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Gamification is growing increasingly prevalent as a
means to incentivize user engagement of social media
sites that rely on user contributions. Badges, or
equivalent rewards, such as top-contributor lists that
are used to recognize a user's contributions on a site,
clearly appear to be valued by users who actively
pursue and compete for them. However, different sites
use different badge designs, varying how, and for what,
badges are awarded. Some sites, such as StackOverflow,
award badges for meeting fixed levels of
contribution. Other sites, such as Amazon and Y!
Answers, reward users for being among some top set of
contributors on the site, corresponding to a
competitive standard of performance. Given that users
value badges, and that contributing to a site requires
effort, how badges are designed will affect the
incentives-therefore the participation and
effort-elicited from strategic users on a site. We take
a game-theoretic approach to badge design, analyzing
the incentives created by widely used badge designs in
a model in which winning a badge is valued, effort is
costly, and potential contributors to the site
endogenously decide whether or not to participate, and
how much total effort to put into their contributions
to the site. We analyze equilibrium existence, as well
as equilibrium participation and effort, in an absolute
standards mechanism $M_\alpha$ in which badges are
awarded for meeting some absolute level of (observed)
effort, and a relative standards mechanism $M_\rho$
corresponding to competitive standards, as in a
top-$\rho$ contributor badge. We find that equilibria
always exist in both mechanisms, even when the value
from winning a badge depends endogenously on the number
of other winners. However, $M_\alpha$ has
zero-participation equilibria for standards that are
too high, whereas all equilibria in $M_\rho$ elicit
nonzero participation for all possible $\rho$, provided
that $\rho$ is specified as a fixed number rather than
as a fraction of actual contributors (note that the two
are not equivalent in a setting with endogenous
participation). Finally, we ask whether or not a site
should explicitly announce the number of users winning
a badge. The answer to this question is determined by
the curvature of the value of winning the badge as a
function of the number of other winners.",
acknowledgement = ack-nhfb,
articleno = "16",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Roberts:2016:RTS,
author = "Ben Roberts and Dinan Gunawardena and Ian A. Kash and
Peter Key",
title = "Ranking and Tradeoffs in Sponsored Search Auctions",
journal = j-TEAC,
volume = "4",
number = "3",
pages = "17:1--17:??",
month = jun,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2910576",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Thu Jun 16 09:24:17 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "In a sponsored search auction, decisions about how to
rank ads impose tradeoffs between objectives, such as
revenue and welfare. In this article, we examine how
these tradeoffs should be made. We begin by arguing
that the most natural solution concept to evaluate
these tradeoffs is the lowest symmetric Nash
equilibrium (SNE). As part of this argument, we
generalise the well-known connection between the lowest
SNE and the VCG outcome. We then propose a new ranking
algorithm, loosely based on the revenue-optimal
auction, that uses a reserve price to order the ads
(not just to filter them) and give conditions under
which it raises more revenue than simply applying that
reserve price. Finally, we conduct extensive
simulations examining the tradeoffs enabled by
different ranking algorithms and show that our proposed
algorithm enables superior operating points by a
variety of metrics.",
acknowledgement = ack-nhfb,
articleno = "17",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Roughgarden:2016:ORM,
author = "Tim Roughgarden and Inbal Talgam-Cohen",
title = "Optimal and Robust Mechanism Design with
Interdependent Values",
journal = j-TEAC,
volume = "4",
number = "3",
pages = "18:1--18:??",
month = jun,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2910577",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Thu Jun 16 09:24:17 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study interdependent value settings and extend
several results from the well-studied independent
private values model to these settings. For
revenue-optimal mechanism design, we give conditions
under which Myerson's virtual value-based mechanism
remains optimal with interdependent values. One of
these conditions is robustness of the truthfulness and
individual rationality guarantees, in the sense that
they are required to hold ex-post. We then consider an
even more robust class of mechanisms called ``prior
independent'' (``detail free''), and show that, by
simply using one of the bidders to set a reserve price,
it is possible to extract near-optimal revenue in an
interdependent values setting. This shows that a
considerable level of robustness is achievable for
interdependent values in single-parameter
environments.",
acknowledgement = ack-nhfb,
articleno = "18",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Conitzer:2016:ISI,
author = "Vincent Conitzer and David Easley",
title = "Introduction to the Special Issue on {EC'14}",
journal = j-TEAC,
volume = "4",
number = "4",
pages = "19:1--19:??",
month = aug,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2953046",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Aug 29 06:37:22 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
acknowledgement = ack-nhfb,
articleno = "19",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Othman:2016:CFT,
author = "Abraham Othman and Christos Papadimitriou and Aviad
Rubinstein",
title = "The Complexity of Fairness Through Equilibrium",
journal = j-TEAC,
volume = "4",
number = "4",
pages = "20:1--20:??",
month = aug,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2956583",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Aug 29 06:37:22 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Competitive equilibrium from equal incomes (CEEI) is a
well-known fair allocation mechanism with desirable
fairness and efficiency properties; however, with
indivisible resources, a CEEI may not exist [Foley
1967; Varian 1974; Thomson and Varian 1985]. It was
shown in Budish [2011] that in the case of indivisible
resources, there is always an allocation, called
A-CEEI, that is approximately fair, approximately
truthful, and approximately efficient for some
favorable approximation parameters. A heuristic search
that attempts to find this approximation is used in
practice to assign business school students to courses.
In this article, we show that finding the A-CEEI
allocation guaranteed to exist by Budish's theorem is
PPAD-complete. We further show that finding an
approximate equilibrium with better approximation
guarantees is even harder: NP-complete.",
acknowledgement = ack-nhfb,
articleno = "20",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Hassidim:2016:LCM,
author = "Avinatan Hassidim and Yishay Mansour and Shai Vardi",
title = "Local Computation Mechanism Design",
journal = j-TEAC,
volume = "4",
number = "4",
pages = "21:1--21:??",
month = aug,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2956584",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Aug 29 06:37:22 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We introduce the notion of local computation mechanism
design -designing game-theoretic mechanisms that run in
polylogarithmic time and space. Local computation
mechanisms reply to each query in polylogarithmic time
and space, and the replies to different queries are
consistent with the same global feasible solution. When
the mechanism employs payments, the computation of the
payments is also done in polylogarithmic time and
space. Furthermore, the mechanism needs to maintain
incentive compatibility with respect to the allocation
and payments. We present local computation mechanisms
for two classical game-theoretical problems: stable
matching and job scheduling. For stable matching, some
of our techniques may have implications to the global
(non-LCA (Local Computation Algorithm)) setting.
Specifically, we show that when the men's preference
lists are bounded, we can achieve an arbitrarily good
approximation to the stable matching within a fixed
number of iterations of the Gale--Shapley algorithm.",
acknowledgement = ack-nhfb,
articleno = "21",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Ghosh:2016:OCD,
author = "Arpita Ghosh and Robert Kleinberg",
title = "Optimal Contest Design for Simple Agents",
journal = j-TEAC,
volume = "4",
number = "4",
pages = "22:1--22:??",
month = aug,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2930955",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Aug 29 06:37:22 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Incentives are more likely to elicit desired outcomes
when they are designed based on accurate models of
agents' strategic behavior. A growing literature,
however, suggests that people do not quite behave like
standard economic agents in a variety of environments,
both online and offline. What consequences might such
differences have for the optimal design of mechanisms
in these environments? In this article, we explore this
question in the context of optimal contest design for
simple agents-agents who strategically reason about
whether or not to participate in a system, but not
about the input they provide to it. Specifically,
consider a contest where n potential contestants with
types $ (q_i, c^i) $ each choose between participating
and producing a submission of quality q$^i$ at cost
c$^i$, versus not participating at all to maximize
their utilities. How should a principal distribute a
total prize V among the n ranks to maximize some
increasing function of the qualities of elicited
submissions in a contest with such simple agents? We
first solve the optimal contest design problem for
settings where agents have homogeneous participation
costs $ c^i = c$. Here, the contest that maximizes
every increasing function of the elicited contributions
is always a simple contest, awarding equal prizes of $
V / j^*$ each to the top $ j^*= V / c - \Theta (\sqrt {
V / (c \ln (V / c))})$ contestants. This is in contrast
to the optimal contest structure in comparable models
with strategic effort choices, where the optimal
contest is either a winner-take-all contest or awards
possibly unequal prizes, depending on the curvature of
agents' effort cost functions. We next address the
general case with heterogeneous costs where agents'
types $ (q^i, c^i)$ are inherently two dimensional,
significantly complicating equilibrium analysis. With
heterogeneous costs, the optimal contest depends on the
objective being maximized: our main result here is that
the winner-take-all contest is a 3-approximation of the
optimal contest when the principal's objective is to
maximize the quality of the best elicited contribution.
The proof of this result hinges around a
``subequilibrium'' lemma establishing a stochastic
dominance relation between the distribution of
qualities elicited in an equilibrium and a
subequilibrium --- a strategy profile that is a best
response for all agents who choose to participate in
that strategy profile; this relation between equilibria
and subequilibria may be of more general interest.",
acknowledgement = ack-nhfb,
articleno = "22",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Fudenberg:2016:RRR,
author = "Drew Fudenberg and Alexander Peysakhovich",
title = "Recency, Records, and Recaps: Learning and
Nonequilibrium Behavior in a Simple Decision Problem",
journal = j-TEAC,
volume = "4",
number = "4",
pages = "23:1--23:??",
month = aug,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2956581",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Aug 29 06:37:22 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Nash equilibrium takes optimization as a primitive,
but suboptimal behavior can persist in simple
stochastic decision problems. This has motivated the
development of other equilibrium concepts such as
cursed equilibrium and behavioral equilibrium. We
experimentally study a simple adverse selection (or
``lemons'') problem and find that learning models that
heavily discount past information (i.e., display
recency bias) explain patterns of behavior better than
Nash, cursed, or behavioral equilibrium. Providing
counterfactual information or a record of past outcomes
does little to aid convergence to optimal strategies,
but providing sample averages (``recaps'') gets
individuals most of the way to optimality. Thus,
recency effects are not solely due to limited memory
but stem from some other form of cognitive constraints.
Our results show the importance of going beyond static
optimization and incorporating features of human
learning into economic models used in both
understanding phenomena and designing market
institutions.",
acknowledgement = ack-nhfb,
articleno = "23",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Goldberg:2016:BQC,
author = "Paul W. Goldberg and Aaron Roth",
title = "Bounds for the Query Complexity of Approximate
Equilibria",
journal = j-TEAC,
volume = "4",
number = "4",
pages = "24:1--24:??",
month = aug,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2956582",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Aug 29 06:37:22 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We analyze the number of payoff queries needed to
compute approximate equilibria of multi-player games.
We find that query complexity is an effective tool for
distinguishing the computational difficulty of
alternative solution concepts, and we develop new
techniques for upper- and lower bounding the query
complexity. For binary-choice games, we show
logarithmic upper and lower bounds on the query
complexity of approximate correlated equilibrium. For
well-supported approximate correlated equilibrium (a
restriction where a player's behavior must always be
approximately optimal, in the worst case over draws
from the distribution) we show a linear lower bound,
thus separating the query complexity of well supported
approximate correlated equilibrium from the standard
notion of approximate correlated equilibrium. Finally,
we give a query-efficient reduction from the problem of
computing an approximate well-supported Nash
equilibrium to the problem of verifying a well
supported Nash equilibrium, where the additional query
overhead is proportional to the description length of
the game. This gives a polynomial-query algorithm for
computing well supported approximate Nash equilibria
(and hence correlated equilibria) in concisely
represented games. We identify a class of games (which
includes congestion games) in which the reduction can
be made not only query efficient, but also
computationally efficient.",
acknowledgement = ack-nhfb,
articleno = "24",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Fearnley:2016:FAN,
author = "John Fearnley and Rahul Savani",
title = "Finding Approximate {Nash} Equilibria of Bimatrix
Games via Payoff Queries",
journal = j-TEAC,
volume = "4",
number = "4",
pages = "25:1--25:??",
month = aug,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2956579",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Aug 29 06:37:22 MDT 2016",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study the deterministic and randomized query
complexity of finding approximate equilibria in a $ k
\times k $ bimatrix game. We show that the
deterministic query complexity of finding an \epsilon
-Nash equilibrium when $ \epsilon < 1 / 2 $ is $ \Omega
(k^2) $, even in zero-one constant-sum games. In
combination with previous results [Fearnley et al.
2013], this provides a complete characterization of the
deterministic query complexity of approximate Nash
equilibria. We also study randomized querying
algorithms. We give a randomized algorithm for finding
a $ (3 - \sqrt {5 / 2 + \epsilon })$-Nash equilibrium
using $ O(k \log k / \epsilon^2)$ payoff queries, which
shows that the $ 1 / 2$ barrier for deterministic
algorithms can be broken by randomization. For
well-supported Nash equilibria (WSNE), we first give a
randomized algorithm for finding an $ \epsilon $-WSNE
of a zero-sum bimatrix game using $ O (k \log k /
\epsilon^4)$ payoff queries, and we then use this to
obtain a randomized algorithm for finding a $ (2 / 3 +
\epsilon)$-WSNE in a general bimatrix game using $ O(k
\log k / \epsilon^4)$ payoff queries. Finally, we
initiate the study of lower bounds against randomized
algorithms in the context of bimatrix games, by showing
that randomized algorithms require $ \Omega (k^2)$
payoff queries in order to find an $ \epsilon $-Nash
equilibrium with $ \epsilon < 1 / 4 k$, even in
zero-one constant-sum games. In particular, this rules
out query-efficient randomized algorithms for finding
exact Nash equilibria.",
acknowledgement = ack-nhfb,
articleno = "25",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Hassidim:2016:G,
author = "Avinatan Hassidim and Haim Kaplan and Yishay Mansour
and Noam Nisan",
title = "The {AND--OR} Game",
journal = j-TEAC,
volume = "5",
number = "1",
pages = "1:1--1:??",
month = nov,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2897186",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Apr 3 11:39:17 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We consider a simple simultaneous first price auction
for two identical items in a complete information
setting. Our goal is to analyze this setting for a
simple, yet highly interesting, AND--OR game, where one
agent is single minded and the other is unit demand. We
find a mixed equilibrium of this game and show that
every other equilibrium admits the same expected
allocation and payments. In addition, we study the
equilibrium, highlighting the change in revenue and
social welfare as a function of the players'
valuations.",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Borodin:2016:LGM,
author = "Allan Borodin and Brendan Lucier",
title = "On the Limitations of Greedy Mechanism Design for
Truthful Combinatorial Auctions",
journal = j-TEAC,
volume = "5",
number = "1",
pages = "2:1--2:??",
month = nov,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2956585",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Apr 3 11:39:17 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study mechanisms for the combinatorial auction (CA)
problem, in which $m$ objects are sold to rational
agents and the goal is to maximize social welfare. Of
particular interest is the special case of $s$-CAs,
where agents are interested in sets of size at most
$s$, for which a simple greedy algorithm obtains an $ s
+ 1 $ approximation, but no polynomial time
deterministic truthful mechanism is known to attain an
approximation ratio better than $ O(m / \sqrt {\log
m})$. We view this not only as an extreme gap between
the power of greedy auctions and truthful greedy
auctions, but also as exemplifying the gap between the
known power of truthful and non-truthful polynomial
time deterministic algorithms. We associate the notion
of greediness with a broad class of algorithms, known
as priority algorithms, which encapsulate many natural
auction methods. This motivates us to ask: how well can
a truthful greedy algorithm approximate the optimal
social welfare for CA problems? We show that no
truthful greedy priority algorithm can obtain an
approximation to the CA problem that is sublinear in
$m$, even for $s$-CAs with $ s \geq 2$. Our
inapproximations are independent of any time
constraints on the mechanism and are purely a
consequence of the greedy-type restriction. We conclude
that any truthful combinatorial auction mechanism with
a non-trivial approximation factor must fall outside
the scope of many natural auction methods.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Harks:2016:RQC,
author = "Tobias Harks and Philipp {Von Falkenhausen}",
title = "Robust Quantitative Comparative Statics for a
Multimarket Paradox",
journal = j-TEAC,
volume = "5",
number = "1",
pages = "3:1--3:??",
month = nov,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2956580",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Apr 3 11:39:17 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We introduce a quantitative approach to comparative
statics that allows to bound the maximum effect of an
exogenous parameter change on a system's equilibrium.
The motivation for this approach is a well-known
paradox in multimarket Cournot competition, where a
positive price shock on a monopoly market may actually
reduce the monopolist's profit. We use our approach to
quantify for the first time the worst-case profit
reduction for multimarket oligopolies exposed to
arbitrary positive price shocks. For markets with
affine price functions and firms with convex cost
technologies, we show that the relative profit loss of
any firm is at most 25\%, no matter how many firms
compete in the oligopoly. We further investigate the
impact of positive price shocks on total profit of all
firms as well as on social welfare. We find tight
bounds also for these measures showing that total
profit and social welfare decreases by at most 25\% and
16.6\%, respectively. Finally, we show that in our
model, mixed, correlated, and coarse correlated
equilibria are essentially unique, thus, all our bounds
apply to these game solutions, as well.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Hummel:2016:WDI,
author = "Patrick Hummel and R. Preston Mcafee",
title = "When Does Improved Targeting Increase Revenue?",
journal = j-TEAC,
volume = "5",
number = "1",
pages = "4:1--4:??",
month = nov,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2956586",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Apr 3 11:39:17 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "In second-price auctions, we find that improved
targeting via enhanced information disclosure decreases
revenue when there are two bidders and increases
revenue if there are at least four symmetric bidders
with values drawn from a distribution with a monotone
hazard rate. With asymmetries, improved targeting
increases revenue if the most frequent winner wins less
than 30.4\% of the time under a model in which shares
are well defined, but can decrease revenue otherwise.
We derive analogous results for position auctions.
Finally, we show that revenue can vary nonmonotonically
with the number of bidders who are able to take
advantage of improved targeting.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Piliouras:2016:RSP,
author = "Georgios Piliouras and Evdokia Nikolova and Jeff S.
Shamma",
title = "Risk Sensitivity of Price of Anarchy under
Uncertainty",
journal = j-TEAC,
volume = "5",
number = "1",
pages = "5:1--5:??",
month = nov,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2930956",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Apr 3 11:39:17 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "In game theory, the price of anarchy framework studies
efficiency loss in decentralized environments.
Optimization and decision theory, on the other hand,
explore tradeoffs between optimality and robustness in
the case of single-agent decision making under
uncertainty. What happens when we combine both
approaches? We examine connections between the
efficiency loss due to decentralization and the
efficiency loss due to uncertainty and establish tight
performance guarantees for distributed systems in
uncertain environments. We present applications based
on novel variants of atomic congestion games with
uncertain costs, for which we provide tight performance
bounds under a wide range of risk attitudes. Our
results establish that the individual's attitude toward
uncertainty has a critical effect on system performance
and therefore should be a subject of close and
systematic investigation.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Devanur:2016:RCP,
author = "Nikhil R. Devanur and Jugal Garg and L{\'a}szl{\'o} A.
V{\'e}gh",
title = "A Rational Convex Program for Linear {Arrow--Debreu}
Markets",
journal = j-TEAC,
volume = "5",
number = "1",
pages = "6:1--6:??",
month = nov,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2930658",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Apr 3 11:39:17 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We present a new flow-type convex program describing
equilibrium solutions to linear Arrow--Debreu markets.
Whereas convex formulations were previously known
([Nenakov and Primak 1983; Jain 2007; Cornet 1989]),
our program exhibits several new features. It provides
a simple necessary and sufficient condition and a
concise proof of the existence and rationality of
equilibria, settling an open question raised by
Vazirani [2012]. As a consequence, we also obtain a
simple new proof of the result in Mertens [2003] that
the equilibrium prices form a convex polyhedral set.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Chau:2016:TMC,
author = "Chi-Kin Chau and Khaled Elbassioni and Majid Khonji",
title = "Truthful Mechanisms for Combinatorial Allocation of
Electric Power in Alternating Current Electric Systems
for Smart Grid",
journal = j-TEAC,
volume = "5",
number = "1",
pages = "7:1--7:??",
month = nov,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2955089",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Apr 3 11:39:17 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Traditional studies of combinatorial auctions often
only consider linear constraints. The rise of smart
grid presents a new class of auctions, characterized by
quadratic constraints. This article studies the
complex-demand knapsack problem, in which the demands
are complex valued and the capacity of supplies is
described by the magnitude of total complex-valued
demand. This naturally captures the power constraints
in alternating current electric systems. In this
article, we provide a more complete study and
generalize the problem to the multi-minded version,
beyond the previously known $ \frac
{1}{2}$-approximation algorithm for only a subclass of
the problem. More precisely, we give a truthful
polynomial-time approximation scheme (PTAS) for the
case $ \phi \in [0, \frac {\pi }{2} - \delta]$ and a
truthful fully polynomial-time approximation scheme
(FPTAS), which fully optimizes the objective function
but violates the capacity constraint by at most $ (1 +
\epsilon)$, for the case $ \phi \in (\frac {\pi }{2},
\pi - \delta]$, where $ \phi $ is the maximum argument
of any complex-valued demand and $ \epsilon, \delta >
0$ are arbitrarily small constants. We complement these
results by showing that, unless P=NP, neither a PTAS
forg the case $ \phi \in (\frac {\pi }{2}, \pi \delta]$
nor any bi-criteria approximation algorithm with
polynomial guarantees for the case when $ \phi $ is
arbitrarily close to $ \pi $ (that is, when $ \delta $
is arbitrarily close to 0) can exist.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Feldman:2016:DCC,
author = "Michal Feldman and Ofir Geri",
title = "Do Capacity Constraints Constrain Coalitions?",
journal = j-TEAC,
volume = "5",
number = "1",
pages = "8:1--8:??",
month = nov,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2955090",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Apr 3 11:39:17 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study strong equilibria in symmetric capacitated
cost-sharing connection games. In these games, a graph
with designated source $s$ and sink $t$ is given, and
each edge is associated with some cost. Each agent
chooses strategically an $s$--$t$ path, knowing that
the cost of each edge is shared equally between all
agents using it. Two settings of cost-sharing
connection games have been previously studied: (i)
games where coalitions can form, and (ii) games where
edges are associated with capacities; both settings are
inspired by real-life scenarios. In this work we
combine these scenarios and analyze strong equilibria
(profiles where no coalition can deviate) in
capacitated games. This combination gives rise to new
phenomena that do not occur in the previous settings.
Our contribution is twofold. First, we provide a
topological characterization of networks that always
admit a strong equilibrium. Second, we establish tight
bounds on the efficiency loss that may be incurred due
to strategic behavior, as quantified by the strong
price of anarchy (and stability) measures.
Interestingly, our results qualitatively differ from
those obtained in the analysis of each scenario alone,
and the combination of coalitions and capacities
entails the introduction of more refined topology
classes than previously studied.",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Brandt:2017:CDB,
author = "Felix Brandt and Markus Brill",
title = "Computing Dominance-Based Solution Concepts",
journal = j-TEAC,
volume = "5",
number = "2",
pages = "9:1--9:??",
month = mar,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/2963093",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Wed Aug 9 16:06:10 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Two common criticisms of Nash equilibrium are its
dependence on very demanding epistemic assumptions and
its computational intractability. We study the
computational properties of less demanding set-valued
solution concepts that are based on varying notions of
dominance. These concepts are intuitively appealing,
always exist, and admit unique minimal solutions in
important subclasses of games. Examples include
Shapley's saddles, Harsanyi and Selten's primitive
formations, Basu and Weibull's CURB sets, and Dutta and
Laslier's minimal covering set. Based on a unifying
framework proposed by Duggan and Le Breton, we
formulate two generic algorithms for computing these
concepts and investigate for which classes of games and
which properties of the underlying dominance notion the
algorithms are sound and efficient. We identify two
sets of conditions that are sufficient for
polynomial-time computability and show that the
conditions are satisfied, for instance, by saddles and
primitive formations in normal-form games, minimal CURB
sets in two-player games, and the minimal covering set
in symmetric matrix games. Our positive algorithmic
results explain regularities observed in the
literature, but also apply to several solution concepts
whose computational complexity was previously
unknown.",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Conitzer:2017:FEL,
author = "Vincent Conitzer and Preston McAfee",
title = "Farewell Editorial: Looking Back on Our Terms Editing
{ACM TEAC} and into the Future",
journal = j-TEAC,
volume = "5",
number = "2",
pages = "9:1--9:??",
month = mar,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3079047",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Wed Aug 9 16:06:10 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
acknowledgement = ack-nhfb,
articleno = "9e",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Pennock:2017:ENT,
author = "David Pennock and Ilya Segal",
title = "Editorial from the New {TEAC} {Co-Editors-in-Chief}",
journal = j-TEAC,
volume = "5",
number = "2",
pages = "9:1--9:??",
month = mar,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3084545",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Wed Aug 9 16:06:10 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
acknowledgement = ack-nhfb,
articleno = "9ee",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Pai:2017:ATL,
author = "Mallesh M. Pai and Aaron Roth and Jonathan Ullman",
title = "An Antifolk Theorem for Large Repeated Games",
journal = j-TEAC,
volume = "5",
number = "2",
pages = "10:1--10:??",
month = mar,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/2976734",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Wed Aug 9 16:06:10 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "In this article, we study infinitely repeated games in
settings of imperfect monitoring. We first prove a
family of theorems showing that when the signals
observed by the players satisfy a condition known as $
(\epsilon, \gamma)$-differential privacy, the folk
theorem has little bite: for values of $ \epsilon $ and
$ \gamma $ sufficiently small, for a fixed discount
factor, any equilibrium of the repeated game involves
players playing approximate equilibria of the stage
game in every period. Next we argue that in large games
($n$-player games in which unilateral deviations by
single players have only a small impact on the utility
of other players), many monitoring settings naturally
lead to signals that satisfy $ (\epsilon,
\gamma)$-differential privacy for $ \epsilon $ and $
\gamma $ tending to zero as the number of players $n$
grows large. We conclude that in such settings, the set
of equilibria of the repeated game collapses to the set
of equilibria of the stage game. Our results nest and
generalize previous results of Green [1980] and
Sabourian [1990], suggesting that differential privacy
is a natural measure of the ``largeness'' of a game.
Further, techniques from the literature on differential
privacy allow us to prove quantitative bounds, where
the existing literature focuses on limiting results.",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Azaria:2017:DMM,
author = "Amos Azaria and David Sarne and Yonatan Aumann",
title = "Distributed Matching with Mixed Maximum--Minimum
Utilities",
journal = j-TEAC,
volume = "5",
number = "2",
pages = "11:1--11:??",
month = mar,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3038911",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Wed Aug 9 16:06:10 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "In this article, we study distributed agent matching
with search friction in environments characterized by
costly exploration, where each agent's utility from
forming a partnership is influenced by some linear
combination of the maximum and the minimum among the
two agents' competence. The article provides a cohesive
analysis for such case, proving the equilibrium
structure for the different min-max linear combinations
that may be used. The article presents an extensive
equilibrium analysis of such settings, proving three
distinct resulting patterns of the acceptance
thresholds used by the different agents. The first
relates to settings where a greater emphasis is placed
on the minimum type, or in the extreme case where the
minimum type solely determines the output. In these
cases, the assortative matching characteristic holds,
where all agents set their threshold below their own
type and the greater is the agent type, the greater is
its threshold. When the utility from the partnership
formation is solely determined by the maximum type, we
show that there exists a type $ x^* $ where
partnerships form if and only if one of the agents has
a type equal to or greater than $ x^* $. When a greater
emphasis is placed on the maximum type (but not only),
we prove that assortative matching never holds, and the
change in the agents' acceptance thresholds can
frequently shift from an increase to a decrease.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Chan:2017:PAW,
author = "Hau Chan and Jing Chen and Gowtham Srinivasan",
title = "Provision-After-Wait with Common Preferences",
journal = j-TEAC,
volume = "5",
number = "2",
pages = "12:1--12:??",
month = mar,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3038910",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Wed Aug 9 16:06:10 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "In this article, we study the Provision-after-Wait
problem in healthcare (Braverman, Chen, and Kannan,
2016). In this setting, patients seek a medical
procedure that can be performed by different hospitals
of different costs. Each patient has a value for each
hospital and a budget-constrained government/planner
pays for the expenses of the patients. Patients are
free to choose hospitals, but the planner controls how
much money each hospital gets paid and thus how many
patients each hospital can serve (in one budget period,
say, one month or one year). Waiting times are used in
order to balance the patients' demand, and the
planner's goal is to find a stable assignment that
maximizes the social welfare while keeping the expenses
within the budget. It has been shown that the optimal
stable assignment is NP-hard to compute, and, beyond
this, little is known about the complexity of the
Provision-after-Wait problem. We start by showing that
this problem is in fact strongly NP-hard, and thus does
not have a Fully Polynomial-Time Approximation Scheme
(FPTAS). We then focus on the common preference
setting, where the patients have the same ranking over
the hospitals. Even when the patients perceive the
hospitals' values to them based on the same quality
measurement-referred to as proportional preferences,
which has been widely studied in resource
allocation-the problem is still NP-hard. However, in a
more general setting where the patients are ordered
according to the differences of their values between
consecutive hospitals, we construct an FPTAS for it. To
develop our results, we characterize the structure of
optimal stable assignments and their social welfare,
and we consider a new combinatorial optimization
problem that may be of independent interest, the
ordered Knapsack problem. Optimal stable assignments
are deterministic and ex-post individually rational for
patients. The downside is that waiting times are
dead-loss to patients and may burn a lot of social
welfare. If randomness is allowed, then the planner can
use lotteries as a rationing tool: The hope is that
they reduce the patients' waiting times, although they
are interim individually rational instead of ex-post.
Previous study has only considered lotteries for two
hospitals. In our setting, for arbitrary number of
hospitals, we characterize the structure of the optimal
lottery scheme and conditions under which using
lotteries generates better (expected) social welfare
than using waiting times.",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Babaioff:2017:PPU,
author = "Moshe Babaioff and Liad Blumrosen and Shaddin Dughmi
and Yaron Singer",
title = "Posting Prices with Unknown Distributions",
journal = j-TEAC,
volume = "5",
number = "2",
pages = "13:1--13:??",
month = mar,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3037382",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Wed Aug 9 16:06:10 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We consider a dynamic auction model, where bidders
sequentially arrive to the market. The values of the
bidders for the item for sale are independently drawn
from a distribution, but this distribution is unknown
to the seller. The seller offers a personalized
take-it-or-leave-it price for each arriving bidder and
aims to maximize revenue. We study how well can such
sequential posted-price mechanisms approximate the
optimal revenue that would be achieved if the
distribution was known to the seller. On the negative
side, we show that sequential posted-price mechanisms
cannot guarantee a constant fraction of this revenue
when the class of candidate distributions is
unrestricted. We show that this impossibility holds
even for randomized mechanisms and even if the set of
possible distributions is very small or when the seller
has a prior distribution over the candidate
distributions. On the positive side, we devise a simple
posted-price mechanism that guarantees a constant
fraction of the known-distribution revenue when all
candidate distributions exhibit the monotone hazard
rate property.",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Fadaei:2017:TMG,
author = "Salman Fadaei and Martin Bichler",
title = "A Truthful Mechanism for the Generalized Assignment
Problem",
journal = j-TEAC,
volume = "5",
number = "3",
pages = "14:1--14:??",
month = aug,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3105787",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Wed Aug 9 16:06:10 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We propose a truthful-in-expectation, $ (1 - 1 /
e)$-approximation mechanism for a strategic variant of
the generalized assignment problem (GAP). In GAP, a set
of items has to be optimally assigned to a set of bins
without exceeding the capacity of any singular bin. In
the strategic variant of the problem we study, values
for assigning items to bins are the private information
of bidders and the mechanism should provide bidders
with incentives to truthfully report their values. The
approximation ratio of the mechanism is a significant
improvement over the approximation ratio of the
existing truthful mechanism for GAP. The proposed
mechanism comprises a novel convex optimization program
as the allocation rule as well as an appropriate
payment rule. To implement the convex program in
polynomial time, we propose a fractional local search
algorithm which approximates the optimal solution
within an arbitrarily small error leading to an
approximately truthful-in-expectation mechanism. The
proposed algorithm improves upon the existing
optimization algorithms for GAP in terms of simplicity
and runtime while the approximation ratio closely
matches the best approximation ratio known for GAP when
all inputs are publicly known.",
acknowledgement = ack-nhfb,
articleno = "14",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Jaggard:2017:DBG,
author = "Aaron D. Jaggard and Neil Lutz and Michael Schapira
and Rebecca N. Wright",
title = "Dynamics at the Boundary of Game Theory and
Distributed Computing",
journal = j-TEAC,
volume = "5",
number = "3",
pages = "15:1--15:??",
month = aug,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3107182",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Wed Aug 9 16:06:10 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We use ideas from distributed computing and game
theory to study dynamic and decentralized environments
in which computational nodes, or decision makers,
interact strategically and with limited information. In
such environments, which arise in many real-world
settings, the participants act as both economic and
computational entities. We exhibit a general
non-convergence result for a broad class of dynamics in
asynchronous settings. We consider implications of our
result across a wide variety of interesting and timely
applications: game dynamics, circuit design, social
networks, Internet routing, and congestion control. We
also study the computational and communication
complexity of testing the convergence of asynchronous
dynamics. Our work opens a new avenue for research at
the intersection of distributed computing and game
theory.",
acknowledgement = ack-nhfb,
articleno = "15",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Anshelevich:2017:EFP,
author = "Elliot Anshelevich and Koushik Kar and Shreyas Sekar",
title = "Envy-Free Pricing in Large Markets: Approximating
Revenue and Welfare",
journal = j-TEAC,
volume = "5",
number = "3",
pages = "16:1--16:??",
month = aug,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3105786",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Wed Aug 9 16:06:10 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study the classic setting of envy-free pricing, in
which a single seller chooses prices for its many
items, with the goal of maximizing revenue once the
items are allocated. Despite the large body of work
addressing such settings, most versions of this problem
have resisted good approximation factors for maximizing
revenue; this is true even for the classic unit-demand
case. In this article, we study envy-free pricing with
unit-demand buyers, but unlike previous work we focus
on large markets: ones in which the demand of each
buyer is infinitesimally small compared to the size of
the overall market. We assume that the buyer valuations
for the items they desire have a nice (although
reasonable) structure, that is, that the aggregate
buyer demand has a monotone hazard rate and that the
values of every buyer type come from the same support.
For such large markets, our main contribution is a
1.88-approximation algorithm for maximizing revenue,
showing that good pricing schemes can be computed when
the number of buyers is large. We also give a $ (e,
2)$-bicriteria algorithm that simultaneously
approximates both maximum revenue and welfare, thus
showing that it is possible to obtain both good revenue
and welfare at the same time. We further generalize our
results by relaxing some of our assumptions and
quantify the necessary tradeoffs between revenue and
welfare in our setting. Our results are the first known
approximations for large markets and crucially rely on
new lower bounds, which we prove for the
revenue-maximizing prices.",
acknowledgement = ack-nhfb,
articleno = "16",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Frongillo:2017:GPM,
author = "Rafael Frongillo and Jens Witkowski",
title = "A Geometric Perspective on Minimal Peer Prediction",
journal = j-TEAC,
volume = "5",
number = "3",
pages = "17:1--17:??",
month = aug,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3070903",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Wed Aug 9 16:06:10 MDT 2017",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Minimal peer prediction mechanisms truthfully elicit
private information (e.g., opinions or experiences)
from rational agents without the requirement that
ground truth is eventually revealed. In this article,
we use a geometric perspective to prove that minimal
peer prediction mechanisms are equivalent to power
diagrams, a type of weighted Voronoi diagram. Using
this characterization and results from computational
geometry, we show that many of the mechanisms in the
literature are unique up to affine transformations. We
also show that classical peer prediction is
``complete'' in that every minimal mechanism can be
written as a classical peer prediction mechanism for
some scoring rule. Finally, we use our geometric
characterization to develop a general method for
constructing new truthful mechanisms, and we show how
to optimize for the mechanisms' effort incentives and
robustness.",
acknowledgement = ack-nhfb,
articleno = "17",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Cole:2017:ASR,
author = "Richard Cole and Shravas Rao",
title = "Applications of $ \alpha $-Strongly Regular
Distributions to {Bayesian} Auctions",
journal = j-TEAC,
volume = "5",
number = "4",
pages = "18:1--18:??",
month = dec,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3157083",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Dec 22 18:33:00 MST 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Two classes of distributions that are widely used in
the analysis of Bayesian auctions are the monotone
hazard rate (MHR) and regular distributions. They can
both be characterized in terms of the rate of change of
the associated virtual value functions: for MHR
distributions, the condition is that for values $ v <
v^' $, $ \phi (v^') - \phi (v) \geq v^' - v $, and for
regular distributions, $ \phi (v^') - \phi (v) \geq 0
$. Cole and Roughgarden introduced the interpolating
class of $ \alpha $-strongly regular distributions ($
\alpha $-SR distributions for short), for which $ \phi
(v^') - \phi (v) \geq \alpha (v^' v)$, for $ 0 \leq
\alpha \leq 1$. In this article, we investigate five
distinct auction settings for which good expected
revenue bounds are known when the bidders' valuations
are given by MHR distributions. In every case, we show
that these bounds degrade gracefully when extended to $
\alpha $-SR distributions. For four of these settings,
the auction mechanism requires knowledge of these
distributions (in the remaining setting, the
distributions are needed only to ensure good bounds on
the expected revenue). In these cases, we also
investigate what happens when the distributions are
known only approximately via samples, specifically how
to modify the mechanisms so that they remain effective
and how the expected revenue depends on the number of
samples.",
acknowledgement = ack-nhfb,
articleno = "18",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Giannakopoulos:2017:VMB,
author = "Yiannis Giannakopoulos and Maria Kyropoulou",
title = "The {VCG} Mechanism for {Bayesian} Scheduling",
journal = j-TEAC,
volume = "5",
number = "4",
pages = "19:1--19:??",
month = dec,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3105968",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Dec 22 18:33:00 MST 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study the problem of scheduling m tasks to n
selfish, unrelated machines in order to minimize the
makespan, in which the execution times are independent
random variables, identical across machines. We show
that the VCG mechanism, which myopically allocates each
task to its best machine, achieves an approximation
ratio of O (ln n \&frac; ln ln n ). This improves
significantly on the previously best known bound of O (
m / n ) for prior-independent mechanisms, given by
Chawla et al. [7] under the additional assumption of
Monotone Hazard Rate (MHR) distributions. Although we
demonstrate that this is tight in general, if we do
maintain the MHR assumption, then we get improved,
(small) constant bounds for m {$>$}= n ln n i.i.d.
tasks. We also identify a sufficient condition on the
distribution that yields a constant approximation ratio
regardless of the number of tasks.",
acknowledgement = ack-nhfb,
articleno = "19",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Assadi:2017:FCD,
author = "Sepehr Assadi and Sanjeev Khanna and Yang Li and
Rakesh Vohra",
title = "Fast Convergence in the Double Oral Auction",
journal = j-TEAC,
volume = "5",
number = "4",
pages = "20:1--20:??",
month = dec,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3084358",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Dec 22 18:33:00 MST 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "A classical trading experiment consists of a set of
unit demand buyers and unit supply sellers with
identical items. Each agent's value or opportunity cost
for the item is his private information, and
preferences are quasilinear. Trade between agents
employs a double oral auction (DOA) in which both
buyers and sellers call out bids or offers that an
auctioneer recognizes. Transactions resulting from
accepted bids and offers are recorded. This continues
until there are no more acceptable bids or offers.
Remarkably, the experiment consistently terminates in a
Walrasian price. The main result of this article is a
mechanism in the spirit of the DOA that converges to a
Walrasian equilibrium in a polynomial number of steps,
thus providing a theoretical basis for the empirical
phenomenon described previously. It is well known that
computation of a Walrasian equilibrium for this market
corresponds to solving a maximum weight bipartite
matching problem. The uncoordinated but mildly rational
responses of agents thus solve in a distributed fashion
a maximum weight bipartite matching problem that is
encoded by their private valuations. We show,
furthermore, that every Walrasian equilibrium is
reachable by some sequence of responses. This is in
contrast to the well-known auction algorithms for this
problem that only allow one side to make offers and
thus essentially choose an equilibrium that maximizes
the surplus for the side making offers. Our results
extend to the setting where not every agent pair is
allowed to trade with each other.",
acknowledgement = ack-nhfb,
articleno = "20",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Bjelde:2017:ISP,
author = "Antje Bjelde and Felix Fischer and Max Klimm",
title = "Impartial Selection and the Power of Up to Two
Choices",
journal = j-TEAC,
volume = "5",
number = "4",
pages = "21:1--21:??",
month = dec,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3107922",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Dec 22 18:33:00 MST 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study mechanisms that select members of a set of
agents based on nominations by other members and that
are impartial in the sense that agents cannot influence
their own chance of selection. Prior work has shown
that deterministic mechanisms for selecting any fixed
number k of agents are severely limited and cannot
extract a constant fraction of the nominations of the k
most highly nominated agents. We prove here that this
impossibility result can be circumvented by allowing
the mechanism to sometimes but not always select fewer
than k agents. This added flexibility also improves the
performance of randomized mechanisms, for which we show
a separation between mechanisms that make exactly two
or up to two choices and give upper and lower bounds
for mechanisms allowed more than two choices.",
acknowledgement = ack-nhfb,
articleno = "21",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Adamczyk:2017:SPP,
author = "Marek Adamczyk and Allan Borodin and Diodato Ferraioli
and Bart {De Keijzer} and Stefano Leonardi",
title = "Sequential Posted-Price Mechanisms with Correlated
Valuations",
journal = j-TEAC,
volume = "5",
number = "4",
pages = "22:1--22:??",
month = dec,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3157085",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Dec 22 18:33:00 MST 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study the revenue performance of sequential
posted-price mechanisms and some natural extensions for
a setting where the valuations of the buyers are drawn
from a correlated distribution. Sequential posted-price
mechanisms are conceptually simple mechanisms that work
by proposing a ``take-it-or-leave-it'' offer to each
buyer. We apply sequential posted-price mechanisms to
single-parameter multiunit settings in which each buyer
demands only one item and the mechanism can assign the
service to at most k of the buyers. For standard
sequential posted-price mechanisms, we prove that with
the valuation distribution having finite support, no
sequential posted-price mechanism can extract a
constant fraction of the optimal expected revenue, even
with unlimited supply. We extend this result to the
case of a continuous valuation distribution when
various standard assumptions hold simultaneously (i.e.,
everywhere-supported, continuous, symmetric, and
normalized (conditional) distributions that satisfy
regularity, the MHR condition, and affiliation ). In
fact, it turns out that the best fraction of the
optimal revenue that is extractable by a sequential
posted-price mechanism is proportional to the ratio of
the highest and lowest possible valuation. We prove
that a simple generalization of these mechanisms
achieves a better revenue performance; namely, if the
sequential posted-price mechanism has for each buyer
the option of either proposing an offer or asking the
buyer for its valuation, then a \Omega (1/max { 1, d })
fraction of the optimal revenue can be extracted, where
d denotes the degree of dependence of the valuations,
ranging from complete independence ( d \&equal;0) to
arbitrary dependence ( d = n -1).",
acknowledgement = ack-nhfb,
articleno = "22",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Bosansky:2017:CSE,
author = "Branislav Bosansk{\'y} and Simina Br{\^a}nzei and
Kristoffer Arnsfelt Hansen and Troels Bjerre Lund and
Peter Bro Miltersen",
title = "Computation of {Stackelberg} Equilibria of Finite
Sequential Games",
journal = j-TEAC,
volume = "5",
number = "4",
pages = "23:1--23:??",
month = dec,
year = "2017",
CODEN = "????",
DOI = "https://doi.org/10.1145/3133242",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Fri Dec 22 18:33:00 MST 2017",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "The Stackelberg equilibrium is a solution concept that
describes optimal strategies to commit to: Player 1
(the leader) first commits to a strategy that is
publicly announced, then Player 2 (the follower) plays
a best response to the leader's choice. We study the
problem of computing Stackelberg equilibria in finite
sequential (i.e., extensive-form) games and provide new
exact algorithms, approximation algorithms, and
hardness results for finding equilibria for several
classes of such two-player games.",
acknowledgement = ack-nhfb,
articleno = "23",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Garg:2018:RCD,
author = "Jugal Garg and Ruta Mehta and Vijay V. Vazirani and
Sadra Yazdanbod",
title = "$ \exists $ {R}-Completeness for Decision Versions of
Multi-Player (Symmetric) {Nash} Equilibria",
journal = j-TEAC,
volume = "6",
number = "1",
pages = "1:1--1:??",
month = mar,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3175494",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:45 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "As a result of a series of important works [7--9, 15,
23], the complexity of two-player Nash equilibrium is
by now well understood, even when equilibria with
special properties are desired and when the game is
symmetric. However, for multi-player games, when
equilibria with special properties are desired, the
only result known is due to Schaefer and Stefankovic
[28]: that checking whether a three-player Nash
Equilibrium (3-Nash) instance has an equilibrium in a
ball of radius half in l$_\infty $-norm is $ \exists $
R-complete, where $ \exists $ R is the class of
decision problems that can be reduced in polynomial
time to Existential Theory of the Reals. Building on
their work, we show that the following decision
versions of 3-Nash are also $ \exists $ R-complete:
checking whether (i) there are two or more equilibria,
(ii) there exists an equilibrium in which each player
gets at least h payoff, where h is a rational number,
(iii) a given set of strategies are played with
non-zero probability, and (iv) all the played
strategies belong to a given set. Next, we give a
reduction from 3-Nash to symmetric 3-Nash, hence
resolving an open problem of Papadimitriou [25]. This
yields $ \exists $ R-completeness for symmetric 3-Nash
for the last two problems stated above as well as
completeness for the class FIXP$_a$, a variant of FIXP
for strong approximation. All our results extend to k
-Nash for any constant k {$>$}= 3.",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Candogan:2018:PEG,
author = "Ozan Candogan and Asuman Ozdaglar and Pablo Parrilo",
title = "Pricing Equilibria and Graphical Valuations",
journal = j-TEAC,
volume = "6",
number = "1",
pages = "2:1--2:??",
month = mar,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3175495",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:45 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study pricing equilibria for graphical valuations,
which are a class of valuations that admit a compact
representation. These valuations are associated with a
value graph, whose nodes correspond to items, and edges
encode (pairwise) complementarities/substitutabilities
between items. It is known that for graphical
valuations a Walrasian equilibrium (a pricing
equilibrium that relies on anonymous item prices) does
not exist in general. On the other hand, a pricing
equilibrium exists when the seller uses an
agent-specific graphical pricing rule that involves
prices for each item and markups/discounts for pairs of
items. We study the existence of pricing equilibria
with simpler pricing rules which either (i) require
anonymity (so that prices are identical for all agents)
while allowing for pairwise markups/discounts or (ii)
involve offering prices only for items. We show that a
pricing equilibrium with the latter pricing rule exists
if and only if a Walrasian equilibrium exists, whereas
the former pricing rule may guarantee the existence of
a pricing equilibrium even for graphical valuations
that do not admit a Walrasian equilibrium.
Interestingly, by exploiting a novel connection between
the existence of a pricing equilibrium and the
partitioning polytope associated with the underlying
graph, we also establish that for simple
(series-parallel) value graphs, a pricing equilibrium
with anonymous graphical pricing rule exists if and
only if a Walrasian equilibrium exists. These
equivalence results imply that simpler pricing rules
(i) and (ii) do not guarantee the existence of a
pricing equilibrium for all graphical valuations.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Fujishige:2018:RAP,
author = "Satoru Fujishige and Yoshio Sano and Ping Zhan",
title = "The Random Assignment Problem with Submodular
Constraints on Goods",
journal = j-TEAC,
volume = "6",
number = "1",
pages = "3:1--3:??",
month = mar,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3175496",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:45 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Problems of allocating indivisible goods to agents in
an efficient and fair manner without money have long
been investigated in literature. The random assignment
problem is one of them, where we are given a fixed
feasible (available) set of indivisible goods and a
profile of ordinal preferences over the goods, one for
each agent. Then, using lotteries, we determine an
assignment of goods to agents in a randomized way. A
seminal paper of Bogomolnaia and Moulin (2001) shows a
probabilistic serial (PS) mechanism to give an
ordinally efficient and envy-free solution to the
assignment problem. In this article, we consider an
extension of the random assignment problem to
submodular constraints on goods. We show that the
approach of the PS mechanism by Bogomolnaia and Moulin
is powerful enough to solve the random assignment
problem with submodular (matroidal and polymatroidal)
constraints. Under the agents' ordinal preferences over
goods we show the following: (1) The obtained PS
solution for the problem with unit demands and
matroidal constraints is ordinally efficient,
envy-free, and weakly strategy-proof with respect to
the associated stochastic dominance relation. (2)For
the multiunit demand and polymatroidal constraint
problem, the PS solution is ordinally efficient and
envy-free but is not strategy-proof in general.
However, we show that under a mild condition (that is
likely to be satisfied in practice) the PS solution is
a weak Nash equilibrium.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Harks:2018:CPR,
author = "Tobias Harks and Britta Peis and Daniel Schmand and
Bjoern Tauer and Laura Vargas Koch",
title = "Competitive Packet Routing with Priority Lists",
journal = j-TEAC,
volume = "6",
number = "1",
pages = "4:1--4:??",
month = mar,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3184137",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:45 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "In competitive packet routing games, the packets are
routed selfishly through a network and scheduling
policies at edges determine which packets are forwarded
first if there is not enough capacity on an edge to
forward all packets at once. We analyze the impact of
priority lists on the worst-case quality of pure Nash
equilibria. A priority list is an ordered list of
players that may or may not depend on the edge.
Whenever the number of packets entering an edge exceeds
the inflow capacity, packets are processed in list
order. We derive several new bounds on the price of
anarchy and stability for global and local priority
policies. We also consider the question of the
complexity of computing an optimal priority list. It
turns out that even for very restricted cases, i.e.,
for routing on a tree, the computation of an optimal
priority list is APX-hard.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Dutting:2018:VCV,
author = "Paul D{\"u}tting and Monika Henzinger and Martin
Starnberger",
title = "Valuation Compressions in {VCG}-Based Combinatorial
Auctions",
journal = j-TEAC,
volume = "6",
number = "2",
pages = "5:1--5:??",
month = oct,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3232860",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "The focus of classic mechanism design has been on
truthful direct-revelation mechanisms. In the context
of combinatorial auctions, the truthful
direct-revelation mechanism that maximizes social
welfare is the Vickrey-Clarke-Groves mechanism. For
many valuation spaces, computing the allocation and
payments of the VCG mechanism, however, is a
computationally hard problem. We thus study the
performance of the VCG mechanism when bidders are
forced to choose bids from a subspace of the valuation
space for which the VCG outcome can be computed
efficiently. We prove improved upper bounds on the
welfare loss for restrictions to additive bids and
upper and lower bounds for restrictions to non-additive
bids. These bounds show that increased expressiveness
can give rise to additional equilibria of poorer
efficiency.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Irfan:2018:CSI,
author = "Mohammad T. Irfan and Luis E. Ortiz",
title = "Causal Strategic Inference in a Game-Theoretic Model
of Multiplayer Networked Microfinance Markets",
journal = j-TEAC,
volume = "6",
number = "2",
pages = "6:1--6:??",
month = oct,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3232861",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "Performing interventions is a major challenge in
economic policy-making. We present causal strategic
inference as a framework for conducting interventions
and apply it to large, networked microfinance
economies. The basic solution platform consists of
modeling a microfinance market as a networked economy,
learning the model using single-sample real-world
microfinance data, and designing algorithms for various
causal questions. For a special case of our model, we
show that an equilibrium point always exists and that
the equilibrium interest rates are unique. For the
general case, we give a constructive proof of the
existence of an equilibrium point. Our empirical study
is based on microfinance data from Bangladesh and
Bolivia, which we use to first learn our models. We
show that causal strategic inference can assist
policy-makers by evaluating the outcomes of various
types of interventions, such as removing a loss-making
bank from the market, imposing an interest-rate cap,
and subsidizing banks.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Ghosh:2018:CC,
author = "Arpita Ghosh and Patrick Hummel",
title = "Cardinal Contests",
journal = j-TEAC,
volume = "6",
number = "2",
pages = "7:1--7:??",
month = oct,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3232862",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We model and analyze cardinal contests, where a
principal running a rank-order tournament has access to
an absolute measure of the quality of agents'
submissions in addition to their relative rankings. We
show that a mechanism that compares each agent's output
quality against a threshold to decide whether to award
her the prize corresponding to her rank is optimal
amongst the set of all mixed cardinal-ordinal
mechanisms where the j th-ranked submission receives a
fraction of the j th prize that is a non-decreasing
function of the submission's quality. Furthermore, the
optimal threshold mechanism uses exactly the same
threshold for each rank.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Wang:2018:VPS,
author = "Weina Wang and Lei Ying and Junshan Zhang",
title = "The Value of Privacy: Strategic Data Subjects,
Incentive Mechanisms, and Fundamental Limits",
journal = j-TEAC,
volume = "6",
number = "2",
pages = "8:1--8:??",
month = oct,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3232863",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "We study the value of data privacy in a game-theoretic
model of trading private data, where a data collector
purchases private data from strategic data subjects
(individuals) through an incentive mechanism. One
primary goal of the data collector is to learn some
desired information from the elicited data.
Specifically, this information is modeled by an
underlying state, and the private data of each
individual represents his of her knowledge about the
state. Departing from most of the existing work on
privacy-aware surveys, our model does not assume the
data collector to be trustworthy. Further, an
individual takes full control of his or her own data
privacy and reports only a privacy-preserving version
of his or her data. In this article, the value of
\epsilon units of privacy is measured by the minimum
payment among all nonnegative payment mechanisms, under
which an individual's best response at a Nash
equilibrium is to report his or her data in an \epsilon
-locally differentially private manner. The higher
\epsilon is, the less private the reported data is. We
derive lower and upper bounds on the value of privacy
that are asymptotically tight as the number of data
subjects becomes large. Specifically, the lower bound
assures that it is impossible to use a lower payment to
buy \epsilon units of privacy, and the upper bound is
given by an achievable payment mechanism that we
design. Based on these fundamental limits, we further
derive lower and upper bounds on the minimum total
payment for the data collector to achieve a given
accuracy target for learning the underlying state and
show that the total payment of the designed mechanism
is at most one individual's payment away from the
minimum.",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Velez:2018:ERD,
author = "Rodrigo A. Velez",
title = "Equitable Rent Division",
journal = j-TEAC,
volume = "6",
number = "2",
pages = "9:1--9:??",
month = oct,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3274528",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
abstract = "How should a group of roommates allocate the rooms and
contributions to rent in the house they lease?
Economists have provided partial answers to this
question in a literature that spans the last 40 years.
Unfortunately, these results were developed in a
non-linear fashion, which obscures them to the
non-specialist. Recently, computer scientists have
developed an interest in this problem, advancing from
an algorithmic complexity perspective. With this new
interest gaining traction, there is an evident need for
a coherent development of the results in economics
literature. This article does so. In particular, we
build connections among results that were seemingly
unrelated and considerably simplify their development,
fill in non-trivial gaps, and identify open questions.
Our focus is on incentives issues, the area in which we
believe economists have more to contribute in this
discussion.",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Feldman:2018:ISI,
author = "Michal Feldman and Brendan Lucier and Michael
Schwarz",
title = "Introduction to the Special Issue on {EC'15}",
journal = j-TEAC,
volume = "6",
number = "3--4",
pages = "10:1--10:??",
month = nov,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3274531",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3274531",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Kurokawa:2018:LAR,
author = "David Kurokawa and Ariel D. Procaccia and Nisarg
Shah",
title = "Leximin Allocations in the Real World",
journal = j-TEAC,
volume = "6",
number = "3--4",
pages = "11:1--11:??",
month = nov,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3274641",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3274641",
abstract = "As part of a collaboration with a major California
school district, we study the problem of fairly
allocating unused classrooms in public schools to
charter schools. Our approach revolves around the
randomized leximin mechanism. We extend previous work
to show that the leximin mechanism is proportional,
envy-free, Pareto optimal, and group strategyproof, not
only in our classroom allocation setting, but in a
general framework that subsumes a number of settings
previously studied in the literature. We also prove
that the leximin mechanism provides a (worst-case)
4-approximation to the maximum number of classrooms
that can possibly be allocated. Our experiments, which
are based on real data, show that a non-trivial
implementation of the leximin mechanism scales
gracefully in terms of running time (even though the
problem is intractable in theory), and performs
extremely well with respect to a number of efficiency
objectives. We establish the practicability of our
approach, and discuss issues related to its
deployment.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Kannan:2018:PPO,
author = "Sampath Kannan and Jamie Morgenstern and Ryan Rogers
and Aaron Roth",
title = "Private {Pareto} Optimal Exchange",
journal = j-TEAC,
volume = "6",
number = "3--4",
pages = "12:1--12:??",
month = nov,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3105445",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3105445",
abstract = "We consider the problem of implementing an
individually rational, asymptotically Pareto optimal
allocation in a barter-exchange economy where agents
are endowed with goods and preferences over the goods
of others, but may not use money as a medium of
exchange. Because one of the most important
instantiations of such economies is kidney
exchange-where the ``input'' to the problem consists of
sensitive patient medical records-we ask to what extent
such exchanges can be carried out while providing
formal privacy guarantees to the participants. We show
that individually rational allocations cannot achieve
any non-trivial approximation to Pareto optimality if
carried out under the constraint of differential
privacy-or even the relaxation of joint -differential
privacy, under which it is known that asymptotically
optimal allocations can be computed in two sided
markets (Hsu et al. STOC 2014). We therefore consider a
further relaxation that we call marginal -differential
privacy-which promises, informally, that the privacy of
every agent i is protected from every other agent j /=
i so long as j does not collude or share allocation
information with other agents. We show that under
marginal differential privacy, it is possible to
compute an individually rational and asymptotically
Pareto optimal allocation in such exchange economies.",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Blum:2018:LWG,
author = "Avrim Blum and Yishay Mansour and Jamie Morgenstern",
title = "Learning What's Going on: Reconstructing Preferences
and Priorities from Opaque Transactions",
journal = j-TEAC,
volume = "6",
number = "3--4",
pages = "13:1--13:??",
month = nov,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3274642",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3274642",
abstract = "We consider a setting where n buyers, with
combinatorial preferences over m items, and a seller,
running a priority-based allocation mechanism,
repeatedly interact. Our goal, from observing limited
information about the results of these interactions, is
to reconstruct both the preferences of the buyers and
the mechanism of the seller. More specifically, we
consider an online setting where at each stage, a
subset of the buyers arrive and are allocated items,
according to some unknown priority that the seller has
among the buyers. Our learning algorithm observes only
which buyers arrive and the allocation produced (or
some function of the allocation, such as just which
buyers received positive utility and which did not),
and its goal is to predict the outcome for future
subsets of buyers. For this task, the learning
algorithm needs to reconstruct both the priority among
the buyers and the preferences of each buyer. We derive
mistake bound algorithms for additive, unit-demand and
single-minded buyers. We also consider the case where
buyers' utilities for a fixed bundle can change between
stages due to different (observed) prices. Our
algorithms are efficient both in computation time and
in the maximum number of mistakes (both polynomial in
the number of buyers and items).",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Esfandiari:2018:ATS,
author = "Hossein Esfandiari and Nitish Korula and Vahab
Mirrokni",
title = "Allocation with Traffic Spikes: Mixing Adversarial and
Stochastic Models",
journal = j-TEAC,
volume = "6",
number = "3--4",
pages = "14:1--14:??",
month = nov,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3105446",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3105446",
abstract = "Motivated by Internet advertising applications, online
allocation problems have been studied extensively in
various adversarial and stochastic models. While the
adversarial arrival models are too pessimistic, many of
the stochastic (such as i.i.d. or random-order) arrival
models do not realistically capture uncertainty in
predictions. A significant cause for such uncertainty
is the presence of unpredictable traffic spikes, often
due to breaking news or similar events. To address this
issue, a simultaneous approximation framework has been
proposed to develop algorithms that work well both in
the adversarial and stochastic models; however, this
framework does not enable algorithms that make good use
of partially accurate forecasts when making online
decisions. In this article, we propose a robust online
stochastic model that captures the nature of traffic
spikes in online advertising. In our model, in addition
to the stochastic input for which we have good
forecasting, an unknown number of impressions arrive
that are adversarially chosen. We design algorithms
that combine a stochastic algorithm with an online
algorithm that adaptively reacts to inaccurate
predictions. We provide provable bounds for our new
algorithms in this framework. We accompany our positive
results with a set of hardness results showing that our
algorithms are not far from optimal in this framework.
As a byproduct of our results, we also present improved
online algorithms for a slight variant of the
simultaneous approximation framework.",
acknowledgement = ack-nhfb,
articleno = "14",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Heidari:2018:IMM,
author = "Hoda Heidari and S{\'e}bastien Lahaie and David M.
Pennock and Jennifer Wortman Vaughan",
title = "Integrating Market Makers, Limit Orders, and
Continuous Trade in Prediction Markets",
journal = j-TEAC,
volume = "6",
number = "3--4",
pages = "15:1--15:??",
month = nov,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3274643",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3274643",
abstract = "We provide the first concrete algorithm for combining
market makers and limit orders in a prediction market
with continuous trade. Our mechanism is general enough
to handle both bundle orders and arbitrary securities
defined over combinatorial outcome spaces. We define
the notion of an \epsilon -fair trading path, a path in
security space along which no order executes at a price
more than \epsilon above its limit, and every order
executes when its market price falls more than \epsilon
below its limit. We show that, under a certain
supermodularity condition, a fair trading path exists
for which the endpoint is efficient, but that under
general conditions reaching an efficient endpoint via
an \epsilon -fair trading path is not possible. We
develop an algorithm for operating a continuous market
maker with limit orders that respects the \epsilon
-fairness conditions in the general case. We conduct
simulations of our algorithm using real combinatorial
predictions made during the 2008 US presidential
election and evaluate it against a natural baseline
according to trading volume, social welfare, and
violations of the two fairness conditions.",
acknowledgement = ack-nhfb,
articleno = "15",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Naor:2018:NOO,
author = "Joseph (Seffi) Naor and David Wajc",
title = "Near-Optimum Online Ad Allocation for Targeted
Advertising",
journal = j-TEAC,
volume = "6",
number = "3--4",
pages = "16:1--16:??",
month = nov,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3105447",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3105447",
abstract = "Motivated by Internet targeted advertising, we address
several ad allocation problems. Prior work has
established that these problems admit no randomized
online algorithm better than (1 --- 1/ e)-competitive
(see Karp et al. (1990) and Mehta et al. (2007)), yet
simple heuristics have been observed to perform much
better in practice. We explain this phenomenon by
studying a generalization of the bounded-degree inputs
considered by Buchbinder et al. (2007), graphs which we
call (k, d)- bounded. In such graphs the maximal degree
on the online side is at most d and the minimal degree
on the offline side is at least k. We prove that, for
such graphs, these problems' natural greedy algorithms
attain a competitive ratio of 1 --- d -1/ k + d -1,
tending to 1 as d / k tends to zero. We prove this
bound is tight for these algorithms. Next, we develop
deterministic primal-dual algorithms for the above
problems, achieving a competitive ratio of 1-(1 --- 1/
d)$^k$ \> 1 --- \& 1/ e$^{k / d}$, or exponentially
better loss as a function of k / /d, and strictly
better than 1 --- 1/e whenever k {$>$}= d. We
complement our lower bounds with matching upper bounds
for the vertex-weighted problem. Finally, we use our
deterministic algorithms to prove by dual-fitting that
simple randomized algorithms achieve the same bounds in
expectation. Our algorithms and analysis differ from
previous ad allocation algorithms, which largely scale
bids based on the spent fraction of their bidder's
budget, whereas we scale bids according to the number
of times the bidder could have spent as much as her
current bid. Our algorithms differ from previous online
primal-dual algorithms in that they do not maintain
dual feasibility but only a primal-to-dual ratio and
only attain dual feasibility upon termination. We
believe our techniques could find applications to other
well-behaved online packing problems.",
acknowledgement = ack-nhfb,
articleno = "16",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Kleinberg:2018:TPT,
author = "Jon Kleinberg and Maithra Raghu",
title = "Team Performance with Test Scores",
journal = j-TEAC,
volume = "6",
number = "3--4",
pages = "17:1--17:??",
month = nov,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3274644",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3274644",
abstract = "Team performance is a ubiquitous area of inquiry in
the social sciences, and it motivates the problem of
team selection -choosing the members of a team for
maximum performance. Influential work of Hong and Page
has argued that testing individuals in isolation and
then assembling the highest scoring ones into a team is
not an effective method for team selection. For a broad
class of performance measures, based on the expected
maximum of random variables representing individual
candidates, we show that tests directly measuring
individual performance are indeed ineffective, but that
a more subtle family of tests used in isolation can
provide a constant-factor approximation for team
performance. These new tests measure the ``potential''
of individuals, in a precise sense, rather than
performance; to our knowledge they represent the first
time that individual tests have been shown to produce
near-optimal teams for a nontrivial team performance
measure. We also show families of subdmodular and
supermodular team performance functions for which no
test applied to individuals can produce near-optimal
teams, and we discuss implications for submodular
maximization via hill-climbing.",
acknowledgement = ack-nhfb,
articleno = "17",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Gopalan:2018:PPB,
author = "Parikshit Gopalan and Noam Nisan and Tim Roughgarden",
title = "Public Projects, {Boolean} Functions, and the Borders
of {Border}'s Theorem",
journal = j-TEAC,
volume = "6",
number = "3--4",
pages = "18:1--18:??",
month = nov,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3274645",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3274645",
abstract = "Border's theorem gives an intuitive linear
characterization of the feasible interim allocation
rules of a Bayesian single-item environment, and it has
several applications in economic and algorithmic
mechanism design. All known generalizations of Border's
theorem either restrict attention to relatively simple
settings or resort to approximation. This article
identifies a complexity-theoretic barrier that
indicates, assuming standard complexity class
separations, that Border's theorem cannot be extended
significantly beyond the state of the art. We also
identify a surprisingly tight connection between
Myerson's optimal auction theory, when applied to
public project settings, and some fundamental results
in the analysis of Boolean functions.",
acknowledgement = ack-nhfb,
articleno = "18",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Rubinstein:2018:SMS,
author = "Aviad Rubinstein and S. Matthew Weinberg",
title = "Simple Mechanisms for a Subadditive Buyer and
Applications to Revenue Monotonicity",
journal = j-TEAC,
volume = "6",
number = "3--4",
pages = "19:1--19:??",
month = nov,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3105448",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3105448",
abstract = "We study the revenue maximization problem of a seller
with n heterogeneous items for sale to a single buyer
whose valuation function for sets of items is unknown
and drawn from some distribution D. We show that if D
is a distribution over subadditive valuations with
independent items, then the better of pricing each item
separately or pricing only the grand bundle achieves a
constant-factor approximation to the revenue of the
optimal mechanism. This includes buyers who are k
-demand, additive up to a matroid constraint, or
additive up to constraints of any downward-closed set
system (and whose values for the individual items are
sampled independently), as well as buyers who are
fractionally subadditive with item multipliers drawn
independently. Our proof makes use of the core-tail
decomposition framework developed in prior work showing
similar results for the significantly simpler class of
additive buyers. In the second part of the article, we
develop a connection between approximately optimal
simple mechanisms and approximate revenue monotonicity
with respect to buyers' valuations. Revenue
non-monotonicity is the phenomenon that sometimes
strictly increasing buyers' values for every set can
strictly decrease the revenue of the optimal mechanism.
Using our main result, we derive a bound on how bad
this degradation can be (and dub such a bound a proof
of approximate revenue monotonicity); we further show
that better bounds on approximate monotonicity imply a
better analysis of our simple mechanisms.",
acknowledgement = ack-nhfb,
articleno = "19",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Daskalakis:2018:RME,
author = "Constantinos Daskalakis and Nikhil R. Devanur and S.
Matthew Weinberg",
title = "Revenue Maximization and Ex-Post Budget Constraints",
journal = j-TEAC,
volume = "6",
number = "3--4",
pages = "20:1--20:??",
month = nov,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3274647",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3274647",
abstract = "We consider the problem of a revenue-maximizing seller
with m items for sale to n additive bidders with hard
budget constraints, assuming that the seller has some
prior distribution over bidder values and budgets. The
prior may be correlated across items and budgets of the
same bidder, but is assumed independent across bidders.
We target mechanisms that are Bayesian incentive
compatible, but that are ex-post individually rational
and ex-post budget respecting. Virtually no such
mechanisms are known that satisfy all these conditions
and guarantee any revenue approximation, even with just
a single item. We provide a computationally efficient
mechanism that is a 3-approximation with respect to all
BIC, ex-post IR, and ex-post budget respecting
mechanisms. Note that the problem is NP-hard to
approximate better than a factor of 16/15, even in the
case where the prior is a point mass. We further
characterize the optimal mechanism in this setting,
showing that it can be interpreted as a distribution
over virtual welfare maximizers. We prove our results
by making use of a black-box reduction from mechanism
to algorithm design developed by Cai et al. Our main
technical contribution is a computationally efficient
3-approximation algorithm for the algorithmic problem
that results from an application of their framework to
this problem. The algorithmic problem has a mixed-sign
objective and is NP-hard to optimize exactly, so it is
surprising that a computationally efficient
approximation is possible at all. In the case of a
single item (m =1), the algorithmic problem can be
solved exactly via exhaustive search, leading to a
computationally efficient exact algorithm and a
stronger characterization of the optimal mechanism as a
distribution over virtual value maximizers.",
acknowledgement = ack-nhfb,
articleno = "20",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Bronfman:2018:RIM,
author = "Slava Bronfman and Noga Alon and Avinatan Hassidim and
Assaf Romm",
title = "Redesigning the {Israeli} Medical Internship Match",
journal = j-TEAC,
volume = "6",
number = "3--4",
pages = "21:1--21:??",
month = nov,
year = "2018",
CODEN = "????",
DOI = "https://doi.org/10.1145/3274646",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3274646",
abstract = "The final step in getting an Israeli MD is performing
a year-long internship in one of the hospitals in
Israel. Internships are decided upon by a lottery,
which is known as the Internship Lottery. In 2014, we
redesigned the lottery, replacing it with a more
efficient one. This article presents the market, the
redesign process, and the new mechanism that is now in
use. In this article, we describe the redesign and
focus on two-body problems that we faced in the new
mechanism. Specifically, we show that decomposing
stochastic assignment matrices to deterministic
allocations is NP-hard in the presence of couples, and
present a polynomial-time algorithm with the optimal
worst case guarantee. We also study the performance of
our algorithm on real-world and simulated data.",
acknowledgement = ack-nhfb,
articleno = "21",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Kirousis:2019:AVM,
author = "Lefteris Kirousis and Phokion G. Kolaitis and John
Livieratos",
title = "Aggregation of Votes with Multiple Positions on Each
Issue",
journal = j-TEAC,
volume = "7",
number = "1",
pages = "1:1--1:??",
month = feb,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3296675",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3296675",
abstract = "We consider the problem of aggregating votes cast by a
society on a fixed set of issues, where each member of
the society may vote for one of several positions on
each issue, but the combination of votes on the various
issues is restricted to a set of feasible voting
patterns. We follow the aggregation framework used by
Dokow and Holzman [Aggregation of non-binary
evaluations, Advances in Applied Mathematics, 45:4,
487--504, 2010], in which both preference aggregation
and judgment aggregation can be cast. We require the
aggregation to be independent on each issue, and also
supportive, i.e., for every issue, the corresponding
component of every aggregator, when applied to a tuple
of votes, must take as value one of the votes in that
tuple. We prove that, in such a setup, non-dictatorial
aggregation of votes in a society of an arbitrary size
is possible if and only if either there is a
non-dictatorial aggregator for two voters or there is
an aggregator for three voters such that, for each
issue, the corresponding component of the aggregator,
when restricted to two-element sets of votes, is a
majority operation or a minority operation. We then
introduce a notion of a uniform non-dictatorial
aggregator, which is an aggregator such that on every
issue, and when restricted to arbitrary two-element
subsets of the votes for that issue, it differs from
all projection functions. We first give a
characterization of sets of feasible voting patterns
that admit a uniform non-dictatorial aggregator. After
this and by making use of Bulatov's dichotomy theorem
for conservative constraint satisfaction problems, we
connect social choice theory with the computational
complexity of constraint satisfaction by proving that
if a set of feasible voting patterns has a uniform
non-dictatorial aggregator of some arity, then the
multi-sorted conservative constraint satisfaction
problem on that set (with each issue representing a
different sort) is solvable in polynomial time;
otherwise, it is NP-complete.",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Kong:2019:ITF,
author = "Yuqing Kong and Grant Schoenebeck",
title = "An Information Theoretic Framework For Designing
Information Elicitation Mechanisms That Reward
Truth-telling",
journal = j-TEAC,
volume = "7",
number = "1",
pages = "2:1--2:??",
month = feb,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3296670",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3296670",
abstract = "In the setting where information cannot be verified,
we propose a simple yet powerful information
theoretical framework-the Mutual Information
Paradigm-for information elicitation mechanisms. Our
framework pays every agent a measure of mutual
information between her signal and a peer's signal. We
require that the mutual information measurement has the
key property that any ``data processing'' on the two
random variables will decrease the mutual information
between them. We identify such information measures
that generalize Shannon mutual information. Our Mutual
Information Paradigm overcomes the two main challenges
in information elicitation without verification: (1)
how to incentivize high-quality reports and avoid
agents colluding to report random or identical
responses; (2) how to motivate agents who believe they
are in the minority to report truthfully. Aided by the
information measures, we found (1) we use the paradigm
to design a family of novel mechanisms where
truth-telling is a dominant strategy and pays better
than any other strategy profile (in the multi-question,
detail free, minimal setting where the number of
questions is large); (2) we show the versatility of our
framework by providing a unified theoretical
understanding of existing mechanisms-Bayesian Truth
Serum Prelec (2004) and Dasgupta and Ghosh (2013)-by
mapping them into our framework such that theoretical
results of those existing mechanisms can be
reconstructed easily. We also give an impossibility
result that illustrates, in a certain sense, the the
optimality of our framework.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Faliszewski:2019:CSR,
author = "Piotr Faliszewski and Piotr Skowron and Arkadii Slinko
and Nimrod Talmon",
title = "Committee Scoring Rules: Axiomatic Characterization
and Hierarchy",
journal = j-TEAC,
volume = "7",
number = "1",
pages = "3:1--3:??",
month = feb,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3296672",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3296672",
abstract = "Committee scoring voting rules are multiwinner
analogues of positional scoring rules, which constitute
an important subclass of single-winner voting rules. We
identify several natural subclasses of committee
scoring rules, namely, weakly separable,
representation-focused, top- k -counting, OWA-based,
and decomposable rules. We characterize SNTV, Bloc, and
k -Approval Chamberlin--Courant as the only nontrivial
rules in pairwise intersections of these classes. We
provide some axiomatic characterizations for these
classes, where monotonicity properties appear to be
especially useful. The class of decomposable rules is
new to the literature. We show that it strictly
contains the class of OWA-based rules and describe some
of the applications of decomposable rules.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Abraham:2019:DPL,
author = "Ittai Abraham and Danny Dolev and Joseph Y. Halpern",
title = "Distributed Protocols for Leader Election: a
Game-Theoretic Perspective",
journal = j-TEAC,
volume = "7",
number = "1",
pages = "4:1--4:??",
month = feb,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3303712",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:46 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3303712",
abstract = "We do a game-theoretic analysis of leader election,
under the assumption that each agent prefers to have
some leader than no leader at all. We show that it is
possible to obtain a fair Nash equilibrium, where each
agent has an equal probability of being elected leader,
in a completely connected network, in a bidirectional
ring, and a unidirectional ring, in the synchronous
setting. In the asynchronous setting, Nash equilibrium
is not quite the right solution concept. Rather, we
must consider ex post Nash equilibrium; this means that
we have a Nash equilibrium no matter what a scheduling
adversary does. We show that ex post Nash equilibrium
is attainable in the asynchronous setting in all the
networks we consider, using a protocol with bounded
running time. However, in the asynchronous setting, we
require that n \> 2. We show that we can get a fair
ex post \epsilon -Nash equilibrium if n =2 in the
asynchronous setting under some cryptographic
assumptions (specifically, the existence of a one-way
functions), using a commitment protocol. We then
generalize these results to a setting where we can have
deviations by a coalition of size k. In this case, we
can get what we call a fair k -resilient equilibrium in
a completely connected network if n \> 2 k; under
the same cryptographic assumptions, we can a get a k
-resilient equilibrium in a completely connected
network, unidirectional ring, or bidirectional ring if
n \> k. Finally, we show that under minimal
assumptions, not only do our protocols give a Nash
equilibrium, they also give a sequential equilibrium,
so players even play optimally off the equilibrium
path.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Hummel:2019:BLT,
author = "Patrick Hummel and Uri Nadav",
title = "Bid-Limited Targeting",
journal = j-TEAC,
volume = "7",
number = "2",
pages = "5:1--5:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3327968",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:47 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3327968",
abstract = "This article analyzes a mechanism for selling items in
auctions in which the auctioneer specifies a cap on the
ratio between the maximum and minimum bids that bidders
may use in the auctions. Such a mechanism is widely
used in online advertising through the caps that
companies impose on the minimum and maximum bid
multipliers that advertisers may use in targeting. When
bidders' values are independent and identically
distributed, this mechanism results in greater revenue
than allowing bidders to condition their bids on the
targeting information in an arbitrary way and also
almost always results in greater revenue than not
allowing bidders to target. Choosing the optimal cap on
the ratio between the maximum and minimum bids can also
be more important than introducing additional
competition in the auction. However, if bidders' values
are not identically distributed, pure-strategy
equilibria may fail to exist.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Aziz:2019:FHG,
author = "Haris Aziz and Florian Brandl and Felix Brandt and
Paul Harrenstein and Martin Olsen and Dominik Peters",
title = "Fractional Hedonic Games",
journal = j-TEAC,
volume = "7",
number = "2",
pages = "6:1--6:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3327970",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:47 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3327970",
abstract = "The work we present in this article initiated the
formal study of fractional hedonic games (FHGs),
coalition formation games in which the utility of a
player is the average value he ascribes to the members
of his coalition. Among other settings, this covers
situations in which players only distinguish between
friends and non-friends and desire to be in a coalition
in which the fraction of friends is maximal. FHGs thus
not only constitute a natural class of succinctly
representable coalition formation games but also
provide an interesting framework for network
clustering. We propose a number of conditions under
which the core of FHGs is non-empty and provide
algorithms for computing a core stable outcome. By
contrast, we show that the core may be empty in other
cases, and that it is computationally hard in general
to decide non-emptiness of the core.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Kash:2019:SPS,
author = "Ian A. Kash and Peter Key and Warut Suksompong",
title = "Simple Pricing Schemes for the Cloud",
journal = j-TEAC,
volume = "7",
number = "2",
pages = "7:1--7:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3327973",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:47 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3327973",
abstract = "The problem of pricing the cloud has attracted much
recent attention due to the widespread use of cloud
computing and cloud services. From a theoretical
perspective, several mechanisms that provide strong
efficiency or fairness guarantees and desirable
incentive properties have been designed. However, these
mechanisms often rely on a rigid model, with several
parameters needing to be precisely known for the
guarantees to hold. In this article, we consider a
stochastic model and show that it is possible to obtain
good welfare and revenue guarantees with simple
mechanisms that do not make use of the information on
some of these parameters. In particular, we prove that
a mechanism that sets the same price per timestep for
jobs of any length achieves at least 50\% of the
welfare and revenue obtained by a mechanism that can
set different prices for jobs of different lengths, and
the ratio can be improved if we have more specific
knowledge of some parameters. Similarly, a mechanism
that sets the same price for all servers even though
the servers may receive different kinds of jobs can
provide a reasonable welfare and revenue approximation
compared to a mechanism that is allowed to set
different prices for different servers.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Goel:2019:KVP,
author = "Ashish Goel and Anilesh K. Krishnaswamy and Sukolsak
Sakshuwong and Tanja Aitamurto",
title = "Knapsack Voting for Participatory Budgeting",
journal = j-TEAC,
volume = "7",
number = "2",
pages = "8:1--8:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3340230",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:47 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3340230",
abstract = "We address the question of aggregating the preferences
of voters in the context of participatory budgeting. We
scrutinize the voting method currently used in
practice, underline its drawbacks, and introduce a
novel scheme tailored to this setting, which we call
``Knapsack Voting.'' We study its strategic
properties-we show that it is strategy-proof under a
natural model of utility (a dis-utility given by the
l$_1$ distance between the outcome and the true
preference of the voter) and ``partially''
strategy-proof under general additive utilities. We
extend Knapsack Voting to more general settings with
revenues, deficits, or surpluses and prove a similar
strategy-proofness result. To further demonstrate the
applicability of our scheme, we discuss its
implementation on the digital voting platform that we
have deployed in partnership with the local government
bodies in many cities across the nation. From voting
data thus collected, we present empirical evidence that
Knapsack Voting works well in practice.",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Halpern:2019:SEC,
author = "Joseph Y. Halpern and Rafael Pass",
title = "Sequential Equilibrium in Computational Games",
journal = j-TEAC,
volume = "7",
number = "2",
pages = "9:1--9:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3340232",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:47 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3340232",
abstract = "We examine sequential equilibrium in the context of
computational games (Halpern and Pass 2015), where
agents are charged for computation. In such games, an
agent can rationally choose to forget, so issues of
imperfect recall arise. In this setting, we consider
two notions of sequential equilibrium. One is an ex
ante notion, where a player chooses his strategy before
the game starts and is committed to it, but chooses it
in such a way that it remains optimal even off the
equilibrium path. The second is an interim notion,
where a player can reconsider at each information set
whether he is doing the ``right'' thing, and if not,
can change his strategy. The two notions agree in games
of perfect recall, but not in games of imperfect
recall. Although the interim notion seems more
appealing, in a companion article (Halpern and Pass
2016), we argue that there are some deep conceptual
problems with it in standard games of imperfect recall.
We show that the conceptual problems largely disappear
in the computational setting. Moreover, in this
setting, under natural assumptions, the two notions
coincide.",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Bei:2019:EUL,
author = "Xiaohui Bei and Jugal Garg and Martin Hoefer and Kurt
Mehlhorn",
title = "Earning and Utility Limits in {Fisher} Markets",
journal = j-TEAC,
volume = "7",
number = "2",
pages = "10:1--10:??",
month = aug,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3340234",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:47 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3340234",
abstract = "Earning limits and utility limits are novel aspects in
the classic Fisher market model. Sellers with earning
limits have bounds on their income and lower the supply
they bring to the market if income exceeds the limit.
Buyers with utility limits have an upper bound on the
amount of utility that they want to derive and lower
the budget they bring to the market if utility exceeds
the limit. Markets with these properties can have
multiple equilibria with different characteristics. We
analyze earning limits and utility limits in markets
with linear and spending-constraint utilities. For
markets with earning limits and spending-constraint
utilities, we show that equilibrium price vectors form
a lattice and the spending of buyers is unique in
non-degenerate markets. We provide a scaling-based
algorithm to compute an equilibrium in time O (n$^3$ l
log (l + nU)), where n is the number of agents, l
{$>$}= n a bound on the segments in the utility
functions, and U the largest integer in the market
representation. We show how to refine any equilibrium
in polynomial time to one with minimal prices or one
with maximal prices (if it exists). Moreover, our
algorithm can be used to obtain in polynomial time a
2-approximation for maximizing Nash social welfare in
multi-unit markets with indivisible items that come in
multiple copies. For markets with utility limits and
linear utilities, we show similar results-lattice
structure of price vectors, uniqueness of allocation in
non-degenerate markets, and polynomial-time refinement
procedures to obtain equilibria with minimal and
maximal prices. We complement these positive results
with hardness results for related computational
questions. We prove that it is NP-hard to compute a
market equilibrium that maximizes social welfare, and
it is PPAD-hard to find any market equilibrium with
utility functions with separate satiation points for
each buyer and each good.",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Chen:2019:ISI,
author = "Yiling Chen and Dirk Bergemann",
title = "Introduction to the Special Issue on {EC'16}",
journal = j-TEAC,
volume = "7",
number = "3",
pages = "11:1--11:??",
month = oct,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3357235",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:47 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3357235",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Caragiannis:2019:UFM,
author = "Ioannis Caragiannis and David Kurokawa and Herv{\'e}
Moulin and Ariel D. Procaccia and Nisarg Shah and
Junxing Wang",
title = "The Unreasonable Fairness of Maximum {Nash} Welfare",
journal = j-TEAC,
volume = "7",
number = "3",
pages = "12:1--12:??",
month = oct,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3355902",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:47 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3355902",
abstract = "The maximum Nash welfare (MNW) solution-which selects
an allocation that maximizes the product of
utilities-is known to provide outstanding fairness
guarantees when allocating divisible goods. And while
it seems to lose its luster when applied to indivisible
goods, we show that, in fact, the MNW solution is
strikingly fair even in that setting. In particular, we
prove that it selects allocations that are envy-free up
to one good-a compelling notion that is quite elusive
when coupled with economic efficiency. We also
establish that the MNW solution provides a good
approximation to another popular (yet possibly
infeasible) fairness property, the maximin share
guarantee, in theory and-even more so-in practice.
While finding the MNW solution is computationally hard,
we develop a nontrivial implementation and demonstrate
that it scales well on real data. These results
establish MNW as a compelling solution for allocating
indivisible goods and underlie its deployment on a
popular fair-division website.",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Epstein:2019:GBU,
author = "Ziv Epstein and Alexander Peysakhovich and David
Rand",
title = "The Good, the Bad, and the Unflinchingly Selfish:
Pro-sociality can be Well Predicted Using Payoffs and
Three Behavioral Types",
journal = j-TEAC,
volume = "7",
number = "3",
pages = "13:1--13:??",
month = oct,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3355947",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:47 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3355947",
abstract = "The human willingness to pay costs to benefit
anonymous others is often explained by social
preferences: rather than only valuing their own
material payoff, people also include the payoffs of
others in their utility function. But how successful is
this concept of outcome-based social preferences for
actually predicting out-of-sample behavior? We
investigate this question by having 1,067 participants
each make 20 Dictator Game decisions with randomized
parameters (e.g., outcomes for the self, for the other,
benefit/cost ratio of pro-sociality). We then use
machine learning to try to predict behavior by each
participant in each decision. A representative agent
model (a small, shared, set of parameters) predicts
better than random but still quite poorly (AUC = 0.69).
Allowing for full heterogeneity across individuals in
the mapping from decision-parameters to outcome yields
good predictive performance (AUC = 0.89). However, this
heterogeneous model is complicated and unwieldy, thus
we also investigate whether a simpler model can yield
similar performance. We find that the vast majority of
the predictive power (AUC = 0.88) is achieved by a
model that allows for three behavioral types. Finally,
we show that cannot be well proxied for by other
measures in psychology. This final analysis adds
further evidence to the literature that human
``cooperative phenotypes'' are indeed meaningful,
relatively orthogonal person-level traits.",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Alon:2019:DES,
author = "Noga Alon and Michal Feldman and Yishay Mansour and
Sigal Oren and Moshe Tennenholtz",
title = "Dynamics of Evolving Social Groups",
journal = j-TEAC,
volume = "7",
number = "3",
pages = "14:1--14:??",
month = oct,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3355948",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:47 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3355948",
abstract = "Exclusive social groups are ones in which the group
members decide whether or not to admit a candidate to
the group. Examples of exclusive social groups include
academic departments and fraternal organizations. In
this article, we introduce an analytic framework for
studying the dynamics of exclusive social groups. In
our model, every group member is characterized by his
opinion, which is represented as a point on the real
line. The group evolves in discrete time steps through
a voting process carried out by the group's members.
Due to homophily, each member votes for the candidate
who is more similar to him (i.e., closer to him on the
line). An admission rule is then applied to determine
which candidate, if any, is admitted. We consider
several natural admission rules including majority and
consensus. We ask: How do different admission rules
affect the composition of the group in the long run? We
study both growing groups (where new members join old
ones) and fixed-size groups (where new members replace
those who quit). Our analysis reveals intriguing
phenomena and phase transitions, some of which are
quite counterintuitive.",
acknowledgement = ack-nhfb,
articleno = "14",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Bilo:2019:DTP,
author = "Vittorio Bil{\`o} and Cosimo Vinci",
title = "Dynamic Taxes for Polynomial Congestion Games",
journal = j-TEAC,
volume = "7",
number = "3",
pages = "15:1--15:??",
month = oct,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3355946",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:47 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3355946",
abstract = "We consider the efficiency of taxation in congestion
games with polynomial latency functions along the line
of research initiated by Caragiannis et al. [ ACM
Transactions on Algorithms, 2010], who focused on both
pure and mixed Nash equilibria in games with affine
latencies only. By exploiting the primal-dual method
[Bil{\`o}, Proceedings of the 10th Workshop on
Approximation and Online Algorithms, 2012], we obtain
interesting upper bounds with respect to a variety of
different solution concepts ranging from approximate
pure Nash equilibria up to approximate coarse
correlated equilibria, and including also approximate
one-round walks starting from the empty state. Our
findings show a high beneficial effect of taxation that
increases more than linearly with the degree of the
latency functions. In some cases, a tight relationship
with some well-studied polynomials in Combinatorics and
Number Theory, such as the Touchard and the Geometric
polynomials, arises. In these cases, we can also show
matching lower bounds, albeit under mild assumptions;
interestingly, our upper bounds are derived by
exploiting the combinatorial definition of these
polynomials, while our lower bounds are constructed by
relying on their analytical characterization.",
acknowledgement = ack-nhfb,
articleno = "15",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Assadi:2019:SMP,
author = "Sepehr Assadi and Sanjeev Khanna and Yang Li",
title = "The Stochastic Matching Problem with (Very) Few
Queries",
journal = j-TEAC,
volume = "7",
number = "3",
pages = "16:1--16:??",
month = oct,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3355903",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:47 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3355903",
abstract = "Motivated by an application in kidney exchange, we
study the following stochastic matching problem: We are
given a graph G (V, E) (not necessarily bipartite),
where each edge in E is realized with some constant
probability p \> 0, and the goal is to find a
maximum matching in the realized graph. An algorithm in
this setting is allowed to make queries to edges in E
to determine whether or not they are realized. We
design an adaptive algorithm for this problem that, for
any graph G, computes a (1- \epsilon)-approximate
maximum matching in the realized graph G$_p$ with high
probability, while making O (log (1/ \epsilon p)/
\epsilon p) queries per vertex, where the edges to
query are chosen adaptively in O (log (1/ \epsilon p)/
\epsilon p) rounds. We further present a non-adaptive
algorithm that makes O (log (1/ \epsilon p)/ \epsilon
p) queries per vertex and computes a (1/2-
\epsilon)-approximate maximum matching in G$_p$ with
high probability. Both our adaptive and non-adaptive
algorithms achieve the same approximation factor as the
previous best algorithms of Blum et al. (EC 2015) for
this problem, while requiring an exponentially smaller
number of per-vertex queries (and rounds of adaptive
queries for the adaptive algorithm). Our results settle
an open problem raised by Blum et al. by achieving only
a polynomial dependency on both \epsilon and p.
Moreover, the approximation guarantee of our algorithms
is instance-wise as opposed to only being competitive
in expectation as is the case for Blum et al. This is
of particular relevance to the key application of
stochastic matching in kidney exchange. We obtain our
results via two main techniques-namely, matching-covers
and vertex sparsification -that may be of independent
interest.",
acknowledgement = ack-nhfb,
articleno = "16",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Roughgarden:2019:MRM,
author = "Tim Roughgarden and Joshua R. Wang",
title = "Minimizing Regret with Multiple Reserves",
journal = j-TEAC,
volume = "7",
number = "3",
pages = "17:1--17:??",
month = oct,
year = "2019",
CODEN = "????",
DOI = "https://doi.org/10.1145/3355900",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Sat Oct 19 12:38:47 MDT 2019",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/ft_gateway.cfm?id=3355900",
abstract = "We study the problem of computing and learning
non-anonymous reserve prices to maximize revenue. We
first define the Maximizing Multiple Reserves (MMR)
problem in single-parameter matroid environments, where
the input is m valuation profiles v$^1$,..., v$^m$,
indexed by the same n bidders, and the goal is to
compute the vector r of (non-anonymous) reserve prices
that maximizes the total revenue obtained on these
profiles by the VCG mechanism with reserves r. We prove
that the problem is APX-hard, even in the special case
of single-item environments, and give a polynomial-time
1/2-approximation algorithm for it in arbitrary matroid
environments. We then consider the online no-regret
learning problem and show how to exploit the special
structure of the MMR problem to translate our offline
approximation algorithm into an online learning
algorithm that achieves asymptotically time-averaged
revenue at least 1/2 times that of the best fixed
reserve prices in hindsight. On the negative side, we
show that, quite generally, computational hardness for
the offline optimization problem translates to
computational hardness for obtaining vanishing
time-averaged regret. Thus, our hardness result for the
MMR problem implies that computationally efficient
online learning requires approximation, even in the
special case of single-item auction environments.",
acknowledgement = ack-nhfb,
articleno = "17",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "http://dl.acm.org/citation.cfm?id=2542174",
}
@Article{Hart:2020:BHS,
author = "Sergiu Hart and Philip J. Reny",
title = "The Better Half of Selling Separately",
journal = j-TEAC,
volume = "7",
number = "4",
pages = "18:1--18:18",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3369927",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Feb 3 08:53:37 MST 2020",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/doi/abs/10.1145/3369927",
abstract = "Separate selling of two independent goods is shown to
yield at least 62% of the optimal revenue, and at least
73% when the goods satisfy the Myerson regularity
condition. This improves the 50% result of Hart and
Nisan [2017, originally circulated in \ldots{}",
acknowledgement = ack-nhfb,
articleno = "18",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "https://dl.acm.org/loi/teac",
}
@Article{Ahuja:2020:DMA,
author = "Kartik Ahuja and Mihaela {Van der Schaar}",
title = "Dynamic Matching and Allocation of Tasks",
journal = j-TEAC,
volume = "7",
number = "4",
pages = "19:1--19:27",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3369925",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Feb 3 08:53:37 MST 2020",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/doi/abs/10.1145/3369925",
abstract = "In many two-sided markets, the parties to be matched
have incomplete information about their
characteristics. We consider the settings where the
parties engaged are extremely patient and are
interested in long-term partnerships. Hence, once the
final \ldots{}",
acknowledgement = ack-nhfb,
articleno = "19",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "https://dl.acm.org/loi/teac",
}
@Article{Ezra:2020:PMU,
author = "Tomer Ezra and Michal Feldman and Tim Roughgarden and
Warut Suksompong",
title = "Pricing Multi-Unit Markets",
journal = j-TEAC,
volume = "7",
number = "4",
pages = "20:1--20:29",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3373715",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Feb 3 08:53:37 MST 2020",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/doi/abs/10.1145/3373715",
abstract = "We study the power and limitations of posted prices in
multi-unit markets, where agents arrive sequentially in
an arbitrary order. We prove upper and lower bounds on
the largest fraction of the optimal social welfare that
can be guaranteed with posted \ldots{}",
acknowledgement = ack-nhfb,
articleno = "20",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "https://dl.acm.org/loi/teac",
}
@Article{Kawase:2020:SPE,
author = "Yasushi Kawase and Yutaro Yamaguchi and Yu Yokoi",
title = "Subgame Perfect Equilibria of Sequential Matching
Games",
journal = j-TEAC,
volume = "7",
number = "4",
pages = "21:1--21:30",
month = feb,
year = "2020",
CODEN = "????",
DOI = "https://doi.org/10.1145/3373717",
ISSN = "2167-8375 (print), 2167-8383 (electronic)",
ISSN-L = "1539-9087",
bibdate = "Mon Feb 3 08:53:37 MST 2020",
bibsource = "http://www.math.utah.edu/pub/tex/bib/teac.bib",
URL = "https://dl.acm.org/doi/abs/10.1145/3373717",
abstract = "We study a decentralized matching market in which
firms sequentially make offers to potential
workers. For each offer, the worker can choose
``accept'' or ``reject,'' but the decision is
irrevocable. The acceptance of an offer guarantees her
job at the firm,. \ldots{}",
acknowledgement = ack-nhfb,
articleno = "21",
fjournal = "ACM Transactions on Economics and Computation",
journal-URL = "https://dl.acm.org/loi/teac",
}