ACM DL

Economics and Computation (TEAC)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Economics and Computation - Special Issue on Algorithmic Game Theory, Volume 1 Issue 2, May 2013

Introduction to the Special Issue on Algorithmic Game Theory
Michal Feldman, Noam Nisan
Article No.: 5
DOI: 10.1145/2465769.2465770

Network Formation in the Presence of Contagious Risk
Lawrence Blume, David Easley, Jon Kleinberg, Robert Kleinberg, Éva Tardos
Article No.: 6
DOI: 10.1145/2465769.2465771

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...

Selling in Exclusive Markets: Some Observations on Prior-Free Mechanism Design
Anna R. Karlin, C. Thach Nguyen, Yuval Peres
Article No.: 7
DOI: 10.1145/2465769.2465772

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...

Mechanism Design via Consensus Estimates, Cross Checking, and Profit Extraction
Bach Q. Ha, Jason D. Hartline
Article No.: 8
DOI: 10.1145/2465769.2465773

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...

The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani
Article No.: 9
DOI: 10.1145/2465769.2465774

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...

On the Competitive Ratio of Online Sampling Auctions
Elias Koutsoupias, George Pierrakos
Article No.: 10
DOI: 10.1145/2465769.2465775

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...

Near-Potential Games: Geometry and Dynamics
Ozan Candogan, Asuman Ozdaglar, Pablo A. Parrilo
Article No.: 11
DOI: 10.1145/2465769.2465776

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,...

Efficient Market Making via Convex Optimization, and a Connection to Online Learning
Jacob Abernethy, Yiling Chen, Jennifer Wortman Vaughan
Article No.: 12
DOI: 10.1145/2465769.2465777

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...

Optimal Auctions with Positive Network Externalities
Nima Haghpanah, Nicole Immorlica, Vahab Mirrokni, Kamesh Munagala
Article No.: 13
DOI: 10.1145/2465769.2465778

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...