Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions

Details Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions

2009-09-30

arxiv.org/abs/0909.5677v1

Computer Science

Computer Science and Game Theory

16 pages, 0 figures

Scientific paper

We study the design of mechanisms in combinatorial auction domains. We focus on settings where the auction is repeated, motivated by auctions for licenses or advertising space. We consider models of agent behaviour in which they either apply common learning techniques to minimize the regret of their bidding strategies, or apply short-sighted best-response strategies. We ask: when can a black-box approximation algorithm for the base auction problem be converted into a mechanism that approximately preserves the original algorithm's approximation factor on average over many iterations? We present a general reduction for a broad class of algorithms when agents minimize external regret. We also present a new mechanism for the combinatorial auction problem that attains an $O(\sqrt{m})$ approximation on average when agents apply best-response dynamics.

Affiliated with

Also associated with

No associations

Rating

Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-590569