I started with a few simple rules regarding air travel:

1. All the rules apply to everyone including the CEO.

2. The company only pays for the lowest available economy fare, regardless of flight length.

3. Everyone gets to keep their miles and use them as they wish, including on upgrades for business trips if that is their desire.

4. No one is forced to take a redeye or a ridiculously complex itinerary to save a few bucks.

5. If, by paying a few bucks more, we can accomodate someone's preferred airline request or get them an upgradeable fare that they will upgrade from, we'll cover it.

6. What constitutes "a few bucks" is a matter of fact, determined on an individual trip basis.

Still following these rules today, 20 years later, having gone from 2 to 230 employees, and now being a public company.