sswp1424.pdf

DIVISION OF THE HUMANITIES AND SOCIAL SCIENCES

CALIFORNIA INSTITUTE OF TECHNOLOGY

PASADENA, CALIFORNIA 91125

ACE: A Combinatorial Market Mechanism

Leslie Fine

Salesforce

Jacob K. Goeree

University of New South Wales

Tak Ishikida

Consultant

John O. Ledyard

Caltech

SOCIAL SCIENCE WORKING PAPER 1424

November, 2016

ACE: A Combinatorial Market

Mechanism

∗

Leslie Fine

†

, Jacob K. Goeree

‡

, Tak Ishikida

and John O. Ledyard

November 3, 2016

Abstract

In 1990 the South Coast Air Quality Management District cre-

ated a tradable emissions program to more efficiently manage the ex-

tremely bad emissions in the Los Angeles basin. The program created

136 different assets that an environmental engineer could use to cover

emissions in place of installing expensive abatement equipment. Stan-

dard markets could not deal with this complexity and little trading

occurred. A new combinatorial market was created in response and

operated successfully for many years. That market design, called ACE

(approximate competitive equilibrium), is described in detail and its

successful performance in practice is analyzed.

∗

To appear in Handbook of Spectrum Auction Design, Cambridge University Press

†

Salesforce

‡

University of New South Wales, Australia

OR consultant, Merced, CA

California Institute of Technology. John Ledyard would like to thank NSF for its

support under grants numbered 1216024-ICES: Large: Collaborative Research: Markets -

Algorithms, Applications and the Digital Economy and 1518941-NeTS: Large: Networked

Markets: Theory and Applications

1 Intro

At the time of the Clean Air Act of 1990, the Los Angeles basin was the only

region in the country classified as an extreme non-attainment area for exceed-

ing the National Ambient Air Quality Standards for ozone. Under pressure

at the national level from the Environmental Protection Agency (EPA), and

at the state level from the California Air Resources Board (CARB) to signif-

icantly reduce emissions, the South Coast Air Quality Management District

(SCAQMD) launched a program for trading permits in Nitrogen and Sulfur

Oxides (NOx and SOx) in the Los Angeles basin. That program was strongly

supported by environmental groups and large firms in the LA basin as the

most cost effective way of attaining the desired reductions. This program,

the REgional CLean Air Incentives Market (RECLAIM), was initialized in

October of 1993 and has been operating since early 1994.

The design of the tradable instruments was inevitably a compromise be-

tween regulatory interests and market efficiency. Regulators wanted to be

able to control the timing and distribution of emissions as finely as possible

with caps at many different locations and for many different time periods.

To create liquidity, market designers wanted as few instruments as possible

- a single aggregate cap would have been their preference. In the end, 136

different types of permits were created that could be used by a company to

cover their emissions and, thereby, avoid the costs of abatement. This meant

there were both substitutes and complements among the permits. Further,

the markets for each of these permits would be illiquid. That created a big

problem for the environmental engineers trying to choose between installing

expensive abatement equipment or buying a portfolio of permits.

Our description of RECLAIM in this subsection is taken liberally from Cason and

Gangadharan (1998). See also Fine (2001), and Carlson, et al. (1993) for more information.

At the request of a number of firms, a new combinatoric market design

was built and operated to help then and others deal with the complexities

that the RECLAIM program created. In this paper, we provide a description

and analysis of that market. There are three parts. In the rest of this section,

we provide more of the details of the RECLAIM program and describe the

problems that created for environmental engineers. In Section 2, we describe

the ACE-RECLAIM market design with special emphasis in Section 3 on

the algorithms that drove the market. Finally, in Section 4 we look at the

performance of that market.

1.1 The RECLAIM program

RECLAIM is targeted at two major pollutants emitted from stationary sources:

Nitrogen Oxides(NOx) and Sulfur Oxides(SOx). All facilities emitting 4 tons

or more (per year) of NOx or SOx from permitted equipment were included

in RECLAIM. Approximately 390 facilities were in the early NOx market,

which collectively represented about 65 percent of the reported NOx emis-

sions from all permitted stationary sources in the Basin. The SOx market

consisted of 41 facilities, which represented about 85 percent of the reported

SOx emissions from all permitted stationary sources.

Each facility in RECLAIM was allocated a certain number of RECLAIM

Trading Credits (henceforth RTCs or simply

permits

) for equipment or pro-

cesses that emit NOx or SOx. This allocation depended on the peak activity

levels for each type of permitted equipment between 1989 and 1992. Each

facility received an allocation for each year

between 1994 and 2000 based on

a straight line rate of reduction calculated from the starting allocation to the

allocation in the year 2000. For the years 2001 to 2003, the allocation levels

were decreased further. Allocations for each year from 2004 to 2010 were

A permit for 1998, for example, could only be used to cover emissions in 1998.

to be equal to the 2003 allocation unless the AQMD decided that further

reductions would be required. Average annual percentage reduction rates for

facilities ranged between 7.1 and 8.7 percent in the NOx market and between

4.1 and 9.2 percent in the SOx market (SCAQMD 1993). There is no bank-

ing allowed. At this point in the design there were 2x17 = 34 different types

of permits to deal with. But more were yet to come.

Based on solid experimental evidence, the SCAQMD realized that this

structure of permits would lead to extreme price volatility towards the end

of each year. In a good business year, the need for permits by all firms would

be high and at the end of the year prices could climb to as high as the fine

for emitting too much. In a bad business year, the need for permits by all

firms could be low and at the end of the year prices would drop, perhaps as

low as zero. This price volatility would wreak havoc with rational planning

efforts. To eliminate this problem, the SCAQMD adopted “cycles”. Permits

were identified by year and by cycle. There were 2 cycles; one beginning Jan

1 and one beginning July 1. As an example, 1994 cycle 1 permits could only

be used to cover pollution emitted from Jan 1 1994 to Dec 31 1994. 1994

cycle 2 permits could only be used to cover pollution emitted from July 1

