The two factors of 'gender-identity' (whether the speaker is male or female) and 'gender-congruence' (whether or not the gender of speaker and listener is the same) can be assumed to act differently in determining levels of politeness. To investigate this assumption, the present study was designed to analyze university student politeness levels in Japan and South Korea when they (i.e., speakers) asked various people (i.e., listeners) to purchase a concert ticket. A decision tree analysis revealed hierarchies of factors predictive of politeness levels specific to young Japanese and Koreans. Among Japanese, distance (i.e., extent to which speaker and listener are acquainted) was the strongest followed by power (i.e., extent of disparity in social status) and gender-identity/gender-congruence. Among Koreans, however, power appeared to override distance, resulting in the descending order of power and gender-identity/gender-congruence. Regarding gender-related factors, the results of these parallel studies in Japan and South Korea generally suggested a distinctive influence of gender-identity on politeness levels when listeners held equal or lesser power than speakers, while gendercongruence was implicated when listeners held greater power.