Article

Free access

On complexity as bounded rationality (extended abstract)

Authors:

Christos H. Papadimitriou,

Mihalis YannakakisAuthors Info & Claims

STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing

Pages 726 - 733

https://doi.org/10.1145/195058.195445

Published: 23 May 1994 Publication History

PDF eReader

References

[1]

R. J. humann, S. Hart (editors) Handbook of Game Theory with Economic Applications, vol. I, North-Holland, 1992.

Google Scholar

[2]

R. Axelrod The Evolution of Cooperation, Basic Books, 1984.

Google Scholar

[3]

E. Ben-Porath "The complexity of computing a best response automaton in repeated games with mixed strategies," Games and Economzc Behavior 2, pp. 1-12, 1990.

Crossref

Google Scholar

[4]

X. Deng, C. H. Papadimitriou "Tile complexity of solution concepts," Math. of O.R., to appear.

Digital Library

Google Scholar

[5]

L. Fortnow, D. Whang "Optimality and domination in repeated games with bounded players," manuscript, 1993.

Google Scholar

[6]

I. Gilboa, E. Kalai, E. Zemel "The complexity of eliminating dominated strategies,':' Math. of O.R. 18, pp. 553-565, 1993.

Digital Library

Google Scholar

[7]

I. Gilboa, E. Zemel "Nash and correlated equilibria some complexity considerations," Games and Economic Behavior 1, pp. 80-93, 1{989.

Crossref

Google Scholar

[8]

D. Koller, N. Megiddo "The complexity of twoperson zero-sum games in extensive form," 1990.

Google Scholar

[9]

N. Megiddo, A. Wigderson "On play by means of computing machines," Proc. 1st Conf. on Theor. Aspects of Reasoning About Knowledge, pp. 259- 274, 1986.

Digital Library

Google Scholar

[10]

A. Neyman "Bounded complexity justifies cooperation in the finitely repeated prisoners' dilemma," Economics Letters 19, pp. 227-229, 1985.

Crossref

Google Scholar

[11]

C. H. Papadimitriou "On players with a bounded number of states," Games and Economic Behavior, 1992.

Google Scholar

[12]

A. Rubinstein "Finite automata play the repeated prisoner's dilemma," J. Econ. Theory, 1986.

Crossref

Google Scholar

[13]

S. Sahni "Computationally related problems," SIAM J. Computing 3, pp. 262-279, 1974.

Crossref

Google Scholar

[14]

H. Simon The Sciences of the Artificial, 1969.

Digital Library

Google Scholar

[15]

S. Sorin "Repeated games with complete information," Chapter 4 in {AH}, 1992.

Google Scholar

Cited By

View all

Gurushankar KGrover P(2024)A Minimal Intervention Definition of Reverse Engineering a Neural Circuit2024 IEEE International Symposium on Information Theory Workshops (ISIT-W)10.1109/ISIT-W61686.2024.10591757(1-9)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT-W61686.2024.10591757
Raju DBakirtzis GTopcu UAgmon NAn BRicci AYeoh W(2023)Memoryless Adversaries in Imperfect Information GamesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598940(2379-2381)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598940
Magen RNaor M(2023)Mirror games against an open book playerTheoretical Computer Science10.1016/j.tcs.2023.114159976:COnline publication date: 17-Oct-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.114159
Show More Cited By

Index Terms

On complexity as bounded rationality (extended abstract)
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Formal languages and automata theory

Recommendations

Bounded Rationality in Service Systems

The traditional operations management and queueing literature typically assumes that customers are fully rational. In contrast, in this paper we study canonical service models with boundedly rational customers. We capture bounded rationality using a ...
Combinatorial auction across independent markets [Extended Abstract]
EC '03: Proceedings of the 4th ACM conference on Electronic commerce

In this paper, we study several issues involved in combinatorial auction across independent markets for individual goods. (i) We establish the complexity for the existence of Walrasian equilibrium of combinatorial auction. (ii) We consider incentive ...
Bounded Relativization
CCC '23: Proceedings of the conference on Proceedings of the 38th Computational Complexity Conference

Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called bounded relativization. For a complexity ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing

May 1994

822 pages

ISBN:0897916638

DOI:10.1145/195058

Chairmen:
F. Tom Leighton
Massachusetts Institue of Technology, Cambridge
,
Michael Goodrich
Johns Hopkins Univ., Baltimore, MD

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC94

Sponsor:

SIGACT

STOC94: Symposium on Theory of Computing

May 23 - 25, 1994

Quebec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

68
Total Citations
View Citations
1,614
Total Downloads

Downloads (Last 12 months)159
Downloads (Last 6 weeks)25

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gurushankar KGrover P(2024)A Minimal Intervention Definition of Reverse Engineering a Neural Circuit2024 IEEE International Symposium on Information Theory Workshops (ISIT-W)10.1109/ISIT-W61686.2024.10591757(1-9)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT-W61686.2024.10591757
Raju DBakirtzis GTopcu UAgmon NAn BRicci AYeoh W(2023)Memoryless Adversaries in Imperfect Information GamesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598940(2379-2381)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598940
Magen RNaor M(2023)Mirror games against an open book playerTheoretical Computer Science10.1016/j.tcs.2023.114159976:COnline publication date: 17-Oct-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.114159
Skyrms B(2022)The Social Contract, the Game of Life and the Shadow of the FutureHomo Oeconomicus10.1007/s41412-022-00119-6Online publication date: 1-Mar-2022
https://doi.org/10.1007/s41412-022-00119-6
Yang YJia KRinard M(2022)On the Impact of Player Capability on Congestion GamesAlgorithmic Game Theory10.1007/978-3-031-15714-1_18(311-328)Online publication date: 14-Sep-2022
https://doi.org/10.1007/978-3-031-15714-1_18
Raju DEhlers RTopcu U(2021)Adapting to the Behavior of Environments with Bounded MemoryElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.346.4346(52-66)Online publication date: 16-Sep-2021
https://doi.org/10.4204/EPTCS.346.4
Bilò VFlammini MMoscardelli L(2021)On Nash Equilibria in Non-Cooperative All-Optical NetworksAlgorithms10.3390/a1401001514:1(15)Online publication date: 9-Jan-2021
https://doi.org/10.3390/a14010015
Haghtalab NJackson MProcaccia A(2021)Belief polarization in a complex world: A learning theory perspectiveProceedings of the National Academy of Sciences10.1073/pnas.2010144118118:19Online publication date: 3-May-2021
https://doi.org/10.1073/pnas.2010144118
Ajayakumar JShook E(2020)Leveraging parallel spatio-temporal computing for crime analysis in large datasets: analyzing trends in near-repeat phenomenon of crime in citiesInternational Journal of Geographical Information Science10.1080/13658816.2020.1732393(1-25)Online publication date: 2-Mar-2020
https://doi.org/10.1080/13658816.2020.1732393
Deuser KNaumov P(2020)Navigability with bounded recall autonomous agents with bounded memory autonomous agents with bounded recall working memory of autonomous agents on composition of bounded-recall plansArtificial Intelligence10.1016/j.artint.2020.103399(103399)Online publication date: Oct-2020
https://doi.org/10.1016/j.artint.2020.103399
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Bounded Rationality in Service Systems

Combinatorial auction across independent markets [Extended Abstract]

Bounded Relativization