1994 to June 30 1995. It was shown experimentally that such an overlapping

structure of permits would serve to mitigate the extreme price volatility. In

the end it was decided to accept a little more complexity in the number of

types of permits for the reduced complexity due to excessive volatility. There

were now 2x34 = 68 different types of permits. And yet more to come.

Due to regulatory worries about maintaining tight control over the dis-

tribution of pollution by the prevailing on-shore winds, the SCAQMD also

identified permits by zones. The idea was that upwind zones could sell their

permits to downwind zones but not vice versa. The SCAQMD originally

wanted 37 zones. But, because the economists warned about serious com-

plexities and thinness in trading, they settled for 2: an inland zone and a

coastal zone. Firms located in a coastal zone could only use permits identi-

fied as coastal. Inland firms could use either coastal or inland permits. In

the end, therefore, for perfectly good regulatory considerations, there were a

total of 136 different assets (68 per pollutant) that could be used to cover a

firm’s pollution: 2 pollutants (NOx and SOx), 2 zones (inland and coastal),

2 cycles, and 17 years (1994-2010).

Put yourself in the position of an environmental engineer dealing with

the complexities of the RECLAIM program. A typical exercise would have

the engineer deciding between installing abatement equipment or buying per-

mits. Suppose abatement equipment costs $B to install and has a lifetime of

T periods.

The equipment abates

units of emissions in period

. As an

alternative, the engineer can cover the same emissions

by using some col-

lection of the 136 permits. We let

be the amount of permit of type k that

can be used to cover one unit of emissions in t. For RECLAIM,

∈{

}

Suppose the engineer already has a portfolio of permits,

∈ <

To avoid

installing the abatement equipment she will have to buy a vector of permits

∈ <

such that

∑

and

∑

≥

where

is the

amount of permit

she will use to cover

If there is an active market for each of the 136 permits and a stable price

A period can be a year, a quarter, a half-year, etc. For purposes of this example, it

doesn’t really matter.

for each, she has a fairly easy decision. Let

= min

y,z

∑

subject to

∑

∀

(1)

∑

≥

∀

≥

∀

The last constraint eliminates short sales. (1) is a straight-forward linear

programming problem which is easy to solve. She installs the abatement

equipment if and only if $

−

≤

P <

−

pw,

she buys the vector

of permits

∗

that solves (1).

But such thick markets never existed. As noted by Cason and and Gan-

gadharan (1998), the program placed minimal restrictions on how permits

could be traded. Although the SCAQMD originally planned on putting out

contracts for the design and management of a market system, brokers lobbied

hard and succeeded in preventing that. Brokers suggested, without much real

evidence, that traders could rely on brokers to help bring buyers and sellers

together. RECLAIM brokers would thus bear the search costs for potential

traders, of course for a fee.

Instead of leaving the market entirely to brokers, however, SCAQMD

planners implemented an electronic bulletin board system (BBS) to help

RECLAIM participants find trading partners and reduce search costs. The

BBS was operated by SCAQMD, and anyone could obtain a password to

access their computerized network. The BBS allowed firms to indicate trad-

ing interest by electronically posting offers to buy or sell RTCs. Other firms

could then scroll through these offers and contact the offering firm to nego-

tiate a transaction. Prices were not posted.

It turned out, however, this was not enough to enable firms to manage

their environmental requirements.

1.2 The Environmental Engineer’s Problem

She must identify and pursue a sequence of deals from the SCAQMD bulletin

board: buying permits of type k without knowing for sure what price she will

be able to negotiate for permits of type, say,

′

. And she has to make the

decision now. A simple toy example illustrates the complications and risks

this type of thin market causes.

Example 1

(Permits as complements: the need for AND bids)

There are 2 markets: one for A and one for B. Bidder 1 is our engineer

who needs to buy both A and B. Bidder 2 is only in market A. Bidders 3 and

4 are only in market B. The amounts they want to buy or sell and their true

values for that transaction are in the following table.

Bidder

$

Amount of A Amount of B

400

- 50

- 180

- 30

- 120

- 20

It is important to remember, for this and other examples, that each bidder

knows only her own

$

value

and does not know those of the others.

If Bidder 1 has to participate separately in market A and market B, she

has to decide what her separate bids in A and B will be. Suppose she assumes

prices will be similar in the 2 markets and decides to bid 200 for 50 units in

each (or 4 per unit). Having done that, suppose she buys her 50 units of A

for 3 per unit or 150 total. So far so good. Now she must go into the market

for B. She has 2 options. If she is unable to complete a trade for B, resell

the A she bought and pay 400 to abate. Suppose she takes a loss from that of

L. The cost of this outcome is

5 +

per unit. That is how much she is now

willing to bid for B. But 3 and 4 are only willing to sell at a price greater

than 6. If

L >

she will pay something more than 6 for B. She will not

have to abate (the socially desirable outcome) but will have paid more than

400

for the permits. This is not a good outcome. If

L <

she will sell the

50 A and abate (the socially undesired outcome). She will also take a loss of

L and therefore will have paid more than

400

. This is not a good outcome.

So, no matter what she does at this point she loses. Whatever the ultimate

price of B, she paid too much for A.

She could have tried to negotiate harder when she bought A but if seller

2’s willingness-to-accept had been 5 and seller 4 and 5 had a willingness-to-

accept of 2, this would lead her to not buying A initially. After buying B

she could go back to seller 2, but he might have completed another deal with

someone else. No matter how she plays it she may end up not buying permits,

which is the undesired outcome.

This is certainly a contrived example but imagine trying to string together

trades for 15 different assets in 15 different markets. The example illustrates

the exposure problem

that the environmental engineer faces when she must

deal in separate

markets for each type of permit or engage in a sequence of

separate

, complex multi-lateral negotiations. A permits and B permits are

complements, like left and right shoes. Getting one without the other is no

The exposure problem was identified and discussed at some length in by Bykowsky,

Cull and Ledyard in 1995. The published version is Bykowsky et. al. (2000).

