New Paper: “Program Equilibrium in the Prisoner’s Dilemma via Löb’s Theorem”

 |   |  News

robust cooperation first pageWe’ve released a new paper recently accepted to the MIPC workshop at AAAI-14: “Program Equilibrium in the Prisoner’s Dilemma via Löb’s Theorem” by LaVictoire et al. This paper is essentially a shortened version of Barasz et al. (2014). For the history of the key results therein, see Robust Cooperation: A Case Study in Friendly AI Research.

Abstract of the new paper:

Applications of game theory often neglect that real-world agents normally have some amount of out-of-band information about each other. We consider the limiting case of a one-shot Prisoner’s Dilemma between algorithms with read access to one anothers’ source code. Previous work has shown that cooperation is possible at a Nash equilibrium in this setting, but existing constructions require interacting agents to be identical or near-identical. We show that a natural class of agents are able to achieve mutual cooperation at Nash equilibrium without any prior coordination of this sort.

 

Christof Koch and Stuart Russell on machine superintelligence

 |   |  News

Recently, Science Friday (hosted by Ira Flatow) featured an interview (page, mp3, transcript) with Christof Koch and Stuart Russell about machine superintelligence. Christof Koch is the Chief Scientific Officer of the Allen Institute for Brain Science, and Stuart Russell is a computer science professor at UC Berkeley, and co-author of the world’s most-used AI textbook.

I was glad to hear both distinguished guests take seriously the opportunities and risks of AGI. Those parts of the conversation are excerpted below:

Read more »

Exponential and non-exponential trends in information technology

 |   |  Analysis

Co-authored with Lila Rieber.

In The Singularity is Near, Ray Kurzweil writes that “every aspect of information and information technology is growing at an exponential pace.”1 In Abundance, the authors list eight fields — including nanomaterials, robotics, and medicine — as “exponentially growing fields.”2 The Second Machine Age says that “technical progress” in general is “improving exponentially.”3

These authors are correct to emphasize that exponential trends in technological development are surprisingly common (Nagy et al. 2013), and that these trends challenge the wisdom of our built-in heuristic to ignore futures that sound absurd. (To someone in the 1980s, the iPhone is absurd. To us, it is an affordable consumer good.)

Unfortunately, these and other popular discussions of “exponential technologies” are often very succinct and therefore ambiguous, resulting in public and professional misunderstanding.4 I (Luke) regularly encounter people who have read the books above and come away with the impression that all information technologies show roughly exponential trends all the time. But this isn’t true unless you have a very broad concept of what counts as “roughly exponential.”

So, without speculating much about what Kurzweil & company intend to claim, we’ll try to clear up some common misunderstandings about exponential technologies by showing a few examples of exponential and not-so-exponential trends in information technology. A more thorough survey of trends in information technology must be left to other investigators.5

Read more »


  1. Page 85. In the same book, he also writes that “we see ongoing exponential growth of every aspect of information technology, including price-performance, capacity, and rate of adoption.” (p. 377). In How to Create a Mind, Kurzweil writes that “In the course of my investigation, I made a startling discovery: If a technology is an information technology, the basic measures of price/performance and capacity… follow amazingly precise exponential trajectories” (p. 254). 
  2. Page 57. In general, Diamandis & Kotler seem to agree with Kurzweil that all information technologies experience exponential growth curves. E.g. on page 99 they write that “Although [some agroecological] practices themselves look decidedly low tech, all the fields they’re informed by are information-based sciences and thus on exponential growth curves,” and on page 190 they write that “almost every component of medicine is now an information technology and therefore on an exponential trajectory.” 
  3. Page 10. The authors also seem to expect exponential trends for anything that becomes a digital process: “…batteries… haven’t improved their performance at an exponential rate because they’re essentially chemical devices, not digital ones…” (p. 52). 
  4. E.g. Kurzweil seems to use a fairly loose definition of “exponential.” For example in Kurzweil (2001) he gives this chart of ISP cost-performance as an example exponential trend. Sometimes this seems to cause confusion in dialogue. For example, in response to Ilkka Tuomi’s criticisms (2002, 2003) of claims of exponential trends in computing, Kurzweil wrote that if Tuomi were correct, “I would have to conclude that the one-quarter MIPS computer costing several million dollars that I used at MIT in 1967 and the 1000 MIPS computer that I purchased recently for $2,000 never really existed… I admire his tenacity in attempting to prove that the world of information technology is flat (i.e., linear).” But Tuomi’s views don’t entail that, and Tuomi didn’t say that trends in information technology have been linear. The conflict appears to stem from the fact that Tuomi was using “exponential” in the strict sense, while Kurzweil was using the term in a very loose sense. This becomes clearer in Tuomi’s reply to Kurzweil
  5. Our thanks to Jonah Sinick for his assistance in researching this post. 

Benjamin Pierce on clean-slate security architectures

 |   |  Conversations

Benjamin C. Pierce portrait Benjamin C. Pierce is Henry Salvatori Professor of Computer and Information Science at the University of Pennsylvania and a Fellow of the ACM. His research interests include programming languages, type systems, language-based security, computer-assisted formal verification, differential privacy, and synchronization technologies. He is the author of the widely used graduate textbooks Types and Programming Languages and Software Foundations.

He has served as co-Editor in Chief of the Journal of Functional Programming, as Managing Editor for Logical Methods in Computer Science, and as editorial board member of Mathematical Structures in Computer ScienceFormal Aspects of Computing, and ACM Transactions on Programming Languages and Systems. He is also the lead designer of the popular Unison file synchronizer.

Luke Muehlhauser: I previously interviewed Greg Morrisett about the SAFE project, and about computer security in general. You’ve also contributed to the SAFE project, gave an “early retrospective” talk on it (slides), and I’d like to ask you some more detailed questions about it.

In particular, I’d like to ask about the “verified information-flow architecture” developed for SAFE. Can you give us an overview of the kinds of information flow security properties you were able to prove about the system?


Benjamin C. Pierce: Sure. First, to remind your readers: SAFE is a clean-slate design of a new hardware / software stack whose goal is to build a network host that is highly resilient to cyber-attack. One pillar of the design is pervasive mechanisms for tracking information flow. The SAFE hardware offers fine-grained tagging and efficient propagation and combination of tags on each instruction dispatch. The operating system virtualizes these generic facilities to provide an “information-flow abstract machine,” on which user programs run.

Formal verification has been part of the SAFE design process right from the beginning. We’d originally hoped to be able to verify the actual running code of the OS in the style of sel4, but we found that the codebase was too big and moving too fast for this to be practical with a small verification team. Instead, we’ve developed a methodology that combines full formal verification of models of the system’s key features with “property-based random testing” (à la QuickCheck) of richer subsets of the system’s functionality.

Our most interesting formal proof so far shows that the key security property of the information-flow abstract machine — the fact that a program’s secret inputs cannot influence its public outputs — is correctly preserved by our implementation on (a simpified version of) the SAFE hardware. This is interesting because the behavior of the abstract machine is achieved by a fairly intricate interplay between a hardware “rule cache” and a software layer that fills the cache as needed by consulting a symbolic representation of the current security policy. Since this mechanism lies at the very core of the SAFE architecture’s security guarantees, we wanted to be completely sure it is correct (and it is!).

Read more »

Michael Fisher on verifying autonomous systems

 |   |  Conversations

Michael Fisher portrait Michael Fisher is a professor of Computer Science, specialising in logical methods and automated formal verification, and Director of the multi-disciplinary Centre for Autonomous Systems Technology at the University of Liverpool and member of the Logic and Computation group in the Department of Computer Science.

Professor Fisher is also a Fellow of both the BCS and the IET, and a member of the UK Computing Research Committee. He is Chair of the Department’s Industrial Liaison Committee.

Luke Muehlhauser: In “Verifying Autonomous Systems” (2013), you and your co-authors summarize some recent approaches to formally verifying autonomous systems. At one point, you write:

Many autonomous systems, ranging over unmanned aircraft, robotics, satellites, and even purely software applications, have a similar structure, namely layered architectures as summarized in Figure 1. Although purely connectionist/sub-symbolic architectures remain prevalent in some areas, such as robotics, there is a broad realization that separating out the important/difficult choices into an identifiable entity can be very useful for development, debugging, and analysis. While such layered architectures have been investigated for many years they appear increasingly common in autonomous systems.

The accompanying figure is:

Figure 1. Typical hybrid autonomous figure architecture—with suitable analysis techniques noted.

What can you say about how common you think something like your “typical hybrid autonomous system architecture” is? E.g. do you think that kind of architecture is in use in ~20 different real-world applications, or ~200 different real-world applications, or perhaps more? Do you think there’s a trend in favor of such architectures? Is there a trend toward such architectures even in robotics, do you think?

Read more »

Harry Buhrman on quantum algorithms and cryptography

 |   |  Conversations

Harry Buhrman portrait Harry Buhrman is head of the research group ‘Algorithms and Complexity’ at the Centrum Wiskunde & Informatica, Amsterdam, which he joined in 1994. Since 2000 he also has a joint appointment as full professor of computer science at the University of Amsterdam. Buhrman’s research focuses on quantum computing, algorithms, complexity theory, and computational biology. In 2003 he obtained a prestigious Vici award and was coordinator of several national and international projects.

