Article

The Clarke tax as a consensus mechanism among automated agents

Authors:

Eithan Ephrati,

Jeffrey S. RosenscheinAuthors Info & Claims

AAAI'91: Proceedings of the ninth National conference on Artificial intelligence - Volume 1

Pages 173 - 178

Published: 14 July 1991 Publication History

Abstract

When autonomous agents attempt to coordinate action, it is often necessary that they reach some kind of consensus. Reaching such a consensus has traditionally been dealt with in the Distributed Artificial Intelligence literature via the mechanism of negotiation. Another alternative is to have agents bypass negotiation by using a voting mechanism; each agent expresses its preferences, and a group choice mechanism is used to select the result. Some choice mechanisms are better than others, and ideally we would like one that. cannot be manipulated by an untruthful agent.

One such non-manipulable choice mechanism is the Clarke tax [Clarke, 1971]. Though theoretically attractive, the Clarke tax presents a number of difficulties when one attempts to use it in a practical implementation. This paper examines how the Clarke tax could be used as an effective "preference revealer" in the domain of automated agents, reducing the need for explicit negotiation.

References

[1]

Arrow, K. J. 1963. Social Choice and Individual Values. John Wiley, New York. First published in 1951.

[2]

Clarke, E. H. 1971. Multipart pricing of public goods. Public Choice 11:17-33.

[3]

Clarke, E. H. 1972. Multipart pricing of public goods: An example. In Muskin, S., editor, Public Prices for Public Products. Urban Inst., Washington.

[4]

Conry, S. E.; Meyer, R. A.; and Lesser, V. R. 1988. Multistage negotiation in distributed planning. In Bond, Alan H. and Gasser, Les, editors, Readings in Distributed Artificial Intelligence. Morgan Kaufmann Publishers, San Mateo, California. 367-384.

[5]

Dubins, L. 1977. Group decision devices. American Mathematical Monthly 84:350-356.

[6]

Durfee, E. H. 1988. Coordination of Distributed Problem Solvers. Kluwer Academic Publishers, Boston.

[7]

Ephrati, Eithan and Rosenschein, Jeffrey, S. 1991. Voting and multi-agent consensus. Technical. report, Computer Science Department, Hebrew University, Jerusalem, Israel. In preparation.

[8]

Gibbard, A. 1973. Manipulation of voting schemes: a general result. Econometrica 41:587-602.

[9]

Kraus, S. and Wilkenfeld, J. 1990. The function of time in cooperative negotiations: Extended abstract. In Proceedings of the Tenth Workshop on Distributed Artificial Intelligence, Bandera, Texas.

[10]

Kreifelts, Thomas and von Martial, Frank 1990. A negotiation framework for autonomous agents. In Proceedings of the Second European Workshop on Modeling Autonomous Agents in a Multi-Agent World, Saint-Quentin en Yvelines, France. 169-182.

[11]

Kuwabara, Kazuhiro and Lesser, Victor R. 1989. Extended protocol for multistage negotiation" In Proceedings of the Ninth Workshop on Distributed Artificial Intelligence, Rosario, Washington. 129-161.

[12]

Laasri, Brigitte; Laasri, Hassan; and Lesser, Victor R. 1990. Negotiation and its role in cooperative distributed problem solving. In Proceedings of the Tenth International Workshop on Distributed Artificial Intelligence, Bandera, Texas.

[13]

Malone, T. W.; Fikes, R. E.; and Howard, M. T. 1988. Enterprise: A market-like task scheduler for distributed computing environments. In Huberman, B. A., editor, The Ecology of Computation. North-Holland Publishing Company, Amsterdam. 177-205.

[14]

Miller, M. S. and Drexler, K. E. 1988. Markets and computation: Agoric open systems. In Huberman, B. A., editor, The Ecology of Computation. North-Holland Publishing Company, Amsterdam, 133-176.

[15]

Rosenschein, Jeffrey S. and Genesereth, Michael R. 1985. Deals among rational agents. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence, Los Angeles, California. 91-99.

[16]

Satterthwaite, N. A. 1975. Strategy-proofness and Arrow's conditions: existence and social welfare functions. Journal of Economic Theory 10:187-217.

[17]

Smith, Reid G. 1978. A Framework for Problem Solving in a Distributed Processing Environment. Ph.D. Dissertation, Stanford University.

[18]

Straffin, Philip D. Jr. 1980. Topics in the Theory of Voting. The UMAP Expository Monograph Series. Birkhäuser, Boston.

[19]

Sycara, Katia P. 1988. Resolving goal conflicts via negotiation. In Proceedings of the Seventh National Conference on Artificial Intelligence, St. Paul, Minnesota. 245-250.