help. A buyer who has to deal in separate markets for A and B is

exposed

to the risk of incomplete transactions. To protect for this she may either bid

lower than she really would be willing to or she may not participate at all.

This destroys potential gains from trade and reduces trade below that which

would be optimal.

Example 2

(Swaps and Endowments: the need for OR bids)

Continuing Example 1, suppose Bidder 1’s company had an initial alloca-

tion of permits from the SCAQMD and is willing to commit some of them to

this project. Suppose she has 60 of A and 40 of B.

If she is going to use per-

mits instead of abatement equipment, she will have to buy the following stream

of permits:

(

−

10)

. As in Example 1, she has a problem in deciding how

much to offer in market A and how much to bid in market B. This is a swap

she is willing to enter into if and only if

−

+ 10

≤

400

−

+ 50

≤

400

What she would like to do is to enter a deal to “sell

10 A and buy 10 B if

+ 50

≤

400

” OR “sell 60 A and 40 B if

+ 50

400

” but not both. But the thin market won’t allow such

deals. Instead she must negotiate separately for A and B. Suppose when she

goes to the A market, the price for A is

$

4.50 and, believing that the price of

B will be equal or greater than that, she sells her 60 permits. Then suppose

that when she gets to the B market she learns the price for B is

$

1.50. She

will have to complete her sale of the 40 B at that price and install abatement

equipment, paying out

400

−

270

−

60 = 70

. If, instead, she had only sold 10

A at the price of

$

5 and bought 10 B at the price of

$

1.50, she would have

made

$

30. The difference is

$

100. And she may be the least cost abater,

which makes this bad not only for her but also for society.

When markets are thick and prices are stable, buyers and sellers with

This is as if A are permits for 1995 and B are permits for 1996 and the firm is given

a declining initial allocation.

complex needs are no more at risk than buyers and sellers with simple needs.

But when markets are thin and prices are unpredictable, buyers and sellers

with complex needs are at risk. Gangadharan (2000) has estimated that

these problems were particularly bad in the early years of the RECLAIM

program. The program consists of firms with very different industrial struc-

tures, which use different technologies to produce very heterogeneous prod-

ucts which means that matching a single buyer with a single seller with

coincident wants is extremely unlikely. She found that these problems re-

duced the probability of trading by about 32%.

Individuals faced with this risk of incomplete trading often turn to bro-

kers who generally claim to be able to find the collection of trades that will

satisfy the bidder’s price point. That is what happened with RECLAIM.

The brokers were more than willing to help, but they charged 40% on each

side of a trade, did not publish their prices, and did not let firms know what

the alternatives in the market really were. They operated dark markets.

After their experience with brokers, a collection of the firms that had been

deeply involved in the design of RECLAIM came to us and asked that we

consider creating a marketplace that would help them. Without knowing the

language or even the exact concept, what they described as desirable was a

combinatorial exchange

. They wanted a transparent market place into which

A quote from Duffie (2012) shows how pervasive the problem is. “Over-the-counter

(OTC) markets for derivatives, collateralized debt obligations, and repurchase agreements

played a significant role in the global financial crisis. Rather than being traded through

a centralized institution such as a stock exchange, OTC trades are negotiated privately

between market participants who may be unaware of prices that are currently available

elsewhere in the market. In these relatively opaque markets, investors can be in the

dark about the most attractive available terms and who might be offering them. This

opaqueness exacerbated the financial crisis, as regulators and market participants were

unable to quickly assess the risks and pricing of these instruments.” This also happened

in the early years of RECLAIM.

they could submit bids that expressed their complex needs and willingness-

to-pay and from which they would get fair trades at understandable prices.

The rest of the paper is about the market we built for them.

2 ACE-RECLAIM

The market, designed for RECLAIM, was initially operated under the name

Automated Credit Exchange (ACE). The design was based on research con-

ducted at Caltech in 1993.

The actual internet-based implementation was

built by a team from Net Exchange that included Takashi Ishikida, Charles

Polk, and Lance Clifner. It utilized an iterated combined-value call market to

trade in quarterly trading sessions. We believe that it was the first internet-

based commercial exchange. ACE-RECLAIM opened in April of 1995 and,

by 1999, it had accounted for approximately 90% of all priced trades in the

RECLAIM market.

A functioning market has two main pieces: a market mechanism (the

inside piece) and a market process (the outside piece). The inside piece in-

cludes the bid forms, the winner determination algorithm and the pricing

algorithms. The outside piece includes the participation rules, bidding rules,

what is displayed to bidders and when, stopping rules, enforcement rules,

etc. We will first describe the outside piece of the ACE-RECLAIM market.

The market flowed as follows:

•

Qualification and escrow

The first step in any market is the qualification of the market par-

ticipants. Since the SCAQMD rules allowed anyone to hold permits

For a detailed description of the design and experimental test-bedding of the ACE-

RECLAIM mechanism, see Ishikida et al (2001).

For more on participation in ACE-RECLAIM, see section 4.1.

and therefore to trade them, anyone was allowed to participate in the

market. But combinatorial markets create a problem that separated

markets do not. Trades are likely to be multi-lateral and complex. This

means that if anyone defaults by not delivering cash or permits at the

end of the process, then many winners may find their trades invali-

dated. To avoid this unfortunate outcome, ACE-RECLAIM required

any participant to provide in escrow, before the market opened, the

cash they would be willing to spend and the permits they were willing

to sell. ACE-RECLAIM then used these data to provide constraints

on the bids the bidders were allowed to make. In particular, no bidder

could bid in a way that would violate the cash and permit bounds,

no matter what bids were accepted. This removed the possibility of

default.

•

Bid submission

Bids were submitted in two ways: either online, through a custom

Windows bidding interface on a computer connected via a modem to

the ACE-RECLAIM computer, or via fax to the market manager who

would then input the bids herself.

•

Provisional winners, prices, and payments.

After bids are submitted, the ACE-RECLAIM computer calculated

