Re: If you require them to tell you exactly what algorithm they use
The corollary of that argument is that similar regulation would be required for all web sites, to ensure that their "internet shop-front signage" was not lying. So trade-practices laws should apply to "SEO", and with any luck put the practice (mostly) out of business.
Seems much more likely that what would really happen is that the game would be over and we'd be back to search results as useful as those of AltaVista.
Be careful what you wish for...