This is taken straight from the XML files included with Civ V:
(Updated for the June 2011 patch, where all of them were reduced by 50%)
<Type>WORLDSIZE_DUEL</Type>
<NumCitiesPolicyCostMod>15</NumCitiesPolicyCostMod>
<Type>WORLDSIZE_TINY</Type>
<NumCitiesPolicyCostMod>15</NumCitiesPolicyCostMod>
<Type>WORLDSIZE_SMALL</Type>
<NumCitiesPolicyCostMod>15</NumCitiesPolicyCostMod>
<Type>WORLDSIZE_STANDARD</Type>
<NumCitiesPolicyCostMod>15</NumCitiesPolicyCostMod>
<Type>WORLDSIZE_LARGE</Type>
<NumCitiesPolicyCostMod>10</NumCitiesPolicyCostMod>
<Type>WORLDSIZE_HUGE</Type>
<NumCitiesPolicyCostMod>7.5</NumCitiesPolicyCostMod>
So it's 15% for all but the largest two map sizes.