In Android 6, how to deny an app permission to access the network? In Android 6, the user has (finally!) the possibility of approving or denying specific permissions to an app.  

However, I couldn't find a way to approve or deny network access, either via Wi-Fi or via cellular data connection. The relevant permission appears in "Other app capabilities" and it's only informative -- apparently there's no way to change it.

Here's an example with the Chess Free app:
You won't be able to achieve success through the native mechanism of Android. 

Cody Toombs at Android Police has very well pointed this out in the article: Android M Will Never Ask Users For Permission To Use The Internet, And That's Probably Okay.

In the section Normal and Dangerous Permissions of the document  Permissions Overview, Google has noted:


  Permissions are divided into several protection levels.
  
  There are two protection levels that affect thrid party apps: normal and dangerous permissions.
  
  
  Normal permissions cover areas where your app needs to access data or resources outside the app's sandbox, but where there's very little risk to the user's privacy or the operation of other apps. For example, permission to set the time zone is a normal permission.
  
  If an app declares in its manifest that it needs a normal permission, the system automatically grants the app that permission at install time. The system does not prompt the user to grant normal permissions, and users cannot revoke these permissions.
  Dangerous permissions cover areas where the app wants data or resources that involve the user's private information, or could potentially affect the user's stored data or the operation of other apps. For example, the ability to read the user's contacts is a dangerous permission. If an app declares that it needs a dangerous permission, the user has to explicitly grant the permission to the app.
  


(Emphasis mine)

Surprising or not, the following permissions comes under the list of Normal Permissions:


CHANGE_NETWORK_STATE - allows applications to change network connectivity state - i.e. mobile data;
CHANGE_WIFI_STATE - allows applications to change Wi-Fi connectivity state;
INTERNET - allows applications to open network sockets.


If that doesn't suffice, checkout the permissions managed by AppOps here. If you don't find your permission listed there, you won't be able to do anything with it in GUI. 

Since alternative methods are already extensively covered on this site, refer to:


Block apps from accessing the Internet on Android device
Are there any tools to sandbox a malware application even more than the granted permissions on Android?