provisional winners, prices, and payments using the market mechanism

described in section 3.

•

Stopping Rule, Resubmissions, and the Improvement Rule

ACE-RECLAIM was run as an iterative process. It proceeded in

rounds. At the end of each round (once provisional winners, prices, and

payments were announced) a stopping rule is calculated. The stopping

rule for ACE-RECLAIM was very simple: (a) there must be at least

3 rounds, (b) after round 2, if surplus and volume do not increase by

at least 5% from the previous round, the market will end, and (c) the

market will end after round 5 if (b) has not taken place. If the rule is

satisfied, the process goes to Clearance and Settlement to finish up.

If the rule is not satisfied, the process returns to allow more bids. There

are two features of ACE-RECLAIM that come into play at this point.

All winning bids must be re-submitted as they are. They can then be

improved on. Improvement can happen in several ways. Without going

into too much detail, improvement usually means (a) for a bid to buy,

a higher willingness to pay is entered or (b) for a bid to sell, a lower

willingness to accept is entered.

Remark 1

ACE can also be run as a one-shot sealed bid or a con-

tinuous mechanism. Each such version can be used with a variety of

stopping rules, e.g. based on eligibility and activity similar to the FCC’s

SMR rules or based on the increase in surplus over the last round (e.g.

stop if less than 5%).

•

Sunshine

An important aspect of combinatorial trading is that often bids of sev-

eral individuals have to fit together, like pieces of a jigsaw puzzle, in

order for them to trade. Thus it is often important to know what

others are willing to trade or to show others what you are willing to

trade. ACE-RECLAIM allowed individual bidders to choose how much

of their own bids would be made public. They could choose (a) nothing,

(b) quantities of permits only, or (c) quantities of permits and dollar

amounts bid. This was called, respectively, (a) no sunshine, (b) partial

sunshine, and (c) sunshine. ACE-RECLAIM is an iterative process and

many bidders chose (a) in early rounds and (b) or (c) in later rounds

as they became more desperate to find a match of some kind.

•

Clearance and Settlement

Once the stopping rule comes into play, ACE-RECLAIM takes the re-

sults of the last round and implements these: sending orders to the

RECLAIM database for the appropriate reallocation of permits and

sending orders to the escrow holder for the appropriate reallocation of

cash between accounts.

3 ACE

ACE is the market mechanism (the inside piece) for ACE-RECLAIM. ACE

is an acronym for Approximate Competitive Equilibrium, the philosophy be-

hind the market mechanism design. It is a generalization of the well-know

Uniform Price Double Auction (UPDA) which produces high efficiencies in

simple markets.

UPDA is usually run like a sealed bid auction. Subjects

submit bids (

P,Q

)

Q >

0, it is a buy order to be read as “I will buy

up to

units of the good for any price less than or equal to

”. If

Q <

then it is a sell order to be read as “I am willing to sell up to

units of the

good for any price greater than or equal to

”. After all bids are submitted,

UPDA picks winners by choosing that set of trades that would maximize the

reported surplus. The price at which all transactions take place is the mid-

point between the marginal units (both accepted and rejected). All winning

buyers pay less than (sellers receive more than) or equal to their bid. It is

the same price for all, there is no subsidy or tax for the market, and there is

a strong incentive to reveal one’s true willingness-to-pay (or accept) except

at margin. Since the probability that any bid is marginal can be very low,

this gives ACE a serious shot at being virtually incentive compatible.

See Smith et.al. (1982), Friedman (1993), and McCabe et. al. (1993).

Since the ACE market mechanism is to operate in a world that is more

complex than UPDA was designed for, the bid structure, winners determina-

tion, and price determination pieces all had to be modified. The mechanism

allows bidders to submit contingent orders. The winners determination algo-

rithm then maximizes reported surplus, as in UPDA. The pricing algorithm

approximates the UPDA price rule but still leaves bidders as well off after as

if they had not participated.

3.1 Bids

The mechanism allows bidders to submit contingent orders. These can be

ANDs (I want A if and only if I can also secure B) or ORs (I want either A

or B).

Participants submit bids that are numbered

= 1

,...,N

3.1.1 AND Bids

The basic bid of ACE is an AND bid. It allows a bidder to express interest

in a collection of complements, all of which are needed. An AND bid is in-

tended to protect the bidder from exposure in situations like Example 1.

Definition 1

A simple AND bid numbered i is

(

)

where

∈<

∈

, and

∈

. K

is the number of commodities.

The bid is read as “ I will pay up to

for the vector

as long as

≤

1”

The vector

∈ <

contains the quantities offered or demanded, where

is the number of commodities. If

0, then

units are demanded.

0, then

units are offered for sale. It is not required that all

be positive or negative, i.e. swaps are allowed. The number

∈ <

is the

maximum amount the bidder is willing to pay for

. (

is the minimum

amount a seller is willing to sell for if

) The number

∈

1] is the

minimum fill number.

When

= 0, the bid is similar to a (

P,Q

) bid in a uniform price auc-

tion where bidders are willing to accept any amount

≤

at a payment

≤

Pq. F

indicates a minimum fill requirement which introduces non-

convexities and discontinuities into the design problem. This is the most

challenging part of the ACE design. When

0, the simple UPDA ap-

proach won’t work, particularly the pricing.

Example 3

