<PAGE>

                                                                    EXHIBIT 10.1
                                                                    ------------

                             STOCKHOLDER AGREEMENT

     STOCKHOLDER AGREEMENT (this "Agreement") dated as of May 4, 2000 among
ShopKo Stores, Inc., a Wisconsin corporation, SKO Holdings, Inc. a Delaware
corporation and a wholly owned subsidiary of ShopKo Stores, Inc. (collectively,
"Holder"), Merck & Co., Inc., a New Jersey corporation ("Parent"), and PV
Acquisition Corp., a Delaware corporation and a wholly owned subsidiary of
Parent ("Merger Sub"). Parent, Merger Sub and ProVantage Health Services, Inc.,
a Delaware corporation (the "Company"), propose to enter into a Merger Agreement
(the "Merger Agreement") on the date of this Agreement providing for the making
of a tender offer by Merger Sub (the "Offer") for shares of Common Stock, par
value $0.01 per share, of the Company (the "Company Common Stock"), at a
purchase price of $12.25 per share, and a subsequent merger (the "Merger")
between the Company and the Merger Sub.

     Holder owns the number of shares of Company Common Stock (the "Shares") or
options to purchase Company Common Stock (the "Stock Options" and collectively,
with the Shares, the "Optioned Securities"), or has the right to vote the number
of Shares or other securities (the "Voting Securities"), listed on Schedule 1.
Parent and the Merger Sub have required, as a condition to entering into the
Merger Agreement, that the Holder enter into this Agreement. The Holder believes
that it is in the best interest of the Company and its stockholders to induce
Parent and the Merger Sub to enter into the Merger Agreement and, therefore, the
Holder is willing to enter into this Agreement.

     Accordingly, in consideration of the mutual covenants and agreements set
forth herein and in consideration of $1.00 and such other valuable consideration
the receipt of which is hereby acknowledged, the parties hereto agree as
follows:

     1.   The Option. Subject to the terms of this Agreement, Holder hereby
          ----------
grants the Merger Sub an irrevocable option (the "Option") to purchase all, and
not less than all, of the Optioned Securities of Holder at the price of $12.25
per share (or such higher price as may be paid pursuant to the Offer), payable
in cash, without interest. The obligation to pay the exercise price for the
Option shall be a joint and several obligation of Parent and Merger Sub.

     2.   Exercise of the Option; Term.
          ----------------------------

          (a)  On the terms and subject to the conditions of this Agreement, the
Merger Sub may exercise the Option at any time after the date on which all
waiting periods under the Hart-Scott-Rodino Antitrust Improvements Act of 1976,
as amended (the "HSR Act"), applicable to the exercise of the Option have
expired or been terminated by written notice to Holder specifying a date and
time for the closing not later than thirty
<PAGE>

(30) business days from the date of such notice (which date and time may be two
business days after the delivery of such notice) and after the Offer has expired
or been terminated; provided, however, that the Option may not be exercised
after it has expired in accordance with the terms hereof.

          (b)  The Option shall expire on the earliest of:

               (1)  the purchase of the Optioned Securities by the Merger Sub
     pursuant to the Offer;

               (2)  the Effective Time (as defined in the Merger Agreement);

               (3)  the termination of the Merger Agreement:

                    (A)  pursuant to the mutual consent of the Company and
          Parent pursuant to Section 7.01(a) of the Merger Agreement;

                    (B)  pursuant to Section 7.01(b) of the Merger Agreement
          (regarding failure of the Offer to be consummated by December 31,
          2000);

                    (C)  pursuant to Section 7.01(c) of the Merger Agreement
          (regarding illegality or prohibition of the Offer or the Merger);

                    (D)  pursuant to Section 7.01(d) of the Merger Agreement
          (regarding a Superior Proposal);

                    (E)  pursuant to Section 7.01(e) of the Merger Agreement
          (regarding termination by Parent on the happening of certain events);
          or

               (4)  thirty (30) days after termination or expiration of the
