I never played Minecraft, but my Lenovo IdeaPad Y470 with a Sandy Bridge (previous generation) Core i5-2410m with a nVidia GT 550m was able to play GTA IV on medium settings. Forget high settings. Even high-end desktop PCs with a graphics card equal to the amount of money you are looking to spend on the laptop will not run the game on high.
A word of warning though. Make sure you get a laptop with good ventilation because GTA IV can cause the CPU to get real hot. After about 2 hours my CPU hit 99C and started to throttle down. In general, I would avoid 14" laptops since they typically do not have much space for really good airflow. Also avoid Lenovo IdeaPads because the bottom of the laptop is referred to as a "thermal panel" by Lenovo themselves. The purpose is so that as little heat will be transferred to underside of the laptop. I placed the overheated Y470 on my bare skin lap and it only felt warm. However, the bottom of the laptop is not designed to take advantage of any cooling pads. I bought a cooling pad (CoolerMaster U2 ... something...) which is a good cooling pad, but it did nothing for the Y470.
The following 15.6" Acer Aspire V3-571G-6622 ($599) is an example of a laptop capable of playing GTA IV. The i5-3230m CPU is a little bit more powerful than my CPU and the nVidia GT 730m is definitely more powerful than the GT 550m in my laptop.
http://www.newegg.com/Product/Product.aspx?Item=N82E16834314016
However, you need to research about how hot the CPU gets. Do not rely on statements like, "It only feels a little warm when I play games". The Lenovo Y470 only felt a bit warm (underside and the keyboard as well) when it was overheated.
The following Acer Aspire V3-551G-X419 ($529) is a less expensive laptop that should also be able to play GTA IV. However, it is not as powerful as the 1st laptop. It has the AMD A10-4600m which is a quad core CPU. However, AMD CPUs are not as powerful as Intel CPUs. At the same clock speed, an Intel Ivy Bridge generation Core i3/i5/i7 CPU is about 20% more powerful than an AMD Trinity generation CPU. The only advantage is that the A10 is a quad core CPU while the i5 is a dual core CPU, but overall the A10 is weaker. It also comes with a Radeon HD 7670m which is weaker than the nVidia GT 550m in my Y470, and most certainly weaker than the GT 730m. But it should still be enough to play GTA IV.
http://www.newegg.com/Product/Product.aspx?Item=N82E16834215974