enter search term and/or author name
Introduction to the Special Issue on Algorithmic Game Theory
Michal Feldman, Noam Nisan
Article No.: 5
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
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
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
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
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...
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
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
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...