Buhrman is editor of several international journals and is member of various advisory and scientific boards, such as the advisory board of the Institute for Quantum Computing (Waterloo, Canada).

Luke Muehlhauser: In theory, position-based quantum cryptography could ensure that certain tasks could only be performed at certain locations:

For example, a country could send a message in such a way that it can only be deciphered at the location of its embassy in another country.

In Buhrman et al. (2011), you and your co-authors showed that

if collaborating adversaries are allowed to pre-share an arbitrarily large entangled quantum state, then… position-based cryptography… is impossible… in the quantum setting.

On the positive side, we show that for adversaries that are restricted to not share any entangled quantum states, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in the bounded case of a bounded amount of entanglement.

What is the current state of our knowledge on whether secure position-verification is possible given a bounded amount of entanglement?


Harry Buhrman: Classically such schemes will always be insecure, also if one restricts the running time or other resources of the adversaries. Quantumly the situation is more complicated, although we and others have shown that with an exponential amount of entanglement, also quantum schemes can be broken and are insecure. The quest is thus on for schemes that 1) can be easily implemented by the honest parties 2) require unreasonable amounts of entanglement for adversaries to break the scheme. We have seen some partial progress along these lines. For example a paper by Beigi and Koenig shows that there are schemes where a linear amount of entanglement is necessary to break them. It turns out that the question whether such schemes exists and if they do, prove for certain schemes that they are secure, is a very hard problem that we are currently working on. It turns out that the approach we have taken implies, if successful, results in classical complexity theory, and thus are very hard. On the other hand, it may still be possible that there simply do not exist schemes that are secure in this sense.
Read more »

New paper: “Problems of self-reference in self-improving space-time embedded intelligence”

 |   |  News

Problems of self-referenceWe’ve released a new working paper by Benja Fallenstein and Nate Soares, “Problems of self-reference in self-improving space-time embedded intelligence.”

Abstract:

By considering agents to be a part of their environment, Orseau and Ring’s space-time embedded intelligence is a better fi t for the real world than the traditional agent framework. However, a self-modifying AGI that sees future versions of itself as an ordinary part of the environment may run into problems of self-reference. We show that in one particular model based on formal logic, naive approaches either lead to incorrect reasoning that allows an agent to put off an important task forever (the procrastination paradox), or fail to allow the agent to justify even obviously safe rewrites (the Löbian obstacle). We argue that these problems have relevance beyond our particular formalism, and discuss partial solutions.

This working paper also cites a brief new technical report by Fallenstein, “Procrastination in probabilistic logic.”

Update 05/14/14: This paper has been accepted to AGI-14.

Liveblogging the SV Gives Fundraiser

 |   |  News

SVGives logo lrgToday MIRI is participating in a massive 24-hour fundraiser called SV Gives. Strategy details here, donate here.

This blog post will be updated many times throughout the day.

Total donated to MIRI: $110,245.

Total prizes & matching won for MIRI: $61,330.

 

12:12am Pacific: That’s a wrap, folks! Our thanks once again to SVCF for putting together a thrilling fundraiser with a neck-and-neck race toward the end. Our thanks to everyone who participated in SV Gives. And of course many thanks to our dedicated, well-organized donors who made this such a surprising success for MIRI. And finally, my thanks to the MIRI staff who worked very long hours to run the fundraiser, especially Malo Bourgon, who worked 38 hours straight, and now must go to sleep. :)

12:07am Pacific: For the last hour, MIRI once again won both the $2,000 prize and the $150 prize! Total raised is $110,245 plus $61,330 in prizes and matching funds!

12:04am Pacific: Fundraiser complete! $7.9M raised for local nonprofits. Congrats to SVCF for a rather thrilling fundraiser, and to leaderboard winners Sankara Eye Foundation and Burlingame Community for Education!

11:58pm Pacific: With two minutes to spare, we passed 2000 total donations today!

11:06pm Pacific: Another $2,000! And also another $150 for a random winner, Samuel Brooks!

10:10pm Pacific: And another $2,000!

9:22pm Pacific: MIRI has won $2,000 again!

8:07pm Pacific: MIRI wins $2,000 again!

7:57pm Pacific: Wow, MIRI and Sankara are still neck-and-neck for Total Unique Donors! Right now Sankara has a 5 person lead.

7:09pm Pacific: MIRI won another $2,000 for unique donors last hour, plus $6,980 in matching! But in other news, Sankara Eye Foundation has now overtaken us in the race for the Grand Prize!

6:21pm Pacific: MIRI won $3,030 in matching at 6pm. Thanks, everyone!