(Minimum Fill required #1)

Consider a market with a single commodity labeled A, with 1 buyer and

3 sellers. Buyer 1 is willing to pay 20 for 3 units but does not want to pay

anything if he gets less than 3 units. That is, he requires his order be filled

at the 100% level or not at all.

Bidder

$

Amount of A % fill required

100

- 2

- 1

- 4

-1

- 10

-1

Gains from trade are maximized if all 4 participate in the deal. Even

though bidder 4 requires

$

10 per unit and bidder 1 is only willing to pay

$

per unit, bidder 4 makes the deal possible for bidders 2 and 3 and should be

included.

The minimum fill requirement creates several problems here. First, if 1

bids

$

8 per unit, 4 will never trade and 1 will not get the 3 units he wants.

Second, if 1 agrees to pay 4 any amount greater than

$

10, both 2 and 3 would

want the same deal. But then 1 cannot afford to pay every one at the rate of

$

10/unit. Often this configuration of values and desires will lead to no trade.

The

$

8 in potential gains from trade is lost.

A standard thin market has difficulty dealing with minimum fill require-

ments. In the above example, the standard market makes it difficult to

include Bid 4 in the final allocation even though it should be. In our next

example, the standard market makes it difficult to exclude someone from the

final allocation even though they should be.

Example 4

(Minimum Fill required #2)

In this example, there is an additional buyer and Seller 4 has a lower

reservation price.

Bidder

$

Amount of A % fill required

100

- 2

- 1

- 4

-1

- 6

-1

Here the allocation that maximizes the gains from trade would include

1,2,3, and 4 and exclude 5. The price would probably be somewhere between

6 and 8. But 5 is more than willing to pay upto

$

10 and so might work hard

to be included in the allocation. In fact, at that proposed price, 5 could offer 2

a deal. 5 can offer to buy 2’s unit for

$

9. There is no price at which 5 is not

willing to buy and 1 is willing to buy. Often this configuration of values and

desires will lead to a single trade between 1 and 5 yielding a surplus of

$

Whereas the maximum surplus possible is

$

12. Potential gains from trade

are lost.

3.1.2 OR bids

An OR bid allows a bidder to express interest in a collection of substitutable

possibilities. An OR bid is intended to protect a bidder from exposure in

situations like Example 2.

Definition 2

An OR bid numbered

{

(

)

}

The bid is read as “I will accept one and only one

∈

in which case I will

pay up to

as long as

∈

1].” If

= 1, then this is exactly the

same as the AND in section 3.1.1.

Each (

) is a simple AND bid. An OR bid requires that, at

most, only one of these be accepted. That means there are

∀

∈

such

that

∈

[

,δ

]

∑

≤

and

∈{

}

3.1.3 Characteristic Bids

A special OR was designed for ACE-RECLAIM to give environmental engi-

neers a user-friendly way of expressing interest and value over a wide range of

substitutable possibilities. Here we provide a slightly more general version.

As we described in Section 1.2, the environmental engineer has a vector of

permits

∈ <

and wants to cover a stream of pollution

∈ <

. The

engineer needs to buy a vector of assets

such that

∑

∀

and

∑

≥

∀

. And, if they want to avoid short sales, they would

add the constraint that

≥

The characteristic bid generalizes the OR bid to allow an infinite variety

of possible satisfactory trades to be considered without exposing the bidder

to the risk of having more than one of those options active at a time.

Definition 3

A characteristic bid numbered

(

)

A characteristic bid is to be read as “I will accept one trade

as long as

≥

∑

≥

and

∈

[

1] in which case I will

pay up to

for it.

= 1, then the characteristic bid lets the market know that the engi-

neer will buy any combination of assets

as long (i) as she can add them to

her endowment

in a way that covers

and (ii) it costs her no more than

her abatement costs, $B. She leaves it to the market to decide what works.

= 0, then the engineer is also allowing the market to consider

buying her endowment

as long as she is paid at least $0. If there are prices

then I would want to agree to that trade if and only if (0

−

) solved

max

(

)

−

subject to

≥

∑

≥

and

∈

1]. In particular, letting

= 1, this means that she would agree to

the trade if and only if

≥

−

where

solves (1). As we will see

below, the ACE market mechanism algorithms are designed with exactly this

in mind.

Remark 2

A characteristic bid is a generalization of a simple bid. Suppose

(

b,x,F

)

is a simple bid. Consider the characteristic bid

(

B,A,e,w,G

) :=

(

b,I,x,

)

This bid agrees to pay up to

for any

such that

≥

fx.

Since

is the dominant possibility this is just another form of a simple

bid.

3.2 Winners Determination

Once all bids are submitted, a winners determination algorithm determines

what trades will be matched and implemented. For ACE, winners are de-

termined by maximizing the ”reported surplus” of the trades subject to the

restrictions imposed by the bidders and subject to no excess demand.

Definition 4

(Winners Determination)

Let

{

AND bids

}

. Let

{

OR bids

}

. Let

{

characteristic

bids

}

. The

winner determination problem

is:

= max

(

f,y

)

∑

∈S∪Z

∑

∈O

∑

∈

(2)

subject to

∈{

}∪