Offer (such earliest date being referred to in this Agreement as the "Expiration
Date").

          (c)  If the Company receives an Acquisition Proposal (as defined in
the Merger Agreement) which the Company in good faith, after compliance with
Section 5.02 of the Merger Agreement, believes is a Superior Proposal (as
defined in the Merger Agreement) and gives written notice to Parent of such
Superior Proposal in compliance with Section 5.02 of the Merger Agreement,
Parent and Merger Sub will not exercise the Option (if it is then exercisable)
for a period commencing on the date of such written notice and ending on the
first to occur of: (1) one business day after the Company can properly terminate
the Merger Agreement pursuant to Section 7.01(d), (2) written notice to Parent
and Merger Sub from the Company that such Superior Proposal is not being
pursued, which notice shall be provided by the Company to Parent and Merger Sub
in writing promptly upon any such determination, and (3) the date on which the
Company

                                      -2-
<PAGE>

receives a written and binding offer that is at least as favorable, from a
financial point of view, to the stockholders of the Company as the Superior
Proposal (such period is referred to herein as the "Review Period").

          (d)  Merger Sub and Parent agree that if Merger Sub exercises the
Option and the Merger Agreement remains in full force and effect (i) the Shares
purchased by Merger Sub pursuant to the Option shall be treated for purposes of
the Merger Agreement and the Offer as if such Shares were purchased by Merger
Sub in the Offer and (ii) Parent and Merger Sub will ensure that the
transactions contemplated by the Merger Agreement (including the Offer and the
Merger) are consummated. Merger Sub and Parent further agree that if Merger Sub
exercises the Option and the Merger Agreement is not in full force and effect
(i) Parent and Merger Sub will cause the Merger Agreement to again become in
full force and effect (or to cause a merger agreement containing the same
economic terms to become in force and effect) and (ii) Parent and Merger Sub
will ensure that the transactions contemplated by the Merger Agreement (or any
replacement merger agreement), including the Offer and the Merger, are fully
consummated.

     3.   Closing. At the closing:
          -------

          (a)  against delivery of the Optioned Securities, free and clear of
     all liens, claims, charges and encumbrances of any kind or nature
     whatsoever, Parent shall cause the Merger Sub to make payment to Holder of
     the aggregate price for Holder's Optioned Securities by wire transfer of
     immediately available funds; and

          (b)  Holder shall deliver to the Merger Sub a duly executed
     certificate or certificates representing the number of Optioned Securities
     purchased from Holder, together with transfer powers endorsed in blank
     relating to such certificates and, if requested by the Merger Sub, an
     irrevocable proxy duly executed by Holder, authorizing such persons as the
     Merger Sub shall designate to act for Holder as his lawful agents,
     attorneys and proxies, with full power of substitution, to vote in such
     manner as each such agent, attorney and proxy or his substitute shall in
     his sole discretion deem proper, and otherwise act with respect to the
     Optioned Securities at any meeting (whether annual or special and whether
     or not an adjourned meeting) of the Company's stockholders or otherwise,
     and revoking any prior proxies granted by Holder with respect to the
     Holder's Optioned Securities.

     Notwithstanding any provision of this Agreement to the contrary, the Holder
shall validly tender its Shares pursuant to the Offer and shall not withdraw
such Shares prior to the expiration of the Offer, and its obligation to sell any
Optioned Securities shall be satisfied, solely with respect to the Shares so
tendered, upon the purchase of such Shares by the Merger Sub pursuant to the
Offer.

                                      -3-
<PAGE>

          4.   Covenants of the Holder.
               -----------------------

          (a)  During the period from the date of this Agreement until the
     Expiration Date, except in accordance with the provisions of this
     Agreement, Holder agrees that it will not:

               (i)    sell, sell short, transfer, pledge, hypothecate, assign or
          otherwise dispose of, or enter into any contract, option, hedging
          arrangement or other arrangement or understanding with respect to the
          sale, transfer, pledge, hypothecation, assignment or other disposition
          of, any Optioned Securities or Voting Securities;

               (ii)   deposit any Optioned Securities or Voting Securities into
          a voting trust, or grant any proxies or enter into a voting agreement
          with respect to any Optioned Securities or Voting Securities; or

               (iii)  except for actions permitted by Section 5.02 of the Merger
          Agreement, initiate, solicit or knowingly encourage, directly or
          indirectly, any inquiries or the making or implementation of any
          proposal that constitutes, or may reasonably be expected to lead to,
          any Acquisition Proposal (as defined in the Merger Agreement) or enter
          into discussions or negotiate with any person or entity in furtherance
          of such inquiries or to obtain a Acquisition Proposal, or agree to or
          endorse any Acquisition Proposal.

          (b)  Any additional shares of Company Common Stock, warrants, options
     or other securities or rights exercisable for, exchangeable for or
     convertible into shares of Company Common Stock (collectively, "Equity
     Securities") acquired by Holder will become subject to this Agreement and
     shall, for all purposes of this Agreement, be considered Optioned
     Securities or Voting Securities, as the case may be.

          (c)  Holder agrees not to engage in any action or omit to take any
     action which would have the effect of preventing or disabling Holder from
     delivering its Optioned Securities to the Merger Sub or otherwise
     performing its obligations under this Agreement. To the extent that any
     Optioned Securities (other than Company Common Stock) may not be assigned
     by Holder to the Merger Sub without exercising, exchanging or converting
     such Optioned Securities for or into Company Common Stock, Holder agrees to
     exercise, exchange or convert such Optioned Securities for or into Company
     Common Stock prior to the closing of the purchase of such Optioned
     Securities upon exercise of the Option.

                                      -4-
<PAGE>

     5.   Representations and Warranties of Holder.  Holder represents and
          ----------------------------------------
warrants to Parent and the Merger Sub as follows:

          (a)  (i)  Holder is the record or beneficial owner of the Optioned
     Securities, or has the right to vote the Voting Securities, listed on
     Schedule 1, (ii) such Optioned Securities or Voting Securities are the only
     Equity Securities owned of record or beneficially by Holder or in which
     Holder has any interest or which Holder has the right to vote, as the case
     may be, and (iii) Holder does not have any option or other right to acquire
     any other Equity Securities;

          (b)  Holder has the right, power and authority to execute and deliver
     this Agreement and to perform its obligations hereunder; the execution,
     delivery and performance of this Agreement by Holder will not require the
     consent of any other person and will not constitute a violation of,
     conflict with or result in a default under (i) any contract, understanding
     or arrangement to which Holder is a party or by which Holder is bound, (ii)
     any judgment, decree or order applicable to Holder, or (iii) any law, rule
     or regulation of any governmental body applicable to Holder; and this
     Agreement constitutes a valid and binding agreement on the part of Holder,
     enforceable in accordance with its terms, subject to applicable bankruptcy,
     insolvency, moratorium or other similar laws relating to creditors' rights
     and general principles of equity;

          (c)  any Shares included in the Optioned Securities owned by Holder
     have been validly issued and are fully paid and nonassessable (except as
     otherwise provided by Wisconsin law) and any shares of Company Common Stock
     issuable upon exercise, exchange or conversion of any other Equity
     Securities, when issued and upon payment of the exercise price therefor,
     will be validly issued, fully paid and nonassessable (except as otherwise
     provided by Wisconsin law);

          (d)  the Optioned Securities owned by Holder are now, and at all times
     during the term of this Agreement will be, held by Holder free and clear of
     all adverse claims, liens, encumbrances and security interests, and none of
     the Optioned Securities or Voting Securities are subject to any voting
     trust or other agreement or arrangement (except as created by this
     Agreement) with respect to the voting or disposition of the Optioned
     Securities or Voting Securities; and there are no outstanding options,
     warrants or rights to purchase or acquire, or agreements (except for this
     Agreement) relating to, such Optioned Securities or Voting Securities; and

          (e)  upon purchase of the Optioned Securities owned by Holder, the
     Merger Sub will obtain good and marketable title to such Optioned
     Securities, free

                                      -5-
<PAGE>

     and clear of all adverse claims, liens, encumbrances and security interests
     (except any created by the Merger Sub).

     6.   Representations and Warranties of Parent and the Merger Sub. Each of
          -----------------------------------------------------------
Parent and the Merger Sub hereby represents and warrants to Holder that: it is a
corporation duly formed under the laws of the states of their respective
incorporations; it has all requisite corporate power and authority to enter into
and perform all its obligations under this Agreement; the execution and delivery
of this Agreement and the consummation of the transactions contemplated hereby
have been duly authorized by all necessary corporate action on its part; this
Agreement has been duly executed and delivered by it; and this Agreement
constitutes a valid and binding agreement on its part, enforceable in accordance
with its terms, subject to applicable bankruptcy insolvency, moratorium or other
similar laws relating to creditors' rights and general principles of equity.

     7.   Voting of Equity Securities. Holder hereby agrees that, from the date
          ---------------------------
hereof until the Expiration Date, at any meeting of the stockholders of the
Company, however called, and in any action by written consent of the
stockholders of the Company, it shall (a) vote all Voting Securities of Holder
in favor of the Merger; (b) not vote any Voting Securities in favor of any
action or agreement which would result in a breach in any material respect of
any covenant, representation or warranty or any other obligation of the Company
under the Merger Agreement; and (c) vote all Voting Securities of Holder against
any action or agreement which would impede, interfere with or attempt to
discourage the Offer or the Merger, including, but not limited to: (i) any
Acquisition Proposal (other than the Offer and the Merger) involving the Company
or any of its subsidiaries; (ii) any change in the management or board of
directors of the Company, except as otherwise agreed to in writing by the Merger
Sub; (iii) any material change in the present capitalization or dividend policy
of the Company; or (iv) any other material change in the Company's corporate
structure or business. Holder hereby irrevocably (except as set forth below)
appoints designees of Merger Sub, the attorneys, agents and proxies, with full
power of substitution, for the undersigned and in the name, place and stead of
the Holder to vote in such manner as such attorneys, agents and proxies or their
substitutes shall in their sole discretion deem proper and otherwise act,
including the execution of written consents, with respect to all Voting
Securities of the Company which the Holder is or may be entitled to vote at any
meeting of the Company with a record date after the date hereof, whether annual
or special and whether or not an adjourned meeting, or in respect of which the
Holder is or may be entitled to act by written consent. This proxy is coupled
with an interest and shall be irrevocable (except as set forth below) and
binding on any successor in interest of the Holder. This proxy shall operate to
revoke any prior proxy as to Voting Securities heretofore granted by the Holder
other than any proxy provided with respect to the Company's currently scheduled
annual meeting with respect to the agenda items disclosed on the Company's April
19, 2000 Proxy Statement. Such

                                      -6-
<PAGE>

proxy shall terminate upon the termination of this Agreement. The obligations of
this Section 7 shall not apply to Holder during any Review Period and Holder may
revoke this Proxy during any such Review Period as long as Holder reinstates
such proxy promptly upon expiration of such Review Period (unless the Company
accepts a Superior Proposal, in which case the proxy shall terminate).

     8.   Adjustments. In the event of any increase or decrease or other change
          -----------
in the Optioned Securities by reason of stock dividends, split-up,
recapitalizations, combinations, exchanges of shares or the like, the number of
Optioned Securities and Voting Securities subject to this Agreement shall be
adjusted appropriately.

     9.   Other Agreements.
          ----------------

          (a)  As a condition to Parent's willingness to enter into the Merger
Agreement, Holder shall, on the date hereof, enter into a letter, in the form
attached hereto, with the Company, providing for certain changes in their
existing contractual arrangements upon the consummation of the Merger (the "Side
Letter"). Holder agrees that Parent is a third party beneficiary to the Side
Letter and neither it nor the Company will terminate, amend or modify the Side
Letter, or waive any of the provisions thereof, without the prior consent of
Parent, which consent may be withheld for any reason or no reason.

          (b)  Holder shall indemnify and hold harmless Parent and its
affiliates (including the Company) against any liability arising by reason of
the Company and any of its Subsidiaries (i) having been members of a "controlled
group of corporations," under "common control" or members of an "affiliated
service group" with Holder within the meaning of Sections 414(b), (c) or (m) of
the Code, or having been required to be aggregated with Holder under Section
414(o) of the Code, or having been under "common control" with Holder, within
the meaning of Section 4001(a)(14) if ERISA and (ii) having participated in
employee benefit plans and programs of Holder prior to the Effective Time (for
purpose of this clause (ii), regardless of whether clause (i) applies).

          (c)  Holder agrees to indemnify and hold harmless Parent, Merger Sub,
the Company, each of their affiliates and each officer, director and employee
thereof from and against any liability, claim, loss, cost, or expense arising
out of or related to any breach by the Company of the representation set forth
in Section 4.21(b) of the Merger Agreement or the covenant of the Company set
forth in Section 5.10(b) of the Merger Agreement.

          (d)  Holder shall take all actions necessary to cause the covenants in
Sections 5.10(b) and Section 7 of the Side Letter to be complied with.

                                      -7-
<PAGE>

     10.  Governing Law. This Agreement shall be governed by and construed in
          -------------
accordance with the law of the State of Delaware without regard to its rules of
conflict of laws.

     11.  Further Assurances. Each party hereto shall perform such further acts
          ------------------
and execute such further documents as may reasonably be required to carry out
the provisions of this Agreement, including, without limitation, using
commercially reasonable efforts to obtain all necessary consents, approvals or
waivers under the HSR Act. Without limiting the generality of the foregoing, the
Holder, to the extent it "controls" the Company, according to the HSR Act and
the rules and regulations promulgated by the Federal Trade Commission to
implement the HSR Act, shall, to the extent required by the HSR Act, file a
premerger notification and report form under the HSR Act with respect to the
Merger as promptly as reasonably possible following execution and delivery of
this Agreement and shall use commercially reasonable efforts to promptly respond
to any request for additional information pursuant to Section (e)(1) of the HSR
Act.

     12.  Legend. As soon as practicable after the execution of this Agreement,
          ------
the following legend shall be placed on the certificates representing the
Optioned Securities:

          "The Securities represented by this certificate are subject to
     certain transfer and other restrictions contained in an Stockholder
     Agreement, dated as of May 4, 2000, among Merck & Co., Inc., P.V.
     Acquisition Corp. and ShopKo Stores, Inc."

     13.  Assignment. This Agreement may not be assigned by any party hereto,
          ----------
except that the Merger Sub may assign its right to purchase the Optioned
Securities to one or more of its affiliates.

     14.  Remedies. The parties agree that legal remedies for breach of this
          --------
Agreement will be inadequate and that this Agreement may be enforced by Parent
and the Merger Sub by injunctive or other equitable relief.

     15.  Notices. All notices or other communications required or permitted
          -------
hereunder shall be in writing (except as otherwise provided herein) and shall be
deemed duly given if delivered in person, by confirmed facsimile transmission or
by overnight courier service, addressed as follows:

                                      -8-
<PAGE>

     To Parent or the Merger Sub:

          Merck & Co., Inc.
          One Merck Drive
          P.O. Box 100 W53AB-05
          Whitehouse Station, NJ 08889
          Attention: Celia A. Colbert
          Assistant General
          Counsel and Secretary

          Fax: (908) 735-1246

     With a copy to:

          Fried, Frank, Harris, Shriver
           & Jacobson
          One New York Plaza
          New York, New York 10004
          Attention: Gary P. Cooperstein, Esq.
          Facsimile: (212) 859-4000

     To Holder:

          ShopKo Stores, Inc.
          700 Pilgrim Way
          Green Bay, Wisconsin 54307-9060
          Attention: Richard D. Schepp
          Senior Vice President
          General Counsel, Secretary
          Facsimile: (920) 429-5664

     With copies to:

          Godfrey & Kahn, S.C.
          780 North Water Street
          Milwaukee, Wisconsin 53202
          Attention: Randall J. Erickson
          Facsimile: (414) 273-5198

     16.  Severability. If any term or other provision of this Agreement is
          ------------
invalid, illegal or incapable of being enforced by any rule of law or public
policy, all other conditions and provisions of this Agreement shall nevertheless
remain in full force and effect so long as the economic or legal substance of
the transactions contemplated hereby is not affected in any manner adverse to
any party. Upon such determination that any

                                      -9-
<PAGE>

term or other provision is invalid, illegal or incapable of being enforced, the
parties hereto shall negotiate in good faith to modify this Agreement so as to
effect the original intent of the parties as closely as possible in an
acceptable manner to the end that the transactions contemplated hereby are
fulfilled to the extent possible.

     17.  Counterparts. This Agreement may be executed in counterparts, each of
          ------------
which shall be deemed to be an original, but all of which together shall
constitute one and the same agreement.

     18.  Binding Effect; Benefits. This Agreement shall be binding upon the
          ------------------------
parties hereto and their respective heirs, legal representatives, successors and
permitted assigns. Nothing in this Agreement, expressed or implied, is intended
to or shall confer on any person other than the parties hereto and their
respective heirs, legal representatives and successors and permitted assigns any
rights, remedies, obligations or liabilities under or by reason of this
Agreement.

     IN WITNESS WHEREOF, the Holder, Parent and Merger Sub have entered into
this Agreement as of the date first written above.

                              SHOPKO STORES, INC.


                              By:  Richard D. Schepp
                                   ---------------------------------------------
                                   Name:  Richard D. Schepp
                                   Title: Senior Vice President, General
                                          Counsel/Secretary


                              MERCK & CO., INC.


                              By:  /s/ Judy C. Lewent
                                   ---------------------------------------------
                                   Name:  Judy C. Lewent
                                   Title: Senior Vice President and
                                          Chief Financial Officer


                              PV ACQUISITION CORP.


                              By:  /s/ Judy C. Lewent
                                   ---------------------------------------------
                                   Name:  Judy C. Lewent
                                   Title: President

                                      -10-
<PAGE>

                                  SCHEDULE 1
                                  ----------

<TABLE>
<CAPTION>
Number                   Number
of                       of                  Total
Shares                   Stock Options       Voting Securities
------                   -------------       -----------------
<S>                      <C>                 <C>
11,710,000               0                   11,710,000
</TABLE>

                                      -12-