OPINION

DIANA GRIBBON MOTZ, Circuit Judge:

In 1998, a member of the United Mine Workers of America, Local 93 filed a grievance with the Marrowbone Development Company asserting that Marrowbone assigned to non-union members certain work that rightfully belonged to Union employees under the governing collective bargaining agreement. The Company prevailed in arbitration, but the district court vacated the arbitration award finding that the Union did not receive a full and fair hearing. Because the arbitrator exceeded his authority under the governing agreement and failed to provide a fundamentally fair hearing, we affirm.

I.

Prior to 1993, Marrowbone operated a non-union coal mining complex in Mingo County, West Virginia. In May 1993, the parties to this litigation signed an interim collective bargaining agreement, and the National Labor Relations Board certified Local 93 as the exclusive collective bargaining agent for Marrowbone's Union employees. The National Bituminous Coal Wage Agreement of 1993 ("1993 Agreement") superseded the interim agreement in December 1993 and controlled work assignments and dispute resolution.

In 1994, members of the Union filed six grievances against the Company pursuant to the 1993 Agreement. Five of the six grievances asserted that Marrowbone used salaried employees — such as Company supervisors — to perform various delivery tasks that the 1993 Agreement assigned to Union employees. The sixth grievance alleged that Marrowbone used an outside contractor to deliver parts to one of its mines — work that the Union claimed belonged to Union employees exclusively.

All six grievances were submitted to an arbitrator, who ordered Marrowbone to cease using non-union employees or subcontractors to perform the disputed work. Marrowbone appealed to the district court, but sought vacatur of only a portion of the arbitration award — the arbitrator's decision as to the sixth grievance. The Company asserted that this decision violated § 8(e) of the National Labor Relations Act, 29 U.S.C. § 158(e) (1994), because it required Marrowbone to cease doing business with third-party contractors. The parties entered into a Joint Stipulation of Undisputed Material Facts to serve as the findings of fact for the ensuing summary judgment motions. The relevant portion of the Joint Stipulation provided:

In April and August, 1994, disputes developed regarding whether classified employees in the bargaining unit were entitled to perform the work of delivering parts and supplies at the Marrowbone Complex. Prior to that time, all parts and supplies had been delivered by contractors, supervisors, or other non-bargaining unit personnel.

That dispute was ultimately decided by this Court in Marrowbone Development Co. v. District 17, 147 F.3d 296 (4th Cir. 1998) (" Marrowbone I"). We held that preventing Marrowbone from employing outside contractors to do transportation and delivery work not previously performed by Union employees violated § 8(e)'s prohibition against "work-acquisitive" union agreements. Id. at 304. In other words, to permit this would allow the Union to use its bargaining position with Marrowbone to acquire new work that was previously done by third-party contractors, thus producing an illegal "secondary effect." Id. Because Marrowbone never challenged the arbitrator's decision regarding the first five grievances, we did not address the question of whether forcing Marrowbone to cease using its own non-union employees, as opposed to outside contractors, for transportation and delivery work similarly violated § 8(e). Id.

Three months after the Marrowbone I decision, a Union employee filed the instant grievance, asserting that:

The Company has violated the collective bargaining agreement by assigning to supervisors and to vendors the type of work traditionally performed by bargaining unit employees, in connection with the delivery of parts through the mining complex. The work wrongfully assigned outside of the unit includes that traditionally performed by surface utility and supply motormen utility employees, and electricians, among others.

This grievance is governed by the National Bituminous Coal Wage Agreement of 1998 ("1998 Agreement"), which superseded the 1993 Agreement but is identical in all relevant respects. Article XXIII of the 1998 Agreement controls the "Settlement of Disputes" and outlines the "Grievance Procedure." It provides that if the parties fail to resolve a dispute under the first two "steps" of the procedure, the grievance is referred to Step 3, where Company and Union representatives "meet and review the facts and pertinent contract provisions in an effort to reach agreement." If the parties "fail to reach agreement" at Step 3, the matter is referred to Step 4, where an arbitrator "shall conduct a hearing in order to hear testimony, receive evidence and consider arguments" and ultimately decide the case.

In accordance with the 1998 Agreement, the grievance at issue here eventually proceeded to a Step 3 meeting that failed to resolve the complaint. The grievance was then referred to a new arbitrator, who initiated a hearing on February 16, 1999. At the outset of the hearing, the arbitrator accepted a handful of joint exhibits, listened to Marrowbone's summary judgment argument, and heard the Union's opening statement.

In that statement, the Union representative noted that the facts the Union sought to prove were "very different from those presented in" Marrowbone I, and promised that the Union would "present evidence . . . that the disputed work . . . is the same type of work that the company assigned simultaneously to bargaining unit employees and . . . is indisputably covered by the contract." The Union attempted to offer testimony, submit evidence, and present arguments in support of its position, and also requested permission to brief issues upon which there was "some confusion from [the Union] as well as the company." The Union concluded that "[t]he grievance before you seeks only to preserve the right of bargaining unit employees to be assigned the type of bargaining unit work which they have traditionally performed. No more, and no less."

Upon hearing this, the Company asked for a recess. Then the Company requested that the arbitrator "remand this case back to Step 3." The Company representative explained that "[b]ased on the representations made by the union in their opening statement of the evidence and arguments that they intend to present throughout the course of this hearing," a remand was necessary for a "full open, frank . . . negotiation of the issues of fact" that were disputed by the parties.

Without hearing testimony or considering the evidence the Union sought to introduce or the arguments it sought to make, the arbitrator decided to remand the case for another Step 3 meeting. Although initially resistant to the delay that a new Step 3 meeting would create, the Union ultimately consented to the remand after the arbitrator agreed to schedule a specific date (March 26) for a full arbitration hearing in the event that the Step 3 meeting failed to resolve the grievance. Before the aborted February hearing adjourned, the Union asked whether the parties should file briefs. The arbitrator responded by stating that they should not, because "[i]f we're going back to Step 3, we're starting over." (Emphasis added).

However, prior to the scheduled date of the full arbitration hearing, the arbitrator reviewed Marrowbone I and decided that it controlled the outcome of the new grievance. On March 22, 1999, the arbitrator issued his opinion and award dismissing the grievance. The award quoted extensively from Marrowbone I, which held that:

The bargaining unit employees never engaged in delivery and transportation work before the enforcement date of the national agreement. . . . [I]n turning over such work to employees, Marrowbone was required to cease its business relations with other parties, [thus] the [agreement is] secondary in nature . . . [and] therefore contrary to the dictates of § 8(e).

Marrowbone I, 147 F.3d at 304. The arbitrator determined that "the grievance filed in this case also pertains to . . . the subject of the grievances filed in 1994," and therefore concluded "that he [wa]s bound by [ Marrowbone I]."

The Union brought this action seeking to have the district court vacate the arbitration award. Both parties then moved for summary judgment. Finding that the arbitrator denied the Union a full and fair hearing, the district court granted the Union's motion, and remanded the case for an evidentiary arbitration hearing. Marrowbone timely appealed to this court.

II.

It is well-settled that an arbitrator acting within the scope of a collective bargaining agreement receives great deference as to procedural matters and legal interpretation. See, e.g., United Paperworkers Int'l Union v. Misco, Inc., 484 U.S. 29, 40, 108 S.Ct. 364, 98 L.Ed.2d 286 (1987). If, however, an award fails to "draw its essence from the collective bargaining agreement," deference is not appropriate. Id. at 36, 108 S.Ct. 364 (citation omitted). See also Island Creek Coal Co. v. District 28, 29 F.3d 126, 129 (4th Cir. 1994) (citing Misco, 484 U.S. at 38, 108 S.Ct. 364). Similarly, courts owe no deference to an arbitrator who has failed to provide the parties with a full and fair hearing. See Hoteles Condado Beach v. Union De Tronquistas, 763 F.2d 34, 38 (1st Cir. 1985). Because "the question of whether a labor arbitrator exceeded the scope of his authority is a question of law, this court reviews the district court's ruling de novo." Mountaineer Gas Co. v. Oil, Chem., Atomic Workers Int'l Union, 76 F.3d 606, 608 (4th Cir. 1996).

When these principles are applied to the case at hand, we can only conclude that the arbitrator exceeded his authority under the governing 1998 Agreement and failed to provide the Union with a full and fair hearing.

A.

By signing the 1998 Agreement, Marrowbone and the Union contracted to settle labor disputes according to a specified procedure. The final step in that agreed-upon process is arbitration. As such, we are wary of invalidating a decision reached through arbitration. At the same time, however, we must also protect the parties by "insur[ing] that the arbitrator . . . act[s] within the contractually-drawn boundaries" outlined in the 1998 Agreement. Champion Int'l Corp. v. United Paperworkers Int'l Union, 168 F.3d 725, 728 (4th Cir. 1999). And we must remember that an arbitration award is "legitimate only so long as it draws its essence from the collective bargaining agreement." United Steelworkers v. Enterprise Wheel Car Corp., 363 U.S. 593, 597, 80 S.Ct. 1358, 4 L.Ed.2d 1424 (1960).

In determining whether an arbitration award draws its essence from the collective bargaining agreement, and whether the arbitrator acted within the scope of his authority under that agreement, we examine:

(1) the arbitrator's role as defined by the [agreement]; (2) whether the award ignored the plain language of the [agreement]; and (3) whether the arbitrator's discretion in formulating the award comported with the essence of the [agreement's] proscribed limits.

Mountaineer, 76 F.3d at 608.

Thus, we must first determine the arbitrator's proper role under the agreement. The principal role of the arbitrator under the 1998 Agreement is to "conduct a hearing in order to hear testimony, receive evidence and consider arguments" and eventually render a decision. In this case, at the abbreviated February arbitration hearing, the Union representative sought to introduce "facts very different from those presented in [ Marrowbone I]," and present evidence demonstrating that the Company had previously assigned the disputed work to Union members. The Union was "willing to go forward" with its testimony and evidence. The arbitrator refused to permit the Union to do so. He also refused to accept briefs containing written arguments, concluding that they were rendered "unnecessary" because the grievance process would be "starting over." Bowing to the Company's contentions that factual disputes should be discussed, and if possible resolved, at a Step 3 meeting, the arbitrator adjourned the initial hearing before the Union could present its evidence. Although the arbitrator scheduled a subsequent arbitration hearing to satisfy the requirements of the 1998 Agreement — hear testimony, receive evidence, and consider arguments — he never convened that hearing. Thus, the arbitrator clearly failed to comport with his "role as defined by" the 1998 Agreement. Mountaineer, 76 F.3d at 608.

Not only did the arbitrator fail to comply with the role assigned to him under the 1998 Agreement, his award also contravened the Agreement's "plain language," and in fashioning it, he acted well beyond the "proscribed limits" of the Agreement. Id. In pertinent part the 1998 Agreement provides:

At the earliest possible time, but no later than 15 days after referral to him, the arbitrator shall conduct a hearing in order to hear testimony, receive evidence and consider arguments.

In cases in which the parties have agreed that there is no question of fact involved in the grievance, the arbitrator may decide the case upon the basis of a joint statement of the parties and such exhibits as they shall submit.

1998 NBCWA, art. XXIII, § (c)(4) (emphasis added).

Here the parties clearly did not agree that "there is no question of fact involved in the grievance." Rather, they affirmatively acknowledged the existence of factual disputes. Indeed, the Company prevailed upon the arbitrator to remand the case to Step 3 of the grievance procedure in an attempt to resolve those disputes. Despite the parties' acknowledgment of disputed facts, the arbitrator did not abide by the Agreement's command that he "conduct a hearing in order to . . . receive evidence." Instead, he issued an award without holding an evidentiary hearing. This action squarely conflicts with the plain language of the Agreement.

Arbitrators receive their authority from the governing collective bargaining agreement. Their awards are "legitimate only so long as [they] draw [their] essence from" that agreement. United Steelworkers, 363 U.S. at 597, 80 S.Ct. 1358. When, as here, the award does not draw its essence from the governing agreement, and the arbitrator has exceeded his authority under the agreement, "courts have no choice but to refuse enforcement of the award." Id.

B.

For many of the same reasons, we believe that the arbitrator also denied the Union a full and fair hearing.

An arbitrator typically retains broad discretion over procedural matters and does not have to hear every piece of evidence that the parties wish to present. Hoteles, 763 F.2d at 39-40. Indeed, an arbitrator's procedural ruling may not be overturned unless it was "in bad faith or so gross as to amount to affirmative misconduct." Misco, 484 U.S. at 40, 108 S.Ct. 364. Thus, a court will not set aside an arbitration award because the arbitrator refused to hear evidence that was immaterial, id. cumulative, National Post Office Mailhandlers v. United States Postal Service, 751 F.2d 834, 841 (6th Cir. 1985), or irrelevant, Grahams Serv. Inc. v. Teamsters Local 975, 700 F.2d 420, 422-23 (8th Cir. 1982).

Nonetheless, "[v]acatur is appropriate . . . when the exclusion of relevant evidence `so affects the rights of a party that it may be said that he was deprived of a fair hearing.'" Hoteles, 763 F.2d at 40 (quoting Newark Stereotypers' Union No. 18 v. Newark Morning Ledger Co., 397 F.2d 594, 599 (3d Cir. 1968)). See also Burchell v. Marsh, 58 U.S. (17 How.) 344, 349, 15 L.Ed. 96 (1854) ("If the award is within the submission, and contains the honest decision of the arbitrators, after a full and fair hearing of the parties, a court of equity will not set it aside for error.") (emphasis added); Forsythe Int'l, S.A. v. Gibbs Oil Co., 915 F.2d 1017, 1020 (5th Cir. 1990) ("In reviewing the district court's vacatur, we [ask] whether the arbitration proceedings were fundamentally unfair."); National Post Office Mailhandlers, 751 F.2d at 841 ("[T]he standard for judicial review of arbitration procedures is merely whether a party to arbitration has been denied a fundamentally fair hearing.").

In Hoteles, for example, the First Circuit held that an arbitrator's refusal to consider a trial transcript submitted by one of the parties denied them "adequate opportunity to present its evidence and arguments." 763 F.2d at 39. See also Prudential Securities, Inc. v. Dalton, 929 F.Supp. 1411, 1417 (N.D.Okla. 1996) (finding arbitrator guilty of misconduct in making a final decision without hearing "evidence pertinent and material to the controversy").

Here, the arbitrator told the Union to meet with Marrowbone, gather information, negotiate further, and, if the dispute was still not resolved, present evidence and argument at a March 26 arbitration hearing. Yet the arbitrator issued his award without ever holding that hearing or affording the Union the opportunity to present the evidence it had been prepared to offer at the abbreviated February hearing. Notably, the arbitrator did not cancel the scheduled hearing because he found the Union's evidence "cumulative," "irrelevant," or "immaterial"; nor does the record suggest that this evidence was, in fact, cumulative or anything less than highly material and relevant. After all, the Union claimed that this evidence would demonstrate that facts involved in the present grievance were "very different from those presented in" Marrowbone I and that the contested work was "indisputably covered by the contract." Therefore, despite our usual deference, we cannot sanction the decision of an arbitrator who failed to provide a signatory to the arbitration agreement a full and fair hearing.

III.

Finally, we note that Marrowbone's reliance on the doctrine of judicial estoppel is misplaced. Marrowbone contends that the Union is judicially estopped from bringing its grievance because that grievance contradicts the Joint Stipulation entered in the Marrowbone I proceeding. The elements of judicial estoppel are:

First, the party sought to be estopped must be seeking to adopt a position that is inconsistent with a stance taken in prior litigation. And the position sought to be estopped must be one of fact rather than law or legal theory. Second, the prior inconsistent position must have been accepted by the court. . . . Finally, the party sought to be estopped must have "intentionally misled the court to gain unfair advantage." Indeed, we have stated that this factor is the "determinative factor" in the application of judicial estoppel to a particular case.

Lowery v. Stovall, 92 F.3d 219, 224 (4th Cir. 1996) (internal citations omitted), cert. denied, 519 U.S. 1113, 117 S.Ct. 954, 136 L.Ed.2d 841 (1997). In this case, it is not at all clear that the "party sought to be estopped," i.e., the Union, has taken inconsistent factual positions or that it has intentionally mislead the court.

The Union's current grievance is not, on its face, contrary to the Joint Stipulation that the parties entered for purposes of the Marrowbone I litigation. That Stipulation stated that prior to 1994, "all parts and supplies had been delivered by contractors, supervisors, or other non-bargaining unit personnel." In contrast, the grievance before us addresses work " traditionally performed by bargaining unit employees, in connection with the delivery of parts." (Emphasis added). The Joint Stipulation and the grievance do not, on their face, explicitly refer to identical delivery work. Nor does the record indicate that the work described in the Joint Stipulation — "work of delivering parts and supplies at the Marrowbone complex" that was performed prior to 1994 by "non-bargaining unit personnel" — is the same work at issue in the instant grievance — work "in connection with the delivery of parts through the mining complex" that was "traditionally performed by bargaining unit employees." Without evidence demonstrating otherwise, we cannot find the claims inconsistent.

In addition, nothing indicates that the Union intentionally mislead the court in either the current grievance or the Joint Stipulation. "[J]udicial estoppel raises the cost of lying," and "prevent[s] situations from arising in which one of two related decisions has to be wrong because a party took opposite positions and won both times." Chaveriat v. Williams Pipe Line Co., 11 F.3d 1420, 1427-28 (7th Cir. 1993). Neither of those situations is present here. There is no evidence that the Union was lying in the Joint Stipulation or is lying in the current proceeding. Of course, if on remand the Company proves that the work at issue here is identical to that covered by the Joint Stipulation and that the Union intentionally mislead the court, then it may reassert its judicial estoppel argument. On the record before us, however, we find no basis for holding that judicial estoppel prevents the Union from bringing its claim.

IV.

In sum, the arbitrator exceeded his authority under the 1998 Agreement and denied the Union a full and fair hearing. Therefore, we affirm the district court's judgment vacating the arbitration award and remanding the case to the arbitrator for the evidentiary hearing required under the governing collective bargaining agreement.

AFFIRMED