[

for all

∈S∪Z

(3)

≥

∑

≥

for all

∈Z

(4)

∈

[

,δ

]

,δ

∈{

}

∑

∈

≤

all

∈

all

∈O

(5)

∑

∈S

∑

∈Z

∑

∈O

∑

∈

≤

∈

(6)

(3) is the minimum fill requirement for all bids except ORs. (4) is the restric-

tion placed by characteristic bids. (5) is the restriction placed by OR bids.

(6) is the requirement that there be no excess demand. In the RECLAIM

ACE market, if

∑

0 at the optimum, the transactions were made and

the un-transacted credits were retired. That is, free disposal was possible for

the market. We retain that feature here.

Remark 3

For ease of computation, the algorithm actually split the mar-

ket into disjoint segments (no overlapping bids). This also aided the price

computations which we pick up in the next section.

Remark 4

Maximizing surplus is not the only rule one might use. For ex-

ample, if one is interested in extracting revenue from the mechanism, then

maximizing surplus is rarely the best strategy. But for now we stay with

surplus maximization.

We will need to identify winners and losers as we proceed.

Definition 5

Let

(

∗

)

be the values that solve (2) and let

∗

∑

∈

∗

for each

∈O

. The set of

winners

is denoted by

{

∗

}

The set of

losers

is denoted by

{

∗

= 0

}

. Those winners for whom

< f

∗

will be referred to as

marginal winners

3.3 Pricing

ACE pricing is about (a) providing useful signals to the market that reflect

aggregate demand and supply, (b) not extracting any revenue, (c) achieving

some measure of incentive compatibility, and (d) not rewarding inflexible bid-

ders (i.e. those for whom allowing

= 0 in (2) would increase the surplus).

Ideally, all of this can be accomplished if we can find competitive equilib-

rium prices that support the allocation found by the winners determination

problem.

3.3.1 Competitive Equilibrium Prices

Competitive equilibrium allocations and prices satisfy two conditions: (i)

each individual’s allocation is just what they would want to buy at those

prices and (ii) there is no excess demand. For ACE, the bids are the indi-

viduals. We want prices that support the winners determination allocation

as a competitive equilibrium. They satisfy

ex-post self-selection

, or incentive

compatibility, for the bidders.

For simple bids, competitive equilibrium prices

would satisfy

−

πx

≥

0 if

∈

and

−

πx

≤

0 if

∈

. For other bids, things are a little more

complex.

For OR bids, let

∗

0 in the winners determination solution; that is,

is the winning part of the OR.

∗

= 0

for all

. Prices

would be

regret-free if (a)

−

πx

≥

0 and

−

πx

= 0 if 0

< f

∗

1 and (b)

−

πx

≤

∗

−

πx

∗

for all

Note that if

is a winner with

These are also sometimes called

no arbitrage

no re-contracting

constraints.

∗

= 1, this does not require

to be a loser (i.e.

−

πx

0) only that

it not be as good as

at those prices. It does imply that if

∑

∈

∗

= 0,

then all the

bids should be losers at the prices

For characteristic bids, let the solution to the winners determination prob-

lem (2) be (

∗

). Prices would be regret-free if

∗

−

πx

∗

≥

−

πx

for all

such that

≥

∑

≥

∈

[

Remark 5

For RECLAIM Zone free bids, the restriction to regret-free prices

was implemented with the constraint that the inland price be less than or equal

to the coastal price. Because inland credits could not be used to cover coastal

emissions, it imposed a simple requirement on the prices of the two zones

no matter what year-cycle is involved. Only the inland firms care about the

relative prices. If the coastal price is less than the inland price, inland firms

would want to only buy coastal credits, thus driving the price up. If the inland

price is less than the coastal price, the coastal firms could not drive the inland

price up. No-regret prices are also arbitrage-free prices.

The no-arbitrage conditions are:

•

If there are

k,k

′

,l,i

such that

′

and

′

then

′

•

If there are

k,k

′

,l,i

such that

′

and

′

= 0

then

≤

′

•

If there are

k,k

′

,l,i

such that

′

and

′

then

′

•

If there are

k,k

′

,l,i

such that

′

and

′

= 0

then

≥

′

If the

and

did not satisfy these then

would not be a cost-minimizing

coverage of

at those prices.

Definition 6

(competitive equilibrium prices)

Let

(

∗

,δ

∗

)

be the values of

that solve the winner determination

problem (2).

Competitive equilibrium prices,

, satisfy the following:

∗

(

−

)

≥

(

−

)

for all

∈

[

∈S

(7)

∑

∈

∗

(

−

πx

)

≥

∑

∈

(

−

πx

)

for all

,δ

such that

(8)

∑

∈

≤

∈

[

,δ

]

,δ

∈{

}

, i

∈O

∗

−

πx

∗

≥

−

πx

for all

(

)

such that

(9)

∈

[

≥

∑

≥

for all

i, i

∈Z

[

∑

∈S

∗

∑

∈Z

∗

∑

∈O

∑

∈

∗

] = 0

(10)

≥

for all

(11)

(7) - (9) are the regret-free conditions on bidders. They require that

ex post

each bid is allocated in a way that maximizes the bid’s surplus at those

prices subject to the bid’s restrictions. (10) is Walras Law which requires

that

= 0 when there is an excess supply of

. These conditions, along

with

no excess demand

(6) from the winners determination problem, imply

that the winners determination allocation and the prices

are a competitive

equilibrium for the economy described by the bids.

There are two possible problems at this point. Competitive equilibrium

prices may not exist. And, even if they do exist, they may not be unique.

∗

is relevant for characteristic bids.

∗

is relevant for OR bids.

∗

is relevant for all

types of bids.

Non-uniqueness:

If (2) is convex, prices satisfying (7) -(11) exist.

The

dual variables of the linear-programming problem will serve as these prices.

But they may not be unique. There are 2 reasons.

One, in a thin market when a package matches another package, the range

of prices satisfying no-regret can be wide. Consider the following example.

Example 5

(Opposing swaps)

There are 2 AND bids.

Bid

$

Amount of A Amount of B

-1

-3

-1

Bid 1 indicates, for example, that some one is willing to pay 3 to swap 1

unit of

for 1 unit of

. In this case,

and

are not separately identified

and all we can conclude is that

−

= 3

. This is not a problem, since no

bidder cares which particular price vector is selected from those.

Two, the bounds in definition 6 may not be tight. This occurs for exam-

ple if there is no marginal winner.

Example 6

(Single asset - No marginal winner)

Bid

$

Amounts

$

/unit

500

-400

-500

0.8

For this example, any price between

$

0.80 and

$

1 will be a competitive

equilibrium price. This is a problem, because the price selected determines

the distribution of the surplus among buyers and sellers.

Since (2) maximizes surplus, and “preferences” are quasi-linear, the winners allocation

is Pareto-optimal. We can therefore apply the second welfare theorem to establish the

existence of prices supporting that allocation.

To deal with non-uniqueness in prices, ACE chooses the prices that max-

imize the winning bidders’ minimum per-unit surplus. This is the intuitive

equivalent to Myerson-Satterthwaite’s (1983)

-double auction when

= 1

It equalizes the per-unit surplus between buyers and sellers on the margin.

In example 6, ACE will set the price to $0.9.

Non-existence:

Non-existence is way more serious than non-uniqueness.

The prime cause of the non-existence of equilibrium prices is inflexibility due

to a minimum fill requirement. In this section, we show how the inflexibility

causes the non-existence through examples and discuss how it is resolved.

For simplicity, the examples are set in a single asset market.

Example 7

(Excess supply at winners determination)

In this example, it is possible to find a regret-free price at the winners

determination allocation but payments will not balance.

Bid

$

Amount Min. scale(%)

$

/unit

2500

2000

1.25

500

1.00

-1500

-3000

100

0.50

If all orders were flexible, a competitive equilibrium would exist at the

price of

$

0.5 per unit and 500 units of order 3 would not trade. Because

of the sell order’s inflexibility, the market must absorbs 500 units of excess

supply. But, because of this imbalance between the amounts bought and the

amounts sold, no single price will allow balance of all payments and charges.

With inflexibility someone must pay for this extra 500 units, or no trade will

occur.

In Example 7, if the extra 500 units were not taken by the market maker,

no trade would occur. So it is not unreasonable to have Bids 1 and 2 pay

for it. A natural way to do that, while preserving some measure of incentive

compatibility, is to charge buyers a higher price than is paid to sellers. To

implement that, we would charge each buy unit at $0.8181 and pay each

sell unit at $0.68182. But this rewards the inflexibility of Bid 3. If they

were perfectly flexible, they would gain a surplus of 0 and get only 2500

units. If they are inflexible and we used this pricing scheme, they would get

3000

18182 = $545

476. An alternative would be to pay B3 at what she

bid, $0.50/unit, and charge the buyers $1.20. But this punishes not only the

inflexible part of Bid 1 but also the flexible part. A better alternative is to

pay the inflexible part (500 units) at $0.50 and then split the prices in a way

that equalizes the per-unit surplus at the margin. In Example 7, this would

mean each buyer would be charged $0.80 and the seller would be paid $0.70

for the 2500 flexible units and $0.50 for the 500 inflexible units. ACE does

something similar to this.

Example 8

(Excess supply from AND bid)

In this example, we illustrate another way in which a single price can be

found to satisfy no-regret but will not balance payments. There are no mini-

mum fill requirements here.

Bid

$

Amount of A Amount of B

- 100

- 30

300

-100

- 75

100

All these bids will win in the winners determination problem. But there

will be an excess supply of 10 units of of B. It is easy to find prices that

satisfy no-regret for all bids. For example,

= 2

= 9

will do the job. But

because there is an excess supply, the market will absorb the 10 units and, as

in example 7, someone will have to pay the

10 = $90

to Bid 1.

ACE will deal with this by splitting the buy and sell prices and then choosing

them so as to equalize the minimum per unit surplus across orders.

Example 9

(Incompatible surplus requirements)

In this example it is not even possible to find a regret-free price at the

winners determination allocation.

Order

$

Amount Min. scale(%)

$

/unit

2000

100

1.00

-425

-500

0.85

-980

-1000

0.98

-525

-500

1.05

Sell order 4 is allocated because buy order 1 is an all-or-none order and

there is enough surplus from the part of trade made among orders 1,2, and

3 to compensate for the surplus loss resulting from matching a part of order

1’s demand and sell order 4. Without order 4 no trades will occur so 4 is

included in the winners determination allocation.

Since sell order 4 asks more per unit than buy order 1 bids per unit, no

single price can satisfy no-regret for both 4 and 1. For allocations in these

examples, individual prices will have to be charged to some bids in order

to satisfy no-regret. One option is to pay 4 what they bid,

$

525, and then

split the buy and sell prices for the others to pay that. Since Order 1 is

inflexible, they would pay

$

1 per unit (as in example 7 we don’t want to

reward inflexibility) while Orders 2 and 3 would be paid

$

0.9833 per unit.

3.3.2 The ACE pricing algorithm

As we found out in the previous section, allowing bids that are able to express

bidders’ preferences opens up the possibility that competitive equilibrium

prices will not exist. So one must settle for something less. In this section,

we describe how ACE handles this.

We want prices that (a) provide useful signals to the market that reflect

aggregate demand and supply, (b) do not extract or inject any revenue into

the process, (c) achieve some measure of incentive compatibility, and (d) do

not reward inflexible bidders. ACE accomplishes (a) by finding prices that

are “as close as possible” to competitive equilibrium prices, accomplishes (b)

by requiring payments and receipts to add up to zero, accomplishes (c) by

ignoring losing bids

and choosing prices between all marginal winning bids

(a double auction approach), and accomplishes (d) by paying inflexible bids

at exactly what they bid.

ACE first identifies those inflexible bids or parts of those bids that pre-

vent regret free prices from existing, as for example Bid 4 in Example 9.

Those inflexible bids are set aside and will be paid or pay at what they bid.

There is now a price that is regret-free for the remaining bids. Unfortunately,

payments may not balance at that price, as happens in Example 7. So ACE

then splits the prices into a price vector for buyers,

, and a price vector for

sellers,

, and searches for a pair that (i) satisfy no-regret for the remaining

bids (or parts of bids), (ii) maximize the minimum per unit surplus for all

In a thick market, losing bids can be used to drive incentive compatibility by leading

winning bids to reveal their true values. In thin markets, losing bids can be used to

manipulate prices and detract from incentive compatibility. Since ACE is designed for

thin markets (it is not needed in thick markets), ACE ignores the losing bids from the

winners determination problem (2) when determining prices. ACE ignores both losing

simple bids (those with

= 0) and the losing parts of OR bids (those with

= 0).

of the remaining bids, and (iii) balance payments and receipts of all bids

(including those set aside).

Step 1:

Ignore losing bids and the losing parts of OR bids.

Begin with the allocation (

∗

) from the winners determination prob-

lem (2). Let

⊂

be the set of allocated orders, (those

∈ S ∪Z

with

∗

0 and those

∈ O

with

∗

0 ). Let

⋂

let

⋂

For

∈ S ∪Z

∗

. For

∈ O

∑

∈

∗

For

∈ S

∗

. For

∈ O

∑

∈

∗

For

∈ Z

∗

and

∗

Step 2:

Determine which units are extra-marginal.

To determine those parts of the winning bids that are inflexible, ACE

solves the following

fully flexible winners determination

problem.

max

(

g,x

)

∑

∈

subject to

|≤|

∈

≥

∑

≥

∈

∑

∈

S∪

∑

∈

≤

∈

(12)

≤

∈

Let (

) be the solution of (12). The inflexible part of bid

is (1

−

)

for

∈

S ∪

, and is

−

for

∈

ACE sets this part of these

orders aside. They will be filled and they will pay (1

−

)

. Prices on

A characteristic bid may not be itself inflexible but a part of it may be matching an

inflexible part of another bid.

the rest of the orders, called the fully flexible orders, will have to “pay” for

∑

∈

−

)

. This usually requires that prices be split into buy and

sell prices.

Step 3:

Find a vector of buy prices and a vector of sell prices that is regret-

free for as many of the fully flexible orders as possible, that balances all pay-

ments, and maximizes the minimum surplus per order.

Let

{

∈

}

and

∑

∈

−

)

is the set of bids

with a fully-flexible component.

is the contribution to the total payment

from the units paying at their bid/ask prices.

For any vector

, let

:= (max

{

}

max

{

}

,...,

max

{

}

) and

−

:= (min

{

}

min

{

}

,...,

min

{

}

is the amount of asset

potentially bought at the market (buy) price, and

−

is the amount of

asset

potentially sold at the market (sell) price.

Solve the following pricing problem.

max

(

m,p

)

(13)

subject to

−

∑

∈

(14)

−

≤

−

for all

such that

≥

∑

≥

∈

∩

(15)

∑

∈

(

∩

)

(

−

) +

∑

∈

∩

(

−

) +

= 0

(16)

≥

m,i

∈

≥

∈

In (14),

is the per-unit surplus that this bid will receive if the prices are

(

). To be precise, each of the terms in (14) should be multiplied by

, but, since they all just cancel, we are leaving them out. The regret-free

condition for all bids is contained in (14) when

≥

(15) is the regret-

free condition for

∈

. It should be noted that the complete statement is

−

(

)

(

−

)

≥

−

(

)

(

−

). But the

cancels

out. Finally, (16) is the requirement that all payments and receipts balance.

Remark 6

Note that (15), as well as (19) below, really involves an infinite

number of constraints that define a convex set. As pointed out in Remark 5,

for the RECLAIM implementation we were able to convert (15) to a finite

set of constraints on the prices. Each application requires its own conversion.

We do not have a general approach to accomplishing that.

If there is no inflexibility, then

= 0, and

in the solution to (13).

That is, a competitive equilibrium price will be found.

Step 4:

Check to see if appropriate prices have been found. If not, set aside

more bids and repeat.

A) If the value of the objective function of (13) is nonnegative, ACE

is done with this phase. ACE then enters into a clearance and settlement

phase, determining what is allocated to each bid and how much they pay or

are paid. We describe that process in Section 3.3.3.

B) If the value of the objective function of (13) is negative, then an ap-

propriate market price system does not exist because there is not enough

surplus at the margin to pay for the inflexible parts of the winning bids.

This would be the case, for example, if Bid 2 in Example 7 were $275 for 500 units or

$0.55 per unit.

In this case, ACE chooses some more units/orders to set aside and to pay at

their bid/ask prices and then recomputes. This iterates until ACE finds an

appropriate market price system for those bids that have not been set aside.

After the

-th iteration, there are two sets of orders.

is the set of the

orders which have been set aside and which will pay at their bid. An order

is (

)

. H

is the set of orders, or parts of orders, which have not

yet been set aside. There are two types of orders in

: simple orders and

cycle-zone free orders (

) and characteristic orders (

is set to be

At the

+ 1-st iteration, we solve

max

(

m,p

)

subject to

−

∑

∈

(17)

−

∈

(18)

−

≥

−

for all

such that

≥

∑

≥

∈

∩

(19)

∑

∈

(

∩

)

(

−

) +

∑

∈

∩

(

−

) +

∑

∈

= 0

(20)

≥

m,i

∈

≥

∈

If the value of the objective function is nonnegative, then ACE is done with

the pricing computation and goes to clearance and settlement (see Section

3.3.3). If the value of the objective function is negative, then the orders

that attain the minimum per unit surplus among the orders in

are now

removed from

and added to

to get

and

is empty, the surplus distribution is determined and ACE goes to

clearance and settlement.

Otherwise ACE repeats Step 4.

3.3.3 Payments

When the ACE pricing algorithm is finished, there are two sets of orders,

and

, and two market price vectors,

and

. The orders in

will pay

what they bid. The orders in

will pay at the market prices.

We perform an extra step to determine the orders that are

truly

attaining the mini-

mum per unit surplus. The step is necessary because of the non-uniqueness of prices; at

some prices more orders can attain the minimum surplus than at other prices.

Let

be the value of the objective function of LP (17). Let

min

be the set of orders

whose per unit surplus

s are found equal to

. Then solve the following LP for each

min

max

sub. to

≥

∈

min

all the constraints in (17)

If the value of the objective function of the above is

, order

is considered attaining

the minimum per unit surplus at the

-th iteration.

There still is a chance that the price is not uniquely determined after the surplus

distribution is determined because bids are as in Example 5. In such a case we choose

prices that support the surplus distribution and are averaged. Suppose a buy order of

$1000 for 500 units each of items A and B matches a sell order of $900 for 500 units each

of items A and B. The per unit surplus of each order is $0.5. This surplus distribution

can be achieved, for example, (

= $19

= $0). We choose (

= $9

5). This

‘averaging’ is often consistent to the reference price information made available to traders

in early round when there was no trade because asking prices by sellers are higher than

bid prices by buyers. Suppose the buyer’s bid is $900 and the seller’s ask is $1000 in the

example in this footnote. If there are no other orders involving assets A and B in the

market, $0.9 is returned as the highest average bid price for both assets A and B and $1.0

is returned as the lowest average ask price for A and B.