6:05pm Pacific: MIRI won another $2,000 for unique donors last hour. Great job everyone! Get ready for more matching funds being avilable at 7pm sharp!

5:54pm Pacific: Hurray! MIRI was one of 50 organizations to win $1,000 from the 5pm matching funds. The 6pm matching funds are coming up, so try to send your donation in the first ~2 seconds after the hour!

5:11pm Pacific: We won the hour again ($2,000), and we also won a 2nd randomly chosen $150 Golden Ticket, courtesy of a donation by Simon Safar!

4:36pm Pacific: Amazingly, MIRI is now 12% of all donations so far during SV Gives day.

4:27pm Pacific: We’ve reached 250 unique donors for the day; thanks so much! As it happens, there’s a MIRI research workshop going on right now, so here is a photo of what you’re all funding (several times over)!

4:06pm Pacific: Another $2,000 for MIRI. Note that we’re coming up on the 5pm matching opportunity, so you should try to donate in the first 5 seconds after 5pm to try to win the match!

3:16pm Pacific: KFOX will be covering SV Gives between 5-7pm today.

3:06pm Pacific: Another $2,000! The strategy is still working!

2:10pm Pacific: MIRI won the hourly $2,000 again. Thanks, everyone!

1:36pm Pacific: Noon matching results have been released. MIRI got $2910 of the $50,000 in matching, which was apparently all taken in less than 4 seconds!

1:11pm Pacific: Another $2,000 prize won. Our deep and sincere thanks to SVCF for organizing SV Gives, and to MIRI’s donors for being so dedicated and well-organized!

12:06pm Pacific: And we won the $2,000 again! Many thanks to our astoundingly well-coordinated donors.

11:07am Pacific: We’ve won the $2,000 Most Unique Donors Each Hour prize again. Who will break MIRI’s winning streak?

10:34am Pacific: We’ve hit the 200 unique donors (for the whole day) mark!

10:08am Pacific: And yet another $2,000 prize for Most Unique Donors Each Hour! I bet the very gracious Sobrato Family Foundation wasn’t expecting to be one of MIRI’s largest donors of the year so far.

9:29am Pacific: On Twitter, SVCF asked us: “What’s your secret? You’ve just got the 9 a.m. $2,000 Golden Ticket prize for a sixth time! Congrats!” We replied: “Our secret is: 70+ person-hours of planning and donor coordination, 10+ energy drinks, and many enthusiastic supporters!” Seriously, I think our participation in SV Gives should be sponsored by Rockstar energy drinks, given how many of them we are consuming over here!

9:07am Pacific: MIRI wins another $2,000. Three cheers for donor coordination!

8:22am Pacific: $1,970 more in matching came in at the beginning of this hour! (The first 14 seconds of this hour, to be precise.)

8:10am Pacific: Another hour, another $2,000 prize for MIRI! Thanks again, everyone.

7:48am Pacific: In the first ~30 seconds after 7am, we captured $2,340 in matching. Thanks, everyone!

7:07am Pacific: MIRI wins the $2,000 prize once again! (For the 6am-7am hour.)

6:16am Pacific: 150 unique donors today so far.

6:08am Pacific: Excellent work, everyone! MIRI won the $2,000 prize for “Most Unique Donors Each Hour” for a third time! (For the 5am-6am hour.)

5:27am Pacific: According to SV Gives’ twitter account, NBC will be covering the SV Gives fundraiser in 3 minutes.

5:18am Pacific: Our thanks to Mick Porter, whose donation won the $150 prize for “random winner” during the 4am hour! We also won the $2,000 “Most Unique Donors Each Hour” again for the 4am-5am hour!

4:41am Pacific: So far we’ve won the $2,000 prize for Most Unique Donors Each Hour once, but not yet twice, so it looks like marginal donors giving as little as $10 each hour can make a difference!

3:50am Pacific: If you’re visiting this page due to MIRI’s SV Gives participation, and would like to know what it looks like to do technical work on ensuring good outcomes from future self-improving AI programs, check out our just-released new working paper, “Problems of self-reference in self-improving space-time embedded intelligence.”

3:04am Pacific: Here’s a live feed of MIRI HQ. Louie, Malo, myself, and Nate are there now.

2:23am Pacific: We won the $2,000 Golden Ticket for the 1am-2am hour! We also won the $2500 “Local Area Code Prize” by way of Patrick LaVictoire making the 408th donation (to any charity) of the day! Our thanks to the Sobrato Family Foundation and the Shackleton Family Foundation, respectively.

As featured in:     Business Week   The Guardian   MSNBC   SF Weekly   Technology Review