abstract

Incentive-compatible distributed greedy protocols

Authors:

Noam Nisan,

Michael Schapira,

Gregory Valiant,

Aviv ZoharAuthors Info & Claims

PODC '11: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing

Pages 335 - 336

https://doi.org/10.1145/1993806.1993871

Published: 06 June 2011 Publication History

Get Access

Abstract

Under many distributed protocols, the prescribed behavior for participants is to behave greedily, i.e., to repeatedly "best respond" to the others' actions. We present recent work (Proc. ICS'11) where we tackle the following general question: "When is it best for a long-sighted participant to adhere to a distributed greedy protocol?". We take a game-theoretic approach and exhibit a class of games where greedy behavior (i.e., repeated best-response) is incentive compatible for all players. We identify several environments of interest that fall within this class, thus establishing the incentive compatibility of the natural distributed greedy protocol for each. These environments include models of the Border Gateway Protocol (BGP) [4], which handles routing on the Internet, and of the Transmission Control Protocol (TCP) [3], and also stable-roommates assignments [2] and cost-sharing [5], which have been extensively studied in economic theory.

References

[1]

Joan Feigenbaum, Michael Schapira, and Scott Shenker. Distributed Algorithmic Mechanism Design. "Algorithmic Game Theory", Chapter 14. Cambridge University Press, 2007.

Google Scholar

[2]

David Gale and Lloyd S. Shapley. College admissions and stability of marriage. Amer. Math. Monthly, (69):9--15, 1962.

Google Scholar

[3]

P. Brighten Godfrey, Michael Schapira, Aviv Zohar, and Scott Shenker. Incentive compatibility and dynamics of congestion control. SIGMETRICS Perform. Eval. Rev., 38(1):95--106, 2010.

Digital Library

Google Scholar

[4]

Hagay Levin, Michael Schapira, and Aviv Zohar. Interdomain routing and games. In STOC, pages 57--66, 2008.

Digital Library

Google Scholar

[5]

Herve Moulin. Incremental cost sharing: Characterization by coalition strategy-proofness. Social Choice and Welfare, 16(2):279--320, 1999.

Crossref

Google Scholar

[6]

Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1):166--196, 2001.

Crossref

Google Scholar

[7]

Noam Nisan, Michael Schapira, Gregory Valiant, and Aviv Zohar. Best-response mechanisms. In ICS '11: Proceedings of the 2nd symposium on Innovations in Computer Science, 2011.

Google Scholar

Index Terms

Incentive-compatible distributed greedy protocols
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

Incentive compatible budget elicitation in multi-unit auctions
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms

In this paper, we consider the problem of designing incentive compatible auctions for multiple (homogeneous) units of a good, when bidders have private valuations and private budget constraints. When only the valuations are private and the budgets are ...
Incentive-Compatible Learning of Reserve Prices for Repeated Auctions
How can an auctioneer optimize revenue by learning the reserve prices from the bids in the previous auctions? How should the long-term incentives and strategic behavior of the bidders be taken into account? Motivated in part by applications in online ...
Large fractions of online advertisements are sold via repeated second-price auctions. In these auctions, the reserve price is the main tool for the auctioneer to boost revenues. In this work, we investigate the following question: how can the auctioneer ...
Incentive-Compatible Learning of Reserve Prices for Repeated Auctions
WWW '19: Companion Proceedings of The 2019 World Wide Web Conference

Motivated by online advertising market, we consider a seller who repeatedly sells ex ante identical items via the second-price auction. Buyers’ valuations for each item are drawn i.i.d. from a distribution F that is unknown to the seller. We find that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '11: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing

June 2011

406 pages

ISBN:9781450307192

DOI:10.1145/1993806

General Chair:
Cyril Gavoille
LaBRI, University of Bordeaux, France
,
Program Chair:
Pierre Fraigniaud
CNRS and University of Paris Diderot, France

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Abstract

Conference

PODC '11

Sponsor:

PODC '11: ACM Symposium on Principles of Distributed Computing

June 6 - 8, 2011

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
113
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Index Terms

Recommendations

Incentive compatible budget elicitation in multi-unit auctions

Incentive-Compatible Learning of Reserve Prices for Repeated Auctions

Incentive-Compatible Learning of Reserve Prices for Repeated Auctions