[20]

Zlotkin, Gilad and Rosenschein, Jeffrey S. 1990a. Negotiation and conflict resolution in non-cooperative domains. In Proceedings of The National Conference on Artificial Intelligence, Boston, Massachusetts. 100-105.

[21]

Zlotkin Gilad and Rosenschein, Jeffrey S. 1990b. Negotiation and goal relaxation. In Proceedings of The Workshop on Modelling Autonomous Agents in a Multi-Agent World, Saint-Quentin en Yvelines, France. Office National D'Etudes et de Recherches Aerospatiales. 115-132.

Cited By

Ulusoy OYolum P(2021)PANOLA: A Personal Assistant for Supporting Users in Preserving PrivacyACM Transactions on Internet Technology10.1145/347118722:1(1-32)Online publication date: 14-Sep-2021
https://dl.acm.org/doi/10.1145/3471187
Ulusoy OYolum PAndre EKoenig SDastani MSukthankar G(2018)PANOProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3238086(2103-2105)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3238086
Ulusoy OAndre EKoenig SDastani MSukthankar G(2018)Collaborative Privacy Management in Online Social NetworksProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237977(1788-1790)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237977
Show More Cited By

The Clarke tax as a consensus mechanism among automated agents
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence

Recommendations

Continuous-Time Negotiation Mechanism for Software Agents

While there are several existing mechanisms and systems addressing the crucial and difficult issues of automated one-to-many negotiation, this paper develops a flexible one-to-many negotiation mechanism for software agents. Unlike the existing general ...
Concurrent Negotiation among Capable Agents
ICNC '09: Proceedings of the 2009 Fifth International Conference on Natural Computation - Volume 05

Negotiation is one of agent’s key social abilities and an effective approach for multi-agent systems to achieve their targets. For efficiency concern, negotiation should occur among only those with target-related expertise and it should be concurrent. ...
Intelligent agents for automated one-to-many e-commerce negotiation

Negotiation is a process in which two or more parties with different criteria, constraints, and preferences, jointly reach an agreement on the terms of a transaction. Many current automated negotiation systems support one-to-one negotiation. One-to-many ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

AAAI'91: Proceedings of the ninth National conference on Artificial intelligence - Volume 1

July 1991

931 pages

ISBN:0262510596

Sponsors

AAAI: American Association for Artificial Intelligence

Publisher

AAAI Press

Publication History

Published: 14 July 1991

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ulusoy OYolum P(2021)PANOLA: A Personal Assistant for Supporting Users in Preserving PrivacyACM Transactions on Internet Technology10.1145/347118722:1(1-32)Online publication date: 14-Sep-2021
https://dl.acm.org/doi/10.1145/3471187
Ulusoy OYolum PAndre EKoenig SDastani MSukthankar G(2018)PANOProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3238086(2103-2105)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3238086
Ulusoy OAndre EKoenig SDastani MSukthankar G(2018)Collaborative Privacy Management in Online Social NetworksProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237977(1788-1790)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237977
Xiao MWang Y(2017)Score aggregation via spectral methodProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171642.3171707(451-457)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171642.3171707
Dey PMisra NNarahari Y(2016)Kernelization complexity of possible winner and coalitional manipulation problems in votingTheoretical Computer Science10.1016/j.tcs.2015.12.023616:C(111-125)Online publication date: 22-Feb-2016
https://dl.acm.org/doi/10.1016/j.tcs.2015.12.023
Dey PBhattacharyya AWeiss GYolum PBordini RElkind E(2015)Sample Complexity for Winner Prediction in ElectionsProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2773334(1421-1430)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2773334
Dey PMisra NNarahari YWeiss GYolum PBordini RElkind E(2015)Kernelization Complexity of Possible Winner and Coalitional Manipulation Problems in VotingProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2772894(87-96)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2772894
Pei Y(2015)Algorithmic mechanism design of evolutionary computationComputational Intelligence and Neuroscience10.1155/2015/5919542015(64-64)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1155/2015/591954
Xia LGini MShehory OIto TJonker C(2013)Designing social choice mechanisms using machine learningProceedings of the 2013 international conference on Autonomous agents and multi-agent systems10.5555/2484920.2484995(471-474)Online publication date: 6-May-2013
https://dl.acm.org/doi/10.5555/2484920.2484995
Perek TFaliszewski PPini MRossi FGini MShehory OIto TJonker C(2013)The complexity of losing votersProceedings of the 2013 international conference on Autonomous agents and multi-agent systems10.5555/2484920.2484986(407-414)Online publication date: 6-May-2013
https://dl.acm.org/doi/10.5555/2484920.2484986
Show More Cited By

View Options

View options

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents