[Letterhead of Goldman, Sachs & Co.]

Exhibit 10.4

Exhibit 10.4

[Letterhead of Goldman, Sachs & Co.]

PERSONAL AND CONFIDENTIAL

February 10, 2005

John S. Reed

Chairman

New York Stock Exchange, Inc.

11 Wall Street

New York, New York 10005

Dear Mr. Reed:

We are pleased to confirm the arrangements under which Goldman, Sachs & Co. (“Goldman Sachs”) is authorized by the New York Stock Exchange, Inc. (the “Company” or the “NYSE”) to facilitate exploring a potential strategic transaction between the Company and Archipelago Holdings, Inc. (“Archipelago”) which is expected to take the form of a merger, consolidation or other business combination with Archipelago but may take the form of a stock or asset sale or other transaction involving the Company and Archipelago (a “Transaction”). The Company understands that Archipelago has similarly authorized Goldman Sachs pursuant to a separate letter (the “Archipelago Letter”) to facilitate exploring a Transaction on terms consistent with those contained in this letter. It is understood and agreed that the Company will engage one or more financial advisors in connection with the Transaction pursuant to a separate agreement to provide a fairness opinion with respect to a Transaction and, if deemed appropriate in the opinion of the Company in its sole discretion, to negotiate on the Company’s behalf the financial aspects of a Transaction with Archipelago, perform valuation analyses and provide financial advice.

By authorizing the arrangement in this letter, the Company is not agreeing or committing to enter into or consummate a Transaction, and nothing in this letter shall prevent the Company from abandoning or otherwise electing not to proceed with a Transaction. The Company shall have final authority to make all decisions with respect to a Transaction, including the right to determine whether to proceed with such a transaction. This letter does not create any agency relationship between the Company and Goldman Sachs, and, accordingly, Goldman Sachs has no power to enter into any agreement or incur any obligation on behalf of the Company.

New York Stock Exchange, Inc.

February 10, 2005

Page Two

During the term of this arrangement, we will assist the Company and Archipelago in connection with a potential Transaction which assistance may include facilitating discussions between the Company and Archipelago with respect to a Transaction. As part of our services, we will perform certain valuation analyses, including with respect to any pro forma combined company resulting from a Transaction. Notwithstanding the foregoing, we will not (i) negotiate on your behalf the financial aspects of a Transaction with Archipelago or (ii) render a fairness opinion in connection with a Transaction.

The Company agrees to pay us a transaction fee in cash to be mutually agreed upon between the Company and Goldman Sachs (the “Transaction Fee”) if and when a Transaction is consummated.

If the Company or any of its affiliates enters into a definitive written agreement providing for a Transaction (the “Agreement”), and the Agreement provides for a payment at any time to the Company in the event the Transaction contemplated thereby is terminated or otherwise not consummated (the “Payment”), the Company agrees that, if and when such payment is made to the Company, the Company shall pay to Goldman Sachs a fee to be mutually agreed upon between Goldman Sachs and the Company (the “Payment Fee”).

You also agree to reimburse us periodically, upon request, and upon consummation of the transaction or transactions contemplated hereby or upon termination of our services pursuant to this letter, for one-half of our reasonable out-of-pocket expenses, including the reasonable fees and disbursements of our attorneys, plus any sales, use or similar taxes (including penalties, interest and other tax-related additions to such taxes, if any) arising in connection with the arrangement provided in this letter and the Archipelago Letter or performing the services that are the subject of this letter and the Archipelago Letter. The fees and disbursements of counsel to be reimbursed pursuant to the immediately preceding sentence shall not exceed $50,000 without the prior written consent of the Company, which consent shall not be unreasonably withheld; provided, however, this sentence shall in no way affect the Company’s obligations as set forth in Annex A to this letter.

The Company and its management will promptly inform Goldman Sachs of any further discussions with Archipelago concerning a Transaction and of any inquiries they may receive with respect to a Transaction.

Subject to the twelfth paragraph of this letter, please note that any written or oral advice provided by Goldman Sachs in connection with this arrangement is for the information of the Board of Directors and senior management of the Company, and such advice and the terms of this letter may not be disclosed to any third party or circulated or referred to publicly without our prior written consent, except as may be required pursuant to a subpoena, request or order issued by a court of competent jurisdiction or by a judicial, administrative, legislative or regulatory body or committee or the Hart-Scott-Rodino Antitrust Improvements Act of

New York Stock Exchange, Inc.

February 10, 2005

Page Three

1976, as amended, and the rules and regulations thereunder, in which case the Company shall (a) notify Goldman Sachs of the receipt of any such subpoena, request or order, (b) consult with Goldman Sachs as to the advisability of taking steps to resist or narrow the scope of the disclosure contemplated thereby and (c) cooperate with Goldman Sachs in any reasonable efforts that it may make to obtain an order or other reliable assurance that confidential treatment will be accorded to such advice and the terms of this letter. Nothing in this letter shall preclude or limit the Company, in its capacity as a national securities exchange under the United States Securities Exchange Act of 1934, as amended, from disclosing (including, if required, without prior notice to Goldman Sachs) information related to the arrangement provided in this letter to the United States Securities and Exchange Commission (the “SEC”) as may be required of the Company in such capacity from time to time by the SEC.

In connection with arrangements such as this, it is our firm policy to receive indemnification. The Company agrees to the provisions with respect to our indemnity and other matters set forth in Annex A, which is incorporated by reference into this letter.

The arrangement provided in this letter may be terminated by you or us at any time with or without cause effective upon receipt of written notice to that effect; provided, however, that our services will automatically terminate on the date that is thirty days after the date of this letter unless you and we shall agree in writing to extend them for a specified period. We will be entitled to (i) the Transaction Fee in the event that, at any time prior to the expiration of the one-year anniversary of such termination, an Agreement is entered into pursuant to which a Transaction is eventually consummated by the Company or any of its affiliates and (ii) the Payment Fee in the event that, at any time prior to the expiration of the one-year anniversary of such termination, an Agreement is entered into pursuant to which a Payment is eventually made; provided, however, in each of case (i) and (ii), in the event Goldman Sachs terminates its services hereunder without cause, Goldman Sachs will not be entitled to either the Transaction Fee or the Payment Fee pursuant to this sentence.

The Company understands and acknowledges that we are rendering services simultaneously to the Company and to Archipelago in connection with a Transaction. The Company understands and acknowledges that potential conflicts of interest, or a perception thereof, may arise as a result of our rendering services to both the Company and to Archipelago. Notwithstanding the foregoing, the Company hereby (i) consents to Goldman Sachs rendering services to Archipelago in connection with the Transaction while rendering services to the Company in connection with a Transaction pursuant to this letter and (ii) waives any claim of conflict of interest with respect to our rendering services for both the Company and Archipelago in connection with a Transaction.

The Company agrees that any documents and information that the Company or its representatives or advisors may provide to Goldman Sachs or our counsel in connection with

New York Stock Exchange, Inc.

February 10, 2005

Page Four

the performance of our services in connection with a Transaction, including any documents and information that the Company considers to be proprietary and confidential, may be provided without limitation by Goldman Sachs or its counsel to Archipelago and its representatives and advisors; provided, however, that any such documents and information shall be subject to the letter agreement of even date herewith between Goldman Sachs and the Company regarding certain confidentiality obligations owed by Goldman Sachs to the Company. The Company understands that many of the Goldman Sachs team members working on or consulted in connection with our rendering services to the Company pursuant to this letter in connection with a Transaction will also be part of the Goldman Sachs team in our rendering services to Archipelago in connection with a Transaction.

As you know, Goldman Sachs is a full service securities firm engaged, either directly or through its affiliates, in various activities, including securities trading, investment management, financing and brokerage activities and financial planning and benefits counseling for both companies and individuals. In the ordinary course of these activities, Goldman Sachs and its affiliates may actively trade the debt and equity securities (or related derivative securities) of companies which may be the subject of this letter for their own account and for the accounts of their customers and may at any time hold long and short positions in such securities.

You acknowledge that Goldman Sachs and certain of its affiliates are members of the Company and own, in the aggregate, approximately 21 seats and lease approximately an additional 92 seats on the NYSE and Goldman Sachs has a representative on the Board of Executives of the Company. You also acknowledge and agree that the arrangement provided in this letter shall not prohibit, prevent or restrict such representative from continuing to act in his capacity on the Board of Executives (subject to the policies and procedures of the Board of Executives as may be in effect from time to time) with respect to any potential transactions being considered by the Company (including by deliberating and voting, if applicable, on any proposals presented to the Company’s Board of Executives), and shall not prohibit, prevent or restrict Goldman Sachs (or its affiliates), as members, from voting (if a vote of the members is taken) their respective membership interests in its own economic interest in connection with any proposed transaction. You hereby agree to waive any, and agree not to make a claim based on an assertion that Goldman Sachs has a, conflict of interest by virtue of its (or its affiliates’) membership in the Company or the ownership and leasing of such seats and representation on the Board of Executives or that Goldman Sachs (or its affiliates), in its capacity as a member, or such representative must act in a particular manner solely because of the arrangement provided in this letter.

You acknowledge that Goldman Sachs Execution & Clearing, LP (“SLK”), an affiliate of Goldman Sachs, provides clearing and technical services to Archipelago. In addition, you acknowledge that Goldman Sachs or its affiliates hold an interest of approximately 15.6% of

New York Stock Exchange, Inc.

February 10, 2005

Page Five

the common stock of Archipelago. You hereby acknowledge and agree that the arrangement provided in this letter shall not prohibit, prevent or restrict (i) SLK, Goldman Sachs and their affiliates from continuing to manage, hold and pursue such investments and relationships, including by taking such actions as they deem appropriate in their economic interest with respect to their investments, or otherwise, or (ii) SLK from continuing to provide the aforementioned technical and clearing services. You also acknowledge that Goldman Sachs has performed, currently performs and may in the future perform, various financial advisory and investment banking services from time to time for ARMY for which we have received or will receive fees, commissions or other payments. You hereby agree to waive any, and not to make a claim based on an assertion that Goldman Sachs has a conflict of interest by virtue of the foregoing, or that SLK, Goldman Sachs or their affiliates must act in a particular manner in respect to their investments, board representations or commercial relationships solely because of the arrangement provided in this letter.

The Company recognizes that, in providing our services pursuant to this letter, we will rely upon and assume the accuracy and completeness of all of the financial, accounting, tax and other information discussed with or reviewed by us for such purposes, and we do not assume responsibility for the accuracy or completeness thereof. Goldman Sachs will have no obligation to conduct any independent evaluation or appraisal of the assets or liabilities of the Company, Archipelago, or any other party or to advise or opine on any related solvency issues. It is understood and agreed that Goldman Sachs will act under this letter as an independent contractor with duties under this letter solely to the Company and nothing in this letter or the nature of our services shall be deemed to create a fiduciary or agency relationship between us and the Company or its members, employees or creditors. Except as set forth in Annex A hereto, nothing in this letter is intended to confer upon any other person (including members, employees or creditors of the Company) any rights or remedies hereunder or by reason hereof.

Goldman Sachs does not provide accounting, tax or legal advice. The Company is authorized, subject to applicable law, to disclose any and all aspects of this potential transaction that are necessary to support any U.S. federal income tax benefits expected to be claimed with respect to such transaction, and all materials of any kind (including tax opinions and other tax analyses) related to those benefits, without Goldman Sachs imposing any limitation of any kind.

New York Stock Exchange, Inc.

February 10, 2005

Page Six

Please confirm that the foregoing is in accordance with your understanding by signing and returning to us the enclosed copy of this letter, which shall become a binding agreement upon our receipt. We are delighted to accept this role and look forward to working with you on this assignment.

New York Stock Exchange, Inc.

February 10, 2005

Page Seven

Annex A

In the event that Goldman Sachs becomes involved in any capacity in any action, proceeding or investigation brought by or against any person, including members of the Company, in connection with or as a result of either the arrangement provided in this letter or performing the services that are the subject of this letter, the Company periodically will reimburse Goldman Sachs for its reasonable legal and other expenses (including the cost of any investigation and preparation) to the extent incurred in connection therewith; provided, however, that if it is found in any such action, proceeding or investigation that any loss, claim, damage or liability of Goldman Sachs has resulted from the gross negligence, willful misconduct or bad faith of Goldman Sachs in performing the services which are the subject of this letter, Goldman Sachs shall repay such portion of the reimbursed amounts that is attributable to expenses incurred in relation to the act or omission of Goldman Sachs which is the subject of such finding. The Company also will indemnify and hold Goldman Sachs harmless against any and all losses, claims, damages or liabilities to any such person in connection with or as a result of either the arrangement provided in this letter or performing the services that are the subject of this letter, except to the extent that any such loss, claim, damage or liability results from the gross negligence, willful misconduct or bad faith of Goldman Sachs in performing the services that are the subject of this letter. If for any reason the foregoing indemnification is unavailable to Goldman Sachs or insufficient to hold it harmless, then the Company shall contribute to the amount paid or payable by Goldman Sachs as a result of such loss, claim, damage or liability in such proportion as is appropriate to reflect the relative economic interests of the Company and its members on the one hand and Goldman Sachs on the other hand in the matters contemplated by this letter as well as the relative fault of the Company and Goldman Sachs with respect to such loss, claim, damage or liability and any other relevant equitable considerations (including any failure by Goldman Sachs to notify the Company of its involvement in any action, proceeding or investigation for which a claim for indemnification in respect thereof is to be made against the Company as provided below). The reimbursement, indemnity and contribution obligations of the Company under this paragraph shall be in addition to any liability which the Company may otherwise have, shall extend upon the same terms and conditions to any affiliate of Goldman Sachs and the partners, directors, agents, employees and controlling persons (if any), as the case may be, of Goldman Sachs and any such affiliate, and shall be binding upon and inure to the benefit of any successors, assigns, heirs and personal representatives of the Company, Goldman Sachs, any such affiliate and any such person. The Company also agrees that neither Goldman Sachs nor any of such affiliates, partners, directors, agents, employees or controlling persons shall have any liability to the Company or any person asserting claims on behalf of or in right of the Company in connection with or as a result of either the arrangement provided in this letter or performing the services that are the subject of this letter, except to the extent that any losses, claims, damages, liabilities or expenses incurred by the Company result from the gross negligence, willful misconduct or bad faith of Goldman Sachs in performing the services that are the subject of this letter. The Company shall not be required to indemnify Goldman Sachs or any of its affiliates, partners, directors, agents, employees or controlling persons for any amount paid or payable by such persons in the settlement of any action, proceeding or investigation without the written consent of the Company, which consent shall not be unreasonably withheld. Promptly after receipt by Goldman Sachs of notice of its involvement in any action, proceeding or investigation, Goldman Sachs shall, if a claim for indemnification in respect thereof is to be made against the Company under this Annex A, notify the Company of such involvement. Failure by Goldman Sachs to so notify the Company shall relieve the Company from the obligation hereunder to indemnify Goldman Sachs under this Annex A only to the

New York Stock Exchange, Inc.

February 10, 2005

Page Eight

extent that the Company suffers actual prejudice as a result of such failure, but shall not relieve the Company from its obligation to provide reimbursement and contribution to Goldman Sachs. Any right to trial by jury with respect to any action or proceeding arising in connection with or as a result of either the arrangement provided in this letter or performing the services that are the subject of this letter is hereby waived by the parties hereto. The provisions of this Annex A shall survive any termination or completion of the arrangement provided in this letter, and this letter shall be governed by and construed in accordance with the laws of the State of New York without regard to principles of conflicts of laws.