text:
# THE BNL MUON ANOMALOUS MAGNETIC MOMENT MEASUREMENT

## 1 Introduction

A precision measurement of the muon anomalous magnetic moment, $`a_\mu =(g2)/2`$, is a sensitive test of physics beyond the standard model. Because contributions to the muon anomaly from known processes (see Fig. 1), such as QED, the weak interaction, and hadronic vacuum polarization (including higher-order terms) are believed to be understood at the sub-ppm level, any significant difference between experiment and theory suggests a yet unknown, and thus not included, physical process. $`^\mathrm{?}`$ Conversely, agreement between theory and experiment can set tight constraints on new physics. Many standard model extensions have been postulated; of these, quite a few would manifest themselves in additional contributions to $`a_\mu `$ at the ppm level. This indirect method of probing high-mass and short-distance physics is being used by the Brookhaven E821 Collaboration $`^\mathrm{?}`$ in a new measurement $`^{\mathrm{?},\mathrm{?},\mathrm{?}}`$ of $`a_\mu `$. The experimental work is complemented by an aggressive effort by others to improve the precision of the standard model theory. In the near-term future, and generally in advance of the direct-discovery possibilities at the Tevatron or the LHC, both experiment and theory should achieve relative precision near or below 0.5 ppm.

The Collaboration recently reported $`^\mathrm{?}`$ a 1.3 ppm precision measurement of $`a_\mu `$ based on data obtained in the 1999 running period. A summary $`^\mathrm{?}`$ of the most up-to-date theoretical information implied a deviation from theory by $`2.6\sigma `$. Subsequently, re-examinations of the 1st-order hadronic vacuum polarization (HVP) contribution suggested some scatter in the central theory value, however the deviation remained greater than two standard deviations. Shortly after this Workshop, Knecht and Nyffeler reported $`^\mathrm{?}`$ a new calculation of the hadronic light-by-light (LbL) diagram (see Fig. 1d). This process cannot be determined from measurements and therefore must be estimated using theoretical models. It has endured a checkered past in which the sign was once reversed from positive to negative. The new finding finds a positive sign for the dominant pion pole contribution, but otherwise a similar magnitude to previous studies by others. $`^{\mathrm{?},\mathrm{?}}`$ This finding prompted Hayakawa and Kinoshita to reexamine their own work $`^\mathrm{?}`$ which indeed contained a sign error—in an innocent computer algorithm—prompting a report $`^\mathrm{?}`$ with a new hadronic light-by-light term of $`a_\mu (\mathrm{LbL})=+89.6(15.4)\times 10^{11}`$. Combined with the other complete hadronic LbL evaluation by Bijnens et al.,$`^\mathrm{?}`$ which has also been updated to report $`^\mathrm{?}`$ a sign error, the standard model summary $`^\mathrm{?}`$ is $`a_\mu `$(thy) $`=11659176.7(6.7)\times 10^{10}`$. This adjustment reduces $`\mathrm{\Delta }a_\mu (\mathrm{exp}\mathrm{thy})`$ by $`1`$ standard deviation and puts the discrepancy with the standard model at the modest $`1.6\sigma `$ level.

This Workshop also featured two talks by leading contributors to the 1st-order HVP evaluation. Simon Eidelman $`^\mathrm{?}`$ described the recent data obtained by the Novosibirsk CMD-II team in their experiment on $`e^+e^{}`$ Hadrons in the important $`\rho `$ region. These data alone, when finalized, should reduce the uncertainty to the 0.6 ppm level without the inclusion of hadronic tau decays. Andreas Höcker,$`^\mathrm{?}`$ together with Michel Davier, pioneered the inclusion of hadronic tau decay data in the evaluation of the HVP term. Despite non-negligible isospin breaking considerations, their results were responsible for a significant decrease in the overall SM theory uncertainty. But their work is not without some controversy and questioning.$`^\mathrm{?}`$ Additional tau data have been analyzed and the present issue discussed at this Workshop was the reliability with respect to the more direct $`e^+e^{}`$ approach; the question raised was, “Can the tau data be used with sub-percent level absolute precision?” The answer is still unclear. On the horizon experimentally is the use of radiative return at higher-energy $`e^+e^{}`$ machines which promises to add complementary precision input to the HVP database. As one has witnessed over the past year, the standard model theory of $`a_\mu `$ is very much a work in progress, just like the experiment.

Recent 1st-order HVP evaluations are shown in Fig. 2. They are compared to the new E821 result and the current world average. The QED, weak and higher-order hadronic terms, which are believed to be known to a few tenths of a ppm or better, have been subtracted from the measurement of $`a_\mu `$. This results in an effective “experiment-to-experiment” comparison because the input to the 1st-order HVP comes from measurement. The plot demonstrates the present relative size of the uncertainties. Both experiment and “theory” uncertainties will be reduced with the analysis of additional data already obtained.

Bill Marciano $`^\mathrm{?}`$ speculated on the implications of the comparison of final data with settled theory. A non-standard model result could be explained rather naturally in the context of supersymmetry. It has been recognized for some years that the muon anomaly scales nearly linearly with $`\mathrm{tan}\beta `$, the ratio of Higgs doublet vacuum expectation values in the theory. The SUSY allowed phase space certainly has ample room for large $`\mathrm{tan}\beta `$ solutions, while the lowest values, which would be exceedingly difficult to observe in $`a_\mu `$ are beginning to be ruled out by direct search experiments. Of course, many other candidate explanations for non-SM $`a_\mu `$ exist; many $`^\mathrm{?}`$ have been published following the original $`2.6\sigma `$ deviation report.

The purpose of this paper is to describe the new experiment which was designed following the three pioneering CERN efforts. Francis Farley $`^\mathrm{?}`$ presented the historical development and the key ideas incorporated in all $`(g2)`$ experiments. I will concentrate here on the specifics related to the E821 implementation and the 1999 data analysis.

## 2 The E821 Experiment

### 2.1 Principle

The experimental goal is to measure directly $`(g2)`$ and not $`g`$. The leading-order contribution to $`a_\mu =(g2)/2`$ is the QED “Schwinger” term whose magnitude is $`(\alpha /2\pi )1.16\times 10^3`$. This implies that to measure $`g`$ directly to an equivalent sensitivity would require an experiment with nearly an 800-fold increase in precision.

The muon anomaly is determined from the difference between the cyclotron and spin precession frequencies for muons contained in a magnetic storage ring, namely

$$\stackrel{}{\omega }_a=\frac{e}{m}\left[a_\mu \stackrel{}{B}\left(a_\mu \frac{1}{\gamma ^21}\right)\stackrel{}{\beta }\times \stackrel{}{E}\right].$$
(1)
In principle, an additional $`\stackrel{}{\beta }\stackrel{}{B}`$ term exists. However, it vanishes when the muon trajectory is perpendicular to the magnetic field as is the case in this experiment. Because electric quadrupoles are used to provide vertical focussing in the storage ring, the $`\stackrel{}{\beta }\times \stackrel{}{E}`$ term is necessary and illustrates the sensitivity of the spin motion to a static electric field. This term conveniently vanishes for the “magic” momentum of 3.094 GeV/$`c`$ where $`\gamma =29.3`$. The experiment is therefore built around the principle of production and storage of muons centered at this momentum in order to minimize the electric field effect. Because of the finite momentum spread of the stored muons, a modest correction to the observed precession frequency is made to account for the muons above or below the magic momentum. Vertical betatron oscillations induced by the electric field imply that the plane of the muon precession has a time-dependent pitch. Accounting for both of these electric-field related effects introduces a $`+0.81\pm 0.08`$ ppm correction to the measured precession frequency.

Muons introduced into the storage ring exhibit cyclotron motion and their spins precess until the time of decay; $`\gamma \tau _\mu 64.4\mu s`$. The net spin precession depends on the integrated path followed by a muon convoluted with the local magnetic field experienced along the path.

Parity violation leads to a preference for the highest-energy decay electrons to be emitted in the direction of the muon spin. Therefore, a snapshot of the muon spin direction at time $`t`$ after injection into the storage ring is obtained, again on average, by the selection of decay electrons in the upper part of the Lorentz-boosted Michel spectrum ($`E_{max}3.1`$ GeV). The number of electrons above a selected energy threshold is modulated at frequency $`\omega _a`$ with a threshold-dependent asymmetry $`A=A(E_{th})`$. The decay electron distribution is described by

$$N(t)=N_0\mathrm{exp}(t/\gamma \tau _\mu )\left[1+A\mathrm{cos}(\omega _at+\varphi )\right],$$
(2)
where $`N_0`$, the normalization, $`A`$ and $`\varphi `$ are all dependent on the energy threshold $`E_{th}`$. For $`E_{th}=2.0`$ GeV, $`A0.4`$.

In summary, the experiment involves the measurement of three quantities: (1) The precession frequency, $`\omega _a`$ in Eq. 1; (2) The muon distribution in the storage ring; and, (3) The time-averaged local magnetic field. The muon anomaly is proportional to the ratio,

$$a_\mu \frac{(1)}{(2)(3)}.$$
(3)
Term (3) above is measured using NMR in units of the free proton precession frequency, $`\omega _p`$. Term (2) is determined from the debunching rate of the initial beam burst and from a tracking simulation. The combined denominator involves an event-weighted average of the field folded with the muon distribution. The symbol $`\stackrel{~}{\omega }_p`$ represents the final average magnetic field and the muon anomaly is computed from the expression

$$a_\mu =\frac{\omega _a/\stackrel{~}{\omega }_p}{\lambda \omega _a/\stackrel{~}{\omega }_p},$$
(4)
where $`\lambda `$ is the measured $`^\mathrm{?}`$ muon-to-proton magnetic moment ratio $`\mu _\mu /\mu _p=3.18334539(10)`$.

Four independent teams evaluated $`\omega _a`$ and two studied $`\stackrel{~}{\omega }_p`$. During the analysis period, the $`\omega _a`$ and $`\stackrel{~}{\omega }_p`$ teams maintained separate, secret offsets to their measured frequencies. The offsets were removed and $`a_\mu `$ was computed only after all analysis checks were complete.

## 3 Experiment

### 3.1 Storage Ring

The Brookhaven muon storage ring $`^\mathrm{?}`$ is a superferric “C”-shaped magnet, 7.11 m in radius, and open on the inside to permit the decay electrons to curl inward (Fig. 3). A 5V power supply drives a 5177 A current in the three superconducting coils. The field is designed to be vertical and uniform at a central value of 1.4513 T. Carefully shaped steel pole pieces and accompanying edge shims are separated from the main iron flux return which makes up the “C” structure. The field is further shaped by tapered iron wedges placed in the yoke/pole-piece gap and by 80 low-current surface correction coils which circumnavigate the ring on the pole piece faces. The storage volume is 9 cm in diameter and is enclosed in a vacuum chamber. A vertical slice through the storage ring illustrating some of these key features is shown in Fig. 4.

Protons from the AGS strike a nickel target in 6–12 bunches separated by 33 ms within a typical 2.5–3.3 s AGS cycle. Pions created in these collisions are directed down a 72 m long beamline to the muon storage ring. Approximately half decay, $`\pi \mu \nu `$, and the forward going muons, having a high degree of longitudinal polarization, remain in the channel, generally at a slightly lower momentum. The last dipoles upstream of the entrance to the storage ring are tuned to a momentum $`1.7\%`$ lower than the main channel in order to enhance the muon fraction in the beam; the result is a final $`\mu :\pi `$ ratio of approximately $`50:50`$ entering the ring.

A superconducting inflector magnet $`^\mathrm{?}`$ provides a field-free channel through the back of the storage ring’s iron yoke. The field created by this magnet is tuned to cancel the main storage ring field. The inflector field is then prevented from extending into the storage ring by flux trapping in a superconducting outer shield.

The pulse structure of the AGS is translated to an effective muon bunch of approximately 25 ns $`RMS`$ passing through the exit of the inflector into the ring. A simple circular trajectory would result in the muon bunch striking the inflector magnet 149 ns after injection, which is the cyclotron period. A pulsed “kicker” magnet provides a 10 mrad transverse deflection to the muon bunch during the first turn in the ring. In practice, three pulsed magnets, all in series, are made from current sheets and special high-voltage pulsed power supplies.

The electric quadrupoles are located symmetrically at four positions occupying, in total, $`43\%`$ of the ring. Immediately after particle injection, the plates are asymmetrically charged in order to scrape the beam against internal collimaters. After approximately 20 $`\mu `$s, the voltages are symmetrized to final values of $`\pm `$24 kV which leads to the stored weak-focussing field index $`n=0.137`$. The horizontal and vertical betatron frequencies are $`\omega _x6.23`$ MHz and $`\omega _y2.48`$MHz, respectively. Because the inflector aperture is small compared to the cross-sectional area of the storage volume, phase space is not fully occupied and the stored beam exhibits “breathing” and “swimming” motions during a fill. These motions manifest themselves as effective modulations in the acceptance function of the detectors because the acceptance is sensitive, on average, to the position of the decaying muons. The relevance of this fact becomes clear when one realizes that the difference between the cyclotron and horizontal betatron frequencies is approximately 470 kHz, which is a little greater than twice $`\omega _a`$. These “coherent betatron oscillations” (CBO) are visible in the data; to account for CBO, Eq. 2 must be multiplied by a term of the type

$$C(t)=1+A_{cbo}e^{(t/\tau _{cbo})^2}\mathrm{cos}(\omega _{cbo}t+\varphi _{cbo})$$
(5)
where $`\tau _{cbo}`$ is the time constant for decay of the CBO terms having initial amplitude $`A_{cbo}`$.

### 3.2 Field Measurements

The magnetic field is measured using pulsed nuclear magnetic resonance (NMR) on protons in water- or Vaseline-filled probes. The proton precession frequency is proportional to the local field strength and is measured with respect to the same clock system employed in the determination of $`\omega _a`$. The absolute field is, in turn, determined by comparison with a precision measurement of $`g_p`$ in a spherical water sample $`^\mathrm{?}`$ and is thus determined to a precision of better than $`10^7`$. A subset of the 360 “fixed” probes is used to continuously monitor the field during data taking. Fixed probes are embedded in machined grooves in the outer upper and lower plates of the aluminum vacuum chamber and consequently measure the field just outside of the actual storage volume. Constant field strength is maintained using 36 of the probes in a continuous feedback loop with the main magnet power supply.

The determination of the field inside the storage volume is made by use of a unique non-magnetic trolley which can travel in vacuum through the muon storage volume. The trolley carries 17 NMR probes on a grid appropriate to determine the local multipolarity of the field versus azimuth. Trolley field maps are made every few days and take several hours to complete. The deviation from the central field strength value $`B_0=1.451266`$ T versus azimuth is shown in Fig. 5. At any given location, field measurement precision is at the 0.1 ppm level even though the local field varies by as much as 100 ppm from $`B_0`$. However, it is the average field which must be determined to the sub ppm level and this goal is readily achieved. A 800 ppm “spike” in the field is seen in a $`1^{}`$ azimuthal segment. This small defect is due to a crack in the inflector magnet shielding. Special measurements were made to map the field in this region for the 1999 data; this inflector was replaced for the 2000 and 2001 data taking periods. A one-time systematic error of 0.2 ppm is included in the 1999 result to account for uncertainties in the procedure of measuring the errant field in this region.

Comparison of the azimuthally averaged trolley field with that which is computed using the fixed probe data permits a determine of the time-dependent field. Figure 6 illustrates the excellent agreement between these two systems. The relative field is interpolated from the fixed-probe extrapolation to better than 0.15 ppm.

The trolley measurements also establish the field homogeneity throughout the storage volume. Three snapshots of the azimuthally-averaged field are shown in Fig. 7. The contours represent 1 ppm deviations from the central value. The left panel illustrates the relatively uneven field achieved shortly after the ring was commissioned in 1997; here it is already better than the CERN III field.$`^\mathrm{?}`$ An aggressive shimming program led to the improved contours for the 1998 and 1999 data taking periods (middle panel). With the inflector replaced, the field for the 2000 and 2001 data taking was again significantly improved (right panel).

## 4 Electron Detection and $`\omega _a`$ Analysis

The electron detection system consists of 24 lead-scintillating fiber electromagnetic calorimeters $`^\mathrm{?}`$ located symmetrically around the inside of the storage ring and placed immediately adjacent to the vacuum chamber. The 23 cm long, radially-oriented fiber grid terminates on four lightguides which pipe the light to independent Hamamatsu R1828 2-inch PMTs, see Fig. 8. The PMT gains are carefully balanced because the four analog signals are added prior to sampling by a custom 400 MHz waveform digitizer. At least 16 digitized samples (usually 24 or more) are recorded for each decay electron event exceeding a hardware threshold of approximately 1 GeV. An example of a series of such samples is shown in Fig. 9. Offline pulse-finding and fitting establishes electron energy and muon time of decay.

Because the full raw waveforms are stored, multi-particle pileup can be studied with sophisticated fitting algorithms which are superior to any “online,” hardware discriminator techniques. The approach taken is to fit waveforms for all occurring pulses using known detector response functions. We identify the level of pileup and remove such events, on average. By processing the data using different artificial deadtime windows around or near the driving trigger pulse, and by carefully accounting for the energy found in such windows, a pileup-free spectrum (less than $`10\%`$ pileup remaining) can be created by appropriate, normalized difference spectra. Figure 10 illustrates three curves of the energy spectrum in the calorimeters. The solid curve is the “true” energy distribution found at late times where no pileup events are expected. The dashed distribution, which extends to much higher energies, is observed at early times when the rate in the detectors is high. Pileup produces effective electron energies beyond the natural maximum of 3.1 GeV. The dotted curve is the recreated pileup-free final spectrum. Its congruence with the late-time curve gives confidence in the correction procedure.

Five-fold, vertically segmented scintillator hodoscopes (FSDs) are attached to the front face of many of the calorimeters. These FSDs are used to measure the rate of “lost muons” from the storage ring. During the initial scraping period, and extending for a period of time afterwards, errant muon trajectories will pass through one of the aperature-defining collimaters inside the storage ring. These muons lose enough energy to exit the ring, many following a path which penetrates three consecutive calorimeters and their corresponding FSDs. A triple coincidence of FSDs, together with the absence of significant energy in the calorimeters, is proportional to the lost muon rate. A representative muon loss spectra for one detector is shown in Fig. 11 At early times, the loss rate exceeds the natural muon decay rate and can be described by an exponential with an approximate $`27\mu s`$ lifetime. At later times, the loss rate is essentially constant. The overall loss rate is proportional to

$$\mathrm{\Lambda }(t)=1+A_\mathrm{\Lambda }e^{t/\tau _\mathrm{\Lambda }}.$$
(6)
Integration of $`\mathrm{\Lambda }(t)`$ and inclusion in the fitting function is necessary to obtain a good representation of the instantaneous muon population in the ring.

## 5 Fitting the 1999 Data

The five adjustable parameters in Eq. 2 were sufficient to give an excellent $`\chi ^2`$ when used to fit the 1998 data.$`^\mathrm{?}`$ Figure 12 illustrates data and 5-parameter fit for 1999. By eye, the fit also looks excellent; however, the $`\chi ^2`$ is unacceptable because the CBO, pileup and muon losses have not been accounted for in this 20 times larger data set. The “pileup-free” spectrum is fit to the function

$$f(t)=N(t)C(t)\mathrm{\Lambda }(t)$$
(7)
where $`N(t)`$ is the ideal function (Eq. 2), $`C(t)`$ accounts for the CBO (Eq. 5), and $`\mathrm{\Lambda }(t)`$ characterizes the time-dependent muon lossses (Eq. 6). With Eq. 7, or equivalent fitting strategies used by the other analysis teams, $`\chi ^2`$ is consistent with 1.

Deviations from the ideal function of the type described are more significant at early times compared to late times. One commonly used test employed by the analysis teams is to fit the data progressively beginning at different “start” times. As shown in Fig. 13, $`\omega _a`$ only fluctuates within the expected band but is otherwise stable. The distribution of variances from neighboring fits is shown on the lower right panel of the figure. This plot has a mean consistent with zero and a normalized width consistent with 1, as expected. The bottom left panels of the figure give $`\omega _a`$ and the $`\chi ^2`$ by detector for the fixed start time of 30 $`\mu `$s. These and other statistical tests yield satisfactory results.

## 6 Results, Conclusions and Outlook

Table 1 summarizes the results. The experimental value from 1999 for positive muons is $`a_{\mu ^+}=\mathrm{11\hspace{0.17em}659\hspace{0.17em}203}(15)\times 10^{10}`$ (1.3 ppm. With the updated standard model theory value of $`a_\mu (\mathrm{thy})=11659176.7(6.7)\times 10^{10}`$ (0.57 ppm), one finds $`\mathrm{\Delta }a_{\mu ^+}(\mathrm{exp}\mathrm{thy})=25(16)\times 10^{10}`$. The 2000 $`\mu ^+`$ data is presently being analyzed and should reduce the uncertainty considerably. The 2001 $`\mu ^{}`$ data is just beginning to be processed at the time of this writing. To complete the experiment, with equal positive and negative muon event samples, a final negative muon run will be necessary. The Collaboration is eager to complete this data taking phase and accompanying analysis in order to achieve our ultimate goal of 0.4 ppm precision or better in the measurement of the muon anomaly.

## Acknowledgments

The $`(g2)`$ experiment is supported in part by the U.S. Department of Energy, the U.S. National Science Foundation, the German Bundesminister für Bildung und Forschung, the Russian Minsitry of Science, and the US-Japan Agreement in High Energy Physics. The author would like to thank the organizers of the Workshop at Erice for an excellent meeting.

## References


format: text

text:
# Combinatorial Auctions with Decreasing Marginal UtilitiesA preliminary version of this paper has been presented at EC’01 Supported by grants from the Israeli Ministry of Science and the Israeli Academy of Sciences

## 1 Introduction and Overview

### 1.1 Background

Recent years have seen a surge of interest in combinatorial (also called combinational) auctions, in which a number of non-identical items are sold concurrently and bidders express preferences about combinations of items and not just about single items. Thus, for example, a bidder may offer $40 for the combination of a Tournedos Rossini and a bottle of Chateau Lafitte, but offer only $10 for each of those items alone. Similarly, a bidder may make an offer of $10 for a blue and for a red shirt, but not be willing to pay more than $10 even if he gets both shirts. In general, a combinatorial auction allows bidders to express complementarities – where the value of a combination of packages of items is worth more than the sum of the values of the separate packages – and substitutabilities – where the value of a combination of packages is less than the sum of the values of the separate packages. Such combinatorial auctions have been suggested for a host of auction situations such as those for spectrum licenses, pollution permits, landing slots, computational resources, and others. See de Vries and Vohra(forthcoming) for a survey.

Implementation of combinatorial auctions faces several challenges including the representational question of succinctly specifying the values of the different packages, the algorithmic challenge of efficiently solving the resulting, NP-hard, allocation problem, and the game-theoretic questions of bidders’ strategies. These questions have been recently approached by a host of researchers both in the general case and in several interesting special cases: MacKie-Mason and Varian(1994), Varian(1995), Rothkopf and al.(1998), Sandholm(1999), Sandholm and Suri(1999), Fujishima and al.(1999), Tennenholtz(2002), Lehmann and al.(forthcoming), Gonen and Lehmann(2000), and Nisan(2000).

Somewhat surprisingly, the special case that is most often studied in economics has received very little attention from the computational point of view. In most of microeconomic theory, consumers are assumed to exhibit diminishing marginal utilities. In particular, such consumers exhibit no complementarities. While it is not clear to what extent this assumption may be justified in practice, it is widely used. At least, it is mathematically convenient, but we think it is often justified in practice. Many papers dealing with computational issues in combinatorial auctions focused on the dual case of no substitutes, i.e., much computational research assumes that a buyer places bids for packages of items and is not interested in a sub-package. In contrast, economists who dealt with auctions did mostly consider auctions in which players expressed no complementarities. For example, for multi-unit auctions, Vickrey’s seminal paper Vickrey(1961) assumes downward sloping valuations for buyers. Recent papers dealing with combinatorial auctions such as Kelso and Crawford(1982), Gul and Stacchetti(1999), Gul and Stacchetti(2000), Ausubel(2000) and Milgrom(2000) usually assume the gross substitutes property. Each of these notions implies lack of complementarities.

Perhaps this lack of computational attention is due to a representational difficulty: it is usually assumed that buyers express their preferences by non-exclusive bids on sets of items. Representing buyers with no complementarities seems to require the use of exclusive bids for sets of items (XOR-bids), and the mechanics of such exclusive bids have never been studied in full. Bids on packages of items inherently express a very strong form of complementarity: sub-packages are not valued at all, and therefore such bids seem to provide a very poor starting point to describe types that exhibit no complementarities. The prevalent method for dealing with substitutabilities is the phantom good approach of Fujishima and al.(1999) and Nisan(2000), that simulates exclusive bids by non-exclusive bids on an enlarged set of goods. This is certainly not a promising approach for studying the specifics of exclusive bids or types exhibiting no complementarities.

In this paper, we study the three notions found in the literature for lack of complementarities. From the most general to the most specific these notions are, informally:

* No Complementarities: The value of a combination of bundles is no more than the sum of the bundle values.
* Decreasing Marginal Utilities: The marginal value of an item decreases as the set of items already acquired increases.
* Gross Substitutes: The demand for an item does not decrease when the prices of other items increase.

This paper’s main message is that the case of decreasing marginal utilities, which is equivalent to submodularity of the valuation functions, should be the focus of interest.

We prove three types of results:

* Representation and Hierarchy: We study the question of how to represent valuations (i.e., bids) that exhibit no complementarities. Our representations are constructed out of atomic valuations that offer a price for a single item, (singleton valuations), using the operations of OR and XOR. Using restricted classes of such bidding languages we are able to obtain a structural hierarchy of families of complement-free valuations. Those syntactic classes are compared to three semantic classes. This hierarchy contains five strictly nested classes of valuations: (a) complement-free valuations; (b) XOR-of-OR-of-singleton valuations; (c) submodular valuations (d) valuations that satisfy the gross substitutes property; and (e) OR-of-XOR-of-singleton valuations. We prove the containment of each class within the previous one and exhibit examples showing that the containment is strict. We also prove theorems regarding closure properties of these classes under the operations of OR and XOR. We finally show that in terms of measure the significant gap is between the class of submodular valuations and the class of valuations that satisfy the gross substitutes condition.
* Allocation: We then focus our attention on the algorithmic question of optimal allocation among players with submodular valuations. We stress the difference between this case and the more restricted and well-studied case of allocation among valuations satisfying the gross substitutes property. In the latter case, it is known that a Walrasian equilibrium exists by a result of Kelso and Crawford(1982), while in the former Walrasian equilibria do not necessarily exist: see Gul and Stacchetti (1999). Walrasian equilibria may be found in polynomial time and are the basis of almost all known computationally efficient allocation algorithms. One may thus say that the submodular case is the first hard case from a computational point of view111A similar phenomena exists from the information transfer point of view: any optimal allocation algorithm among submodular valuations requires exponential communication, while if the valuations satisfy the gross substitutes property then polynomial communication suffices by a result of Nisan and Segal(2001)..

We first show that the optimal allocation problem remains NP-hard even among agents of submodular types. Our main positive algorithmic result is a simple greedy algorithm that produces an allocation that is a $`2`$-approximation, i.e., an allocation whose value is at least half of the optimal one. This result is then generalized to types exhibiting marginal utilities that may increase only in a bounded manner. This is in sharp contrast to the general case where it remains NP-hard to find even a $`n^{1/2ϵ}`$-approximation: Sandholm(1999) and independently Lehmann and al.(forthcoming).

We do not know if a better approximation ratio is possible, nor do we know whether a polynomial time approximation algorithm exists that works for all complement-free valuations.
* False Name Bids: Our next concern is with the strategic issue of false-name bids that was identified and analyzed in a sequence of papers: Sakurai and al.(1999), Yokoo and al.(2000a, 2000b, 2001). This concerns the following problem that is inherent in combinatorial auctions that use the Vickrey-Clark-Groves payment rules (see MacKie-Mason and Varian(1994)) – the only choice, if one requires incentive compatibility and efficiency. Sakurai and al.(1999) observed that a bidder can manipulate a VCG combinatorial auction and reduce his payment by splitting his bid and placing two separate bids under false-names. They showed that, in the case of single-item multi-unit auctions, this type of savings cannot occur when all bids are downward sloping. It is claimed there (without proof and without precise definitions) that this generalizes to combinatorial auctions when all bidders have no complementarities. We show that this is not exactly the case222We have contacted the authors of this paper and they have confirmed a bug in their unpublished proof., but rather the generalization to combinatorial auctions requires that the combined valuation of other bidders is submodular.

We provide an example showing that it is not sufficient to require that each player be of a submodular type.

### 1.2 Paper Structure

This paper is charting the so far unexplored territory of complement-free valuations. It is therefore by necessity proceeding carefully and proving a large number of small results. In section 2 we present the basic definitions of the classes of valuations that we discuss. Section 3 discusses the representation of valuations using OR and XOR expressions, and provides a structural hierarchy of sub-classes of complement-free valuations. It also shows that gap between submodular and gross substitutes valuations is very large. Section 4 provides many examples of complement-free and submodular valuations, both natural ones. Such examples are used to separate the different classes defined and studied previously. Section 5 presents the main result of this paper. It discusses allocation (winner determination) algorithms for submodular agents, comparing with the gross substitutes case. Section 6 discusses false-name bids. Finally, section 7 shortly mentions an extension of the results of section 5 to valuations exhibiting limited complementarities and bounded increases in marginal utilities.

## 2 Definitions

### 2.1 Preliminaries

In this paper we consider a combinatorial auction of non-identical goods. There is a set $`X`$ of items for sale by a single auctioneer in a single combinatorial auction. We shall denote the number of items for sale by m = $`X`$. There are $`n`$ agents (buyers, bidders) who all desire these items. Each agent $`i`$ has its own private valuation function, $`v_i`$, that specifies the utility it gets from each possible subset of items: i.e. for a subset $`AX`$ of items, $`v_i(A)`$ is the amount of money at which bidder $`i`$ values this subset $`A`$ of items. For a singleton set $`\{x\}`$ we will use $`v_i(x)`$ as a shorthand for $`v_i(\{x\})`$. This formalization makes two important implicit assumptions:

* Quasi-linearity: Agents’ utilities can be measured in terms of “money”, i.e. are linear in the “money”.
* No Externalities: An agent’s valuation depends only on the set of items he wins, not on the identity of the agents that get the items outside $`A`$: the valuation function $`v_i`$ is $`v_i=v_i(A)`$, where $`A`$ is the set of items won by agent $`i`$.

In addition, we assume that these valuations all satisfy the following conditions:

* Free disposal: Items have non-negative value. Thus $`v_i`$ satisfies $`v_i(A)v_i(B)`$, whenever $`AB`$.
* Normalization: $`v_i(\mathrm{})=0`$.

###### Definition 1

A valuation is a function, $`v:2^X^+`$, from subsets of items to the non-negative reals that satisfies the normalization and free disposal conditions, i.e. $`v_i(\mathrm{})=0`$ and $`v_i(A)v_i(B)`$, whenever $`AB`$ (monotonicity).

The auctioneer’s aim is to find an optimal allocation.

###### Definition 2

An allocation is a partition of $`X`$ into pairwise disjoint sets of items $`S_1\mathrm{}S_n`$ that allocates the bundle $`S_i`$ to agent $`i`$. An allocation is optimal if it maximizes $`_iv_i(S_i)`$.

The auction rules must also define the payments received from each bidder.

### 2.2 Marginal Valuations

A central notion that we will be using is that of the marginal valuation. It describes how a player would value sets of remaining items if he were already given some other items.

###### Definition 3

Given a valuation $`v`$ on a set $`X`$ of items and a set $`WX`$ of items, the marginal valuation of a set $`AXW`$ given $`W`$ is defined by:

$$v(AW)=v(AW)v(W).$$

One may consider the marginal valuation of a single element, $`v(x)`$, as a discrete analog for the partial derivative of $`v`$ in direction $`x`$.

### 2.3 No Complementarities

###### Definition 4

A valuation $`v`$ is called complement-free if it satisfies:

$$v(A)+v(B)v(AB)$$

for all sets $`A`$, $`BX`$. The class CF is the set of all complement free valuations.

While this notion is clearly natural, it turns out that valuations with this property can still have hidden complementarities. Example 4 shows that even if $`v`$ is in CF, the valuation $`v(W)`$ need not be, i.e., once a set of items $`W`$ is already acquired, complementarities may surface. Indeed, as Example 4 shows, this condition of complement-freedom is not the proper analog of downward-sloping valuations. It is therefore only natural to turn to those valuations that have no such hidden complementarities: those valuations whose marginal valuations exhibit no complementarities. It turns out that these are exactly the submodular valuations, i.e., valuations with decreasing marginal utilities.

### 2.4 Decreasing Marginal Utilities – Submodular Valuations

This paper focuses on a subset of valuations that is of special economic interest: valuations with decreasing marginal utilities. These valuations are a strict subset of the complement-free valuations. We believe that, in fact, it is the correct economic notion capturing absolute lack of complementarity and that it is a much more natural assumption than the convexity of preferences that is so central to much of economic theory. Such valuations are known as submodular functions. In many combinatorial problems, submodularity can play a role similar to convexity in optimization.

###### Definition 5

A valuation $`v`$ is called submodular if for every two sets of items $`ST`$ and element $`x`$, $`v(xT)v(xS)`$. Submodular valuations are also called valuations with decreasing marginal utilities. The class SM is the set of all submodular valuations.

Thus we require that the marginal utility of an element decreases as the set of items already acquired increases. Submodular functions are well-known and heavily used in combinatorics (see Narayanan(1997). If we extend the analogy between the marginal valuation and the derivative discussed in section 2.2, we see why submodular valuations are considered a discrete analog of convex functions – the “derivative” $`v(x)`$ is decreasing. Here, we consider only valuations: monotone, positive submodular functions. In the literature, submodular functions have been generally been considered in a wider setting. Many equivalent characterizations of decreasing marginal utilities are well-known.

###### Theorem 1 (see Moulin(1988) or Narayanan(1997))

A valuation $`v`$ is submodular if and only if any one of the following equivalent propositions holds.

* For any $`x,yX`$ and $`SX`$: $`v(xS)v(xS\{y\})`$.
* For any $`S,T,VX`$, such that $`ST`$: $`v(VS)v(VT)`$.
* For any $`A,BX`$: $`v(A)+v(B)v(AB)+v(AB)`$.

From the last characterization we get:

###### Corollary 1

A submodular valuation is complement-free.

The converse is not true and in Example 4 below we exhibit a valuation that is complement-free, yet its marginal utilities are not decreasing. It turns out that valuations with decreasing marginal utilities are exactly the valuations without any “hidden” complementarities.

###### Lemma 1

\[see Topkis(1998)\] A valuation $`v`$ is submodular if and only if for every subset of items $`R`$, the marginal valuation function $`v(R)`$ is complement-free.

In particular we get the corollary.

###### Corollary 2

If a valuation $`v`$ is submodular, then for every subset $`R`$ of items the marginal valuation function $`v(R)`$ is submodular.

Proof: All the marginal valuation functions of $`v(R)`$ are also marginal valuation functions of $`v`$ and thus have no complementarities.

### 2.5 Gross Substitutes

All the definitions and theorems in this subsection are from Kelso and Crawford(1982), Gul and Stacchetti(1999). We have sometimes slightly modified the terminology and notation. We have kept with the now traditional terminology of gross substitutes, even though gross does not fit the situation. In order to define the gross substitutes property we need to consider first the effect of putting prices on items. We think of what happens to the valuation of $`v`$ of a set $`S`$, when the price of all items in $`S`$ must be paid.

###### Definition 6

Given a vector of real item prices $`\stackrel{}{p}=`$ $`(p_1\mathrm{}p_m)`$, the surplus of a set of items $`S`$ relative to these prices is defined as $`v(S\stackrel{}{p})=`$ $`v(S)_{iS}p_i`$. A set $`S`$ is a preferred set of $`v`$ at prices $`\stackrel{}{p}`$ if $`v(S\stackrel{}{p})=`$ $`\mathrm{max}_Tv(T\stackrel{}{p})`$, i.e., $`S`$ maximizes the surplus. The demand set of $`v`$ at prices $`\stackrel{}{p}`$ is the set of all preferred sets $`D(v\stackrel{}{p})=`$ $`\{Sv(S\stackrel{}{p})=\mathrm{max}_Tv(T\stackrel{}{p})\}`$.

The gross substitutes property mandates that increasing the price of an item will not decrease the demand for any other item: i.e., if an item $`i`$ is in a preferred set at prices $`\stackrel{}{p}`$, then increasing $`p_j`$ for some $`ji`$, will still have item $`i`$ in some preferred set.

###### Definition 7

A valuation $`v`$ is said to satisfy the gross substitutes property if for any item $`i`$, any price vector $`\stackrel{}{p}`$ and any price vector $`\stackrel{}{q}\stackrel{}{p}`$ (coordinatewise comparison) with $`p_i=q_i`$, we have that if $`iA`$ where $`AD(v\stackrel{}{p})`$, then there exists $`A^{}D(v\stackrel{}{q})`$ such that $`iA^{}`$. The class GS is set of all valuations that satisfy the gross substitutes property.

An equivalent condition is called the single improvement property. This condition states that a non-preferred set can always be improved (in terms of its surplus) by deleting at most one element from it and inserting at most one element into it.

###### Lemma 2 (Gul and Stacchetti(1999))

A valuation $`v`$ satisfies the gross substitutes property if and only if for any $`\stackrel{}{p}`$ and $`AD(v\stackrel{}{p})`$, there exists $`A^{}`$ such that $`A^{}A1`$ and $`AA^{}1`$ and $`v(A^{}\stackrel{}{p})>v(A\stackrel{}{p})`$.

The gross substitutes property is stronger than submodularity.

###### Lemma 3 (Gul and Stacchetti(1999))

A valuation that satisfies the gross substitutes property is submodular.

The key property that makes valuations with the gross substitutes property so convenient is that in an auction (equivalently an exchange economy) with such valuations, Walrasian equilibria exist. A Walrasian equilibrium is a vector of prices on the items and an allocation such that every bidder receives a preferred set at these prices.

###### Definition 8

A Walrasian equilibrium in an auction with valuations $`v_1\mathrm{}v_n`$ is a price vector $`\stackrel{}{p}`$ and an allocation $`A_1\mathrm{}A_n`$ such that for all bidders $`j`$: $`A_jD(v_j\stackrel{}{p})`$.

###### Theorem 2 (Kelso and Crawford(1982))

Any auction with gross substitutes valuations $`v_1\mathrm{}v_n`$ has a Walrasian equilibrium.

It turns out that this is essentially also a necessary condition.

###### Theorem 3 (Gul and Stacchetti(1999))

If $`v_1`$ does not satisfy the gross substitutes property then there exist valuations $`v_2\mathrm{}v_n`$ that do satisfy the gross substitutes property333In fact, Gul and Stacchetti(1999) prove that $`v_2\mathrm{}v_n`$ may be unit demand functions – a stronger claim. and the auction with $`v_1\mathrm{}v_n`$ does not have a Walrasian equilibrium.

It is easy to verify the “first Welfare theorem” in this context: any Walrasian equilibrium gives an optimal allocation, i.e. one that maximizes $`_jv_j(A_j)`$.

## 3 Representation and Structure

### 3.1 Elements of Representation

The question of representation of valuations, i.e., how to succinctly describe a valuation without listing explicitly the values for each of the $`2^n1`$ subsets of items, must be addressed before valuations can be efficiently treated in any allocation algorithm. How can we represent complement-free valuations succinctly? We may consider representing such valuations by combining simple valuations by suitable operators.

The basic syntactic elements from which valuations are usually constructed consist of a certain price for a specific set of elements. They correspond to the single-minded valuations (i.e., bidders) of Lehmann and al.(forthcoming). The only single-minded valuations in CF are valuations in which only a single item is valued at a positive value. It is therefore expected that those singleton valuations will play a central role in describing CF valuations.

###### Definition 9

For an item $`xX`$ and a price $`p`$, the singleton valuation $`e_x^p`$ is a valuation giving the same value $`p`$ to all sets containing $`x`$ and the value $`0`$ to all sets that do not include $`x`$.

The operators commonly used for representing valuations are those introduced in Sandholm(1999): OR and XOR. They are often understood as prescriptions concerning the compatibility of bids, but the following presentation, as operations on valuations, is more convenient.

###### Definition 10 (Nisan(2000))

Let $`v_1`$ and $`v_2`$ be two valuations on the set $`X`$ of items. The valuations $`v_1v_2`$ (XOR) and the valuation $`v_1v_2`$ (OR) are defined by:

$$(v_1v_2)(S)=max(v_1(S),v_2(S)),$$

$$(v_1v_2)(S)=\underset{TS}{\mathrm{max}}(v_1(T)+v_2(ST)).$$

Both operators have an intuitive description. The OR ($``$) of two valuations represents the valuation of an agent representing both valuations, bidding on their behalf and sharing the result between them optimally. The value given to a bundle by the OR of two valuations is obtained by partitioning the bundle optimally between these valuations. The XOR ($``$) of two valuations represents the valuation of a single bidder capable of choosing between two possible but incompatible personalities after the auction. His value for a set $`S`$ is the largest of the two values of the component valuations. The operations OR and XOR are obviously associative and commutative.

### 3.2 A Syntactic Hierarchy

It is now natural to study the hierarchy of valuations obtained by combining singleton valuations by the OR and XOR operations. Here are the levels of the hierarchy

1. Singleton valuations.
2. $`OSvaluations`$: The family of valuations that can be described by OR of singletons is precisely the family of (separately) additive valuations: those valuations which value any set at the sum of the values of its elements. They exhibit no complementarities and no substitutabilities.
3. $`XSvaluations`$: The family of valuations that can be described by XOR of singletons is usually called the family of unit-demand valuations Gul and Stacchetti(1999): those valuations that value any set of elements at the value of the element of the set that is most valued. This family of types has been considered central by Vickrey and since.
4. $`OXSvaluations`$: The family of OR’s of XS valuations represents the aggregated valuation of multiple unit-demand players.
5. $`XOSvaluations`$: The family of XOR’s of additive valuations turns out to subsume the whole hierarchy. This follows from the simple observation that OR distributes over XOR:

$$(ab)(cd)=(ac)(ad)(bc)(bd).$$

Therefore XOS is closed under OR (it is obviously closed under XOR). It follows that any expression that uses combinations of OR and XOR operations on singleton valuations can be represented as a simple XOS expression.

We shall see in Section 4.2 that XOS is a strict subset of CF, but contains SM and that OXS is a strict subset of XOS. In fact we have just shown that on any set of atomic valuations (not only singletons), XOR-of-OR combinations can represent arbitrary complex combinations of ORs and XORs.

### 3.3 Closure Theorems

Once we have defined the operations of OR and XOR it is natural to ask whether the classes of valuations defined semantically (CF, SM, and GS) are closed under these operations.

#### 3.3.1 CF

The operations of OR and XOR fit well our concern with the class CF since:

###### Theorem 4

The class CF is closed under OR and XOR.

Proof: Let $`v_1`$ and $`v_2`$ be complement free valuations then:

$$(v_1v_2)(ST)=max(v_1(ST),v_2(ST))$$

$$max(v_1(S)+v_1(T),v_2(S)+v_2(T))$$

$$max(v_1(S),v_2(S))+max(v_1(T),v_2(T))=$$

$$(v_1v_2)(S)+(v_1v_2)(T).$$

Similarly fix partitions $`(S_1:S_2)`$ of $`S`$ and $`(T_1:T_2)`$ of $`T`$, such that $`(v_1v_2)(ST)=`$ $`v_1(S_1T_1)+v_2(S_2T_2)`$. Now,

$$(v_1v_2)(ST)=v_1(S_1T_1)+v_2(S_2T_2)$$

$$v_1(S_1)+v_1(T_1)+v_2(S_2)+v_2(T_2))$$

$$(v_1v_2)(S)+(v_1v_2)(T).$$

#### 3.3.2 SM

The class of submodular valuations is not closed under either OR or XOR. It is not closed under XOR as it contains the class OS of additive valuations, but Example 3 shows that it does not contain the class XOS which is XORs of additive valuations. The fact that it is not closed under OR is shown by Example 5.

#### 3.3.3 GS

The class GS is not closed under XOR as it contains the class OS of additive valuations, but Example 3 shows that even its superset SM does not contain the class XOS which is XORs of additive valuations. It is however closed under the OR operation, as will be shown now.

###### Theorem 5

If valuations $`u`$ and $`w`$ satisfy the gross substitutes property then so does $`uw`$.

The theorem follows from combining the results of Fujishige and Yang(2001) showing that gross substitutes is equivalent to $`M^\mathrm{\#}concavity`$ with those of Murota and Shioura(1999) regarding the closure of $`M^\mathrm{\#}`$-convex functions under convolution (i.e., OR). For completeness, we provide a simple proof based on the results cited above of Kelso and Crawford(1982) and Gul and Stacchetti(1999).

Proof: We will prove the theorem indirectly, applying Theorems 3 and 2. Using Theorem 3, it suffices to show that for all gross substitutes valuations $`v_2\mathrm{}v_n`$, an auction among agents $`uw,v_2\mathrm{}v_n`$ has a Walrasian equilibrium. Theorem 2 states that an auction among agents $`u,w,v_2,\mathrm{},v_n`$ has a Walrasian equilibrium: vector of prices $`\stackrel{}{p}`$ with allocation $`A_u,A_w,A_2,\mathrm{}A_n`$. We claim that $`\stackrel{}{p}`$ with the allocation $`A_uA_w,A_2,\mathrm{}A_n`$ is a Walrasian equilibrium for bidders $`uw,v_2\mathrm{}v_n`$.

The only thing that needs to be verified is that $`(A_uA_w)D(uw\stackrel{}{p})`$. This is so since for any set $`S`$, let $`S_u`$ and $`S_w`$ be a partition of $`S`$ such that $`(uw)(S)=`$ $`u(S_u)+w(S_w)`$. Thus also $`(uw)(S\stackrel{}{p})=`$ $`u(S_u\stackrel{}{p})+w(S_w\stackrel{}{p})`$. Now, since $`A_uD(u\stackrel{}{p})`$ we have that $`u(S_u\stackrel{}{p})`$ $`u(A_u\stackrel{}{p})`$, and similarly for $`w`$. Clearly $`u(A_u)+w(A_w)`$ $`(uw)(A_uA_w)`$, and so also $`u(A_u\stackrel{}{p})+w(A_w\stackrel{}{p})`$ $`(uw)(A_uA_w\stackrel{}{p})`$. Thus

$$(uw)(S\stackrel{}{p})=u(S_u\stackrel{}{p})+w(S_w\stackrel{}{p})$$

$$u(A_u\stackrel{}{p})+w(A_w\stackrel{}{p})(uw)(A_uA_w\stackrel{}{p}).$$

### 3.4 The Complete Hierarchy

We have seen by now five significant classes of valuations. Three of them were defined semantically: complement-free (CF), submodular (SM), and gross substitutes (GS). Two of them were defined syntactically: ORs of XORs of singletons (OXS) and XORs of ORs of singletons (XOS). We now can state the relationships between these classes.

###### Theorem 6

$$OXSGSSMXOSCF.$$

All containments are strict.

Proof: We will prove the containments from left to right. The fact that they are strict will follow from the examples found below in Section 4.2.

1. $`OXSGS`$: This follows from Theorem 5 since GS contains all unit demand valuations (XS-valuations) (Gul and Stacchetti(1999)), and therefore also contains ORs of XS valuations.
2. $`GSSM`$: This was shown in Gul and Stacchetti(1999).
3. $`SMXOS`$: each submodular valuation may be represented by a long XOR expression. For each permutation $`\pi `$ of the items we will have an OR clause – the XOS expression will be the XOR of all these OR clauses. The OR clause for the permutation $`\pi `$ will offer for each item $`i`$ the marginal price of $`i`$ assuming that all items preceding it in the permutation $`\pi `$ have already been obtained. Formally, for $`i=\pi (j)`$, the price is $`v(i\{\pi (1),\mathrm{},\pi (j1)\})`$. To see that the XOS expression indeed represents the submodular valuation, consider a submodular $`v`$ and a set $`A`$ of items. For any permutation $`\pi `$ of the items in which the items of $`A`$ are placed first, the value given to $`A`$ by the OR clause for $`\pi `$ is exactly $`v(A)`$. All other OR clauses give to $`A`$ a value that is smaller or equal, since $`v`$ has decreasing marginal utilities.
4. $`XOSCF`$: By Theorem 4.

### 3.5 Measure

In this section we study how $`large`$ are the five classes of valuations studied so far. Our sense of size is the simple one of measure. Each valuation is specified by a vector of $`2^m1`$ real numbers, and we can thus look at each class of valuations as residing in the $`2^m1`$-dimensional Euclidean space. What we ask here is what is the measure of these classes, in particular whether their measure is positive. It turns out that there is a significant gap between the GS and SM levels of the hierarchy: GS valuations have measure $`0`$, while SM valuations have positive measure.

###### Theorem 7

For every number of items $`m3`$, the class GS (on $`m`$ items) has zero-measure in the $`2^m1`$-dimensional Euclidean space. Therefore its interior is empty.

Proof: The theorem is directly implied by the following claim:

###### Claim 1

If $`x,y,z\mathrm{\Omega }`$ are pairwise distinct items and $`v`$ is a GS valuation such that $`v(zy)<v(zx)`$, then $`v(xy)=v(xz)`$.

The theorem follows from the claim since the set GS is contained in the union of the three hyper-planes defined by the equations $`v(xy)=v(xz)`$ for all permutations of $`x,y,z`$.

The claim follows from the two lemmas below. Each of those lemmas is proved by a similar technique, making a direct use of a GS valuation: the prices of two of the three items are fixed and the price of the third item is made to increase from zero to a large value.

###### Lemma 4

If $`v(zy)<v(zx)`$, then $`v(xy)v(xz)`$.

Proof: Given a valuation $`v`$, a price vector (for all items), and sets $`A`$, $`B`$ of items, we write $`AB`$ or $`BA`$ if $`B`$ is at least as preferred as $`A`$ at the given prices, $`AB`$ or $`BA`$ if $`B`$ is strictly preferred to $`A`$ and $`AB`$ if $`A`$ and $`B`$ have the same net utility given the prices. Let us fix the prices of $`x`$ and $`y`$: $`p_x=v(xz)`$ and $`p_y=v(yz)`$. These prices induce preferences between subsets of $`\mathrm{\Omega }`$. First: $`xzzyz`$. Notice that this holds independently of the price of $`z`$. Notice also that, since $`v`$ is GS it is submodular, i.e., it exhibits decreasing marginal values and, since one does not gain by adding $`x`$ to $`z`$, one cannot gain by adding $`x`$ to $`yz`$ and therefore $`xyzyz`$. Let us now fix, at first, the price of $`z`$ at zero: $`p_z^1=0`$. One never loses by adding $`z`$ to one’s bundle and therefore all three bundles: $`z`$, $`xz`$ and $`yz`$ are preferred bundles. In particular $`xz`$ is a preferred set at the current prices. Let us now increase the price of $`z`$ to some value, $`p_z^2`$ such that $`v(zy)<p_z^2<v(zx)`$. At the new prices $`yzy`$ and $`xxz`$. Therefore $`xy`$. By the gross substitutes property, there is, at the new prices, some preferred set that contains $`x`$. This set must be at least as preferred as $`y`$ and therefore cannot be $`x`$ and certainly not $`xz`$ or $`xyz`$. Therefore $`xy`$ is a preferred set and $`xyy`$: $`v(xy)p_x0`$ and $`v(xy)v(xz)`$.

###### Lemma 5

If $`v(zy)<v(zx)`$, then $`v(xy)v(xz)`$.

Proof: By contradiction. Assume $`v(zy)<v(zx)`$ and $`v(xy)>`$ $`v(xz)`$ and fix prices for $`x`$ and $`z`$ such that: $`v(xz)<`$ $`p_x<`$ $`v(xy)`$ and $`v(zy)<`$ $`p_z<`$ $`v(zx)`$. Those prices for $`x`$ and $`z`$ imply the following preferences: $`yzyxy`$ and $`xxzz`$. Since $`v`$ is submodular, we also know that $`xyzyz`$ (one does not gain by adding $`x`$ to $`z`$, therefore one cannot gain by adding $`x`$ to $`yz`$) and that $`\mathrm{}x`$ (one gains by adding $`x`$ to $`y`$, therefore one gains by adding $`x`$ to the empty bundle). Let us fix, first the price of $`y`$ at zero. Then, $`xy`$ is a preferred set. Let, then, the price of $`y`$ increase to a value high enough to make any bundle containing $`y`$ unattractive. Then $`z`$ is the only preferred bundle, contradicting the substitutes property. This concludes the proof of the lemma, of the claim, and of the theorem.

We do not know what is the dimensionality of the class GS. In particular it is possible that its dimension is only polynomial in $`m`$. We have shown that the class GS is small, let us now show that SM is large.

###### Theorem 8

For any number of items $`m1`$, the class SM of valuations over $`m`$ items has a non-empty interior in the $`2^m1`$-dimensional Euclidean space. Therefore it has positive measure.

Proof: We shall use $`x`$ to denote the absolute value of a number $`x`$ and $`S`$ to denote the cardinality of a finite set $`S`$. Let $`n=\mathrm{\Omega }`$. The valuation $`v_c(S)=12^S`$ is a symmetric (see section 4.1.1), monotone, normal, submodular valuation for which the marginal value of the $`k`$th element is $`2^k`$. It is, in a sense, a central submodular valuation. The theorem follows from the claim that, for any function $`h:2^\mathrm{\Omega }`$ such that $`h(S)2^{(n+2)}`$, the valuation $`v(S)=v_c(S)+h(S)`$ is submodular. Indeed, assume $`ST`$ and $`xT`$. We have:

$$v(xS)=v(S\{x\})v(S)2^{(S+1)}2^{(n+1)}$$

$$2^{(S^{}+1)}+2^{(S^{}+1)}2^{(n+1)}2^{(S^{}+1)}+2^{(n+1)}$$

$$v(xS^{})v(S)=v(xS^{}).$$

## 4 Examples of Submodular Valuations

### 4.1 Natural Examples

The simplest and most common natural examples of valuations with no complementarities are the additive valuations (the class OS) and the unit demand valuations (the class XS) mentioned in Section 3.2. These valuations are both trivially in sub-classes of OXS and thus clearly satisfy the gross substitutes property, and are also submodular. We now mention some other natural valuations that are submodular.

#### 4.1.1 Symmetric valuations

Symmetric valuations are ones where $`v(S)`$ depends only on the size of $`S`$, $`S`$. These cases fit auctions of multiple identical items. Symmetric valuations may be described by a sequence of marginal values: numbers $`p_1\mathrm{}p_m`$ where $`p_i=v(T)v(S)`$ for any sets $`T`$ and $`S`$ of sizes $`i`$ and $`i1`$ respectively. We then have: $`v(S)=_i^Sp_i`$ for any set $`S`$. The following set of symmetric valuations has received considerable attention. For example Vickrey(1961)’s multi-unit auction considers only such valuations.

###### Definition 11

A symmetric valuation is downward sloping iff for all $`i`$, $`p_{i+1}p_i`$.

As expected, these are exactly the symmetric submodular valuations.

###### Proposition 1

A symmetric valuation is downward sloping if and only if it is submodular.

Proof: For a symmetric valuation $`v`$, for $`xS`$, $`v(xS)=p_{S+1}`$, and the equivalence is immediate.

It is known from Gul and Stacchetti(1999) that downward sloping symmetric valuations also satisfy the gross substitutes property and in fact can be represented in the class OXS (see Nisan(2000)). On the other hand, the complement-free symmetric valuations are a wider class – see below Examples 4 and 3.

#### 4.1.2 Additive valuations with a budget limit

Our second class of examples is composed of valuations that are additive-up-to-a-budget-limit. In these valuations, a set is valued at the sum of the values of its items, unless this sum is larger than a budget limit. In this last case it is valued at the budget limit.

###### Definition 12

A valuation $`v`$ is called additive with a budget limit if there exists a constant $`b`$, the budget limit, such that for all sets $`S`$ of items, $`v(S)=`$ $`min(b,_{iS}v(i))`$.

###### Proposition 2

Every additive valuation with a budget limit is submodular.

Proof: Assume $`ST`$ and $`xT`$. We have

$$v(xT)=min(b,v(T)+v(\{x\}))v(T)=$$

$$min(bv(T),v(x))min(bv(S),v(x))=v(xS).$$

These type of valuations do not necessarily satisfy the gross substitutes property – see below Example 2.

#### 4.1.3 Valuations based an underlying measure

The third class of valuations we want to present consists of valuations based on some underlying set with a measure on it. Let us first start with a concrete example. Consider a combinatorial auction for a set of spectrum licenses in overlapping geographical regions. Each geographical region contains a certain population, and a reasonable valuation for a set of licenses is the total population in the geographic area covered by the regions in the set. It turns out that such valuations are submodular. More generally, the overlapping regions may be arbitrary sets in some underlying base set, and the population count may be replaced by any measure on the base set.

###### Definition 13

A valuation $`v`$ is said to be based on the underlying measure $`\mu `$ on a base set $`\mathrm{\Gamma }`$ if there are sets $`I_1\mathrm{}I_m\mathrm{\Gamma }`$ such that for each set $`S`$ of goods, $`v(S)=\mu (_{iS}I_i)`$.

###### Lemma 6

Every valuation that is based on an underlying measure is submodular.

Proof: Consider $`ST`$, and an item $`x`$. Denote $`\stackrel{~}{S}=`$ $`_{iS}I_i`$, and similarly $`\stackrel{~}{T}`$. Clearly $`\stackrel{~}{S}\stackrel{~}{T}`$. We now have $`v(xS)=`$ $`\mu (I_x\stackrel{~}{S})\mu (I_x\stackrel{~}{T})=`$ $`v(xT)`$.

### 4.2 Separation Examples

#### 4.2.1 $`OXSGS`$

###### Example 1

Consider a set $`X`$ of four items: $`X=\{a,b,c,d\}`$ and the valuation $`v`$ defined by: the value of any singleton is $`10`$ and the value of any other set is $`19`$, except for the two sets $`\{a,c\}`$ and $`\{b,d\}`$ the value of which is $`15`$.

###### Claim 2

The valuation $`v`$ is not in OXS.

Proof: Suppose $`v=v_1\mathrm{}v_n`$. Since $`v(\{a\})=10`$, there is some $`i`$ with $`v_i(\{a\})=10`$. Without loss of generality, assume $`i=1`$. Since $`v(\{b\})=10`$, there is some $`i`$ with $`v_i(\{b\})=10`$. Since $`v(\{a,b\})<20`$, for any $`i1`$, $`v_i<10`$. We conclude that $`v_1(\{b\})=10`$. Similarly, $`v_1(\{c\})=v_1(\{d\})=10`$. Consider now that $`v(\{a,c\})=15`$, therefore, since $`v_1(\{a\})=10`$, for any $`i>1`$, $`v_i(\{c\})5`$. Similarly, for any item $`x`$ and any $`i>1`$, $`v_i(\{x\})5`$. But $`v(\{a,b\})=19`$ and therefore there must be $`ij`$ such that $`v_i(\{a\})+v_j(\{b\})=19`$, a contradiction.

###### Claim 3

The valuation $`v`$ is in GS.

Proof:(sketch) We will use the single improvement property (Lemma 2). Let $`\stackrel{}{p}`$ be any price vector and consider any non-preferred set $`A`$. Let $`DD(v\stackrel{}{p})`$ be a preferred set. We need to show that we can improve the surplus of $`A`$ by deleting at most one element and inserting at most one element. This requires a tedious case by case analysis that we omit, except for the only nontrivial case where $`A=D^c`$ and both are of size 2, e.g. $`A=\{a,b\}`$ and $`D=\{c,d\}`$. In this case either $`\{a,d\}`$ or $`\{b,c\}`$ will have a surplus greater than $`A`$’s.

#### 4.2.2 $`GSSM`$

###### Example 2

Consider the additive valuation with budget limit 4 on three elements: $`v(1)=v(2)=2`$, $`v(3)=4`$. Since the budget limit is 4, each set that contains at least two elements has a valuation of 4.

This valuation is submodular by Proposition 2, but it does not satisfy the gross substitutes property. Consider the price vector $`p_1=0,p_2=1,p_3=2`$. At these prices the preferred subset is $`\{1,2\}`$ giving a surplus of 3. However, if we increase the price of item 1 to $`p_1=2`$, then the preferred subset is $`\{3\}`$ giving a surplus of $`2`$, where any set that contains item 2 will have a surplus of at most 1. Thus we have reduced the demand for item 2.

#### 4.2.3 $`SMXOS`$

###### Example 3

Consider the symmetric valuation on three elements defined by $`p_1=2`$, $`p_2=0`$, $`p_3=1`$: a set of one or two elements is valued at 2, while the set of all three elements is valued at 3.

By definition, it is not downward sloping, therefore not submodular, by Proposition 1, but it is obtained by the following XOR-of-OR-of-singletons:

$$(\{1\}:2)(\{2\}:2)(\{3\}:2)w$$

where $`w=`$ $`(\{1\}:1)(\{2\}:1)(\{3\}:1)`$.

#### 4.2.4 $`XOSCF`$

###### Example 4

Assume a set $`X`$ of three items and $`v(S)=2`$ if $`S=1`$, $`v(S)=3`$ if $`S=2`$ and $`v(S)=5`$ if $`S=3`$.

The valuation $`v`$ is in CF since $`2+23`$ and $`2+35`$. We shall show that it cannot be expressed as a XOR-of-ORs-of-singletons. Assume that it is, and consider the OR clause that provides the valuation of $`5`$ to the set of all three elements. This OR clause contains (at most) three singleton bids for the three items; if we take the two highest bids of these three we must get a valuation of at least $`52/3>3`$, in contradiction to the valuation of any two elements being 3.

This is also an example for the fact that the class CF is not closed under marginal valuations. The marginal valuation $`v_W`$, where $`W`$ contains any single item, gives $`v_W(S)=1`$ if $`S=1`$ and $`v_W(S)=3`$ if $`S=2`$ and is not in CF.

#### 4.2.5 SM is not closed under OR

The following example will show that SM is not closed under OR.

###### Example 5

Let $`u(1)=3`$, $`u(2)=5`$ and $`u(3)=3`$, where $`u`$ has a budget limit of 6. Let $`w`$ be the additive valuation: $`w(1)=1`$, $`w(2)=2`$, $`w(3)=0`$. Let $`v=uw`$.

The valuation $`u`$ is submodular by Proposition 2. One can see that: $`v(\{1,2\})=`$ $`6`$ ($`u`$ gets both), $`v(\{2,3\})=6`$ ($`u`$ gets both). Therefore $`v(\{1,2\})+v(\{2,3\})=`$ $`12`$. But $`v(\{1,2,3\})=8`$ ($`u`$ gets 1 and 3 and $`w`$ gets 2), $`v(2)=5`$ ($`u`$ gets it), and $`8+5>12`$ and $`v`$ is not submodular.

We know of two special cases in which the OR of submodular functions is submodular. The first concerns symmetric valuations.

###### Proposition 3

If $`v_1`$ and $`v_2`$ are symmetric submodular valuations then $`v_1v_2`$ is submodular (and symmetric).

Proof: By proposition 1 and Nisan(2000), any symmetric submodular valuation is an OXS valuation. Since OXS is clearly closed under the $`OR`$ operation we have that $`v_1v_2`$ is in OXS and thus also, by Theorem 6, is submodular.

The second case concerns valuations with disjoint supports.

###### Proposition 4

If $`v_1`$ and $`v_2`$ are submodular valuations with disjoint supports (i.e., $`v_i(x)>0`$ implies $`v_j(x)=0`$) then $`v_1v_2`$ is submodular.

Proof: For any set $`S`$: $`(v_1v_2)(S)=v_1(S)+v_2(S)`$.

## 5 Allocation

We now turn to the computational problem of allocating the items in a combinatorial auction in which all agents have submodular valuations. As a computational problem, we must first consider the format of the input, i.e. how are the valuation functions $`v_1\mathrm{}v_n`$ presented to the algorithm. In the most general case representing a valuation may require exponential size (in $`m`$, the number of items). We, on the other hand, are looking for algorithms that are polynomial in the relevant parameters, $`n`$ and $`m`$. There are two possible approaches for obtaining efficient algorithms despite the exponential size of the input.

The first approach considers the general case, but where the valuations are presented to the algorithm as “valuation oracles” – black boxes that can be queried for the valuation of a set $`S`$, returning its valuation $`v(S)`$. In a mechanism, this corresponds to allowing bidders to send an arbitrary representation of the valuation function, as long as the valuations of sets can be efficiently computed from it444Surprisingly, achieving this is not totally trivial – see section 3.6 of Nisan(2000).. The second approach fixes a representation, and provides allocation algorithms that require polynomial time in the size of the representation of the valuations in this format. Such algorithms will generally be as interesting as the strength of the representation format.

We present our main positive result in section 5.3, in the general terms of valuation oracles. Our main negative result, the NP-hardness of allocation for submodular valuations, presented in subsection 5.2, holds for a special case (additive valuations with a budget limit) that has a simple short representation. Both our results are therefore presented in the strongest possible manner. Concrete lower bounds for the valuation oracle representation are derived in Nisan and Segal(2001). We first review the case of GS agents, which is polynomial time solvable.

### 5.1 The Case of Gross Substitutes

The case of a combinatorial auction where all valuations satisfy the gross substitutes property can be solved in polynomial time. Since Walrasian equilibria exist in this case by Kelso and Crawford(1982) (see definition 8 and theorem 2 above), they can be found and an optimal allocation results. Let us look more closely at the computational process of finding this Walrasian equilibrium. The following procedure of Kelso and Crawford(1982) yields prices and an allocation that is arbitrarily close to optimal:

1. Initialize all item prices to 0.
2. Repeat the following procedure: compute a preferred set for each bidder at these prices and increase by a small amount $`ϵ`$ the price of all items that are demanded by more than one agent.
3. Stop when each item is demanded by at most one agent, and let the allocation be the preferred sets at these prices.

This procedure produces an allocation whose distance from optimal depends only on $`ϵ`$ and whose running time is polynomial in $`n,m,ϵ^1`$. This algorithm is naturally implemented as a mechanism, in some cases is actually incentive compatible, and in the general case can serve as a basis for an incentive compatible mechanism as in Ausubel(2000). But this procedure only provides an approximation (it is actually a “FPAS” – fully polynomial approximation scheme) and not an exact solution.

An exact solution can be computed in polynomial time using linear programming. Indeed, the optimization problem can be described as an integer-programming problem whose LP relaxation has an integral solution (see Bikhchandani and al.(2001)). This linear program has an exponential number of variables, but only a polynomial number of constraints. One can therefore solve the problem using a separation-based algorithm on the dual (see Nisan and Segal(2001) for more details). This LP algorithm requires only a polynomial number of calls to a demand oracle that, given a GS valuation $`v`$ and a price vector $`\stackrel{}{p}`$, computes a preferred set $`SD(v\stackrel{}{p})`$ at these prices.

The fact that allocation among GS valuations can be computed in polynomial time follows also from the algorithms for calculating the convolution of $`M^\mathrm{\#}`$-concave functions developed in Murota(1996), Murota(2000) and Murota and Tamura(2001).

###### Theorem 9

An optimal allocation among GS valuations can be found in polynomial time, if the valuations themselves can be computed in polynomial time.

A special case of interest is when all valuations in the auction are OXS valuations. If these valuations are given using the OR of XOR of singletons representation, then the allocation problem reduces to a matching problem in a bipartite graph and can thus be computed in polynomial time by Tarjan(1983), Fredman and Tarjan(1987).

### 5.2 NP-hardness of an exact solution among submodular players

The problem of finding an optimal allocation in combinatorial auctions is known from Rothkopf and al.(1998) to be NP-hard even if bidders are single-minded, i.e., place only one bid each. Is the problem any easier if the bidders are assumed to have submodular valuations? The answer is negative. Finding an optimal allocation is still an NP-hard problem, even if all valuations are additive with budget limit. Note that, in such a case, all players valuations may be succinctly expressed.

###### Theorem 10

Finding an optimal allocation in a combinatorial auction with two valuations that are additive with a budget limit is NP-hard.

Proof: We will reduce from the well-known NP-complete problem “Knapsack” (see Garey and Johnson(1979)): Given a sequence of integers $`a_1\mathrm{}a_m`$, and a desired total $`t`$, determine whether there exists some subset $`S`$ of the integers whose sum is $`t`$, $`_{iS}a_i=t`$. Given an input of this form, construct the following two valuations on $`m`$ items:

* The first valuation is additive giving the price $`a_i`$ to each item $`i`$: $`v_1(S)=_{iS}a_i`$.
* The second valuation is additive with a budget limit of $`2t`$, and gives the price $`2a_i`$ to each item $`i`$: $`v_2(S)=2\mathrm{min}(t,_{iS}a_i)`$.

Fix an allocation of $`S`$ to valuation 2 and $`S^c`$ to valuation 1 and consider the 3 cases: $`_{iS}a_i<t`$, $`_{iS}a_i=t`$, and $`_{iS}a_i>t`$. Denote $`f=_ia_i`$. If $`_{iS}a_i=t`$ then $`t+_{iS^c}a_i=f`$ and $`v_1(S^c)+v_2(S)=`$ $`_{iS^c}a_i+2t=`$ $`f+t`$. If $`_{iS}a_i<`$ $`t`$ then $`v_1(S^c)+v_2(S)=`$ $`_{iS^c}a_i+2_{iS}a_i=`$ $`f+_{iS}a_i<`$ $`f+t`$. If $`_{iS}a_i>`$ $`t`$ then $`_{iS^c}a_i+t<`$ $`f`$, and $`v_1(S^c)+v_2(S)=`$ $`_{iS^c}a_i+2t<`$ $`f+t`$. Thus we see that the auction has an allocation $`(S^c:S)`$ with value $`f+t`$ if the knapsack problem has a positive answer $`S`$, and otherwise the allocation has a lower value.

Two comments should be made here: first, this NP-hardness result is for specific, succinctly defined, submodular valuations. The case of general submodular valuations given as an oracle is harder in a stricter sense, that of requiring exponentially many oracle queries as shown in Nisan and Segal(2001). Second, this result is for allocation among several valuations. A related well studied question is the maximization a single submodular function (not necessarily monotone). This problem is well known to be NP-hard for some specific succinctly defined functions, and to require exponentially many queries in the general oracle model, see Jensen and Korte(1982), Lovász(1980), and Lovász(1983).

### 5.3 A 2-approximation

Our main algorithmic result is a $`2`$-approximation algorithm for combinatorial auctions in which all valuations are submodular. The result does not rely on any specific representation of submodular functions: it only assumes that one can effectively compute valuations of subsets.

Input: $`v_1,\mathrm{},v_n`$ \- submodular valuations, given as black boxes.

Output: An allocation (partition of the items) $`S_1,\mathrm{},S_n`$ which is a $`2`$-approximation to the optimal allocation

Algorithm

1. Set $`S_1=S_2=\mathrm{}=S_n\mathrm{}`$.
2. For $`x=1\mathrm{}m`$ do:

1. Let $`j`$ be the bidder with highest value of $`v_j(xS_j)`$.
    2. Allocate $`x`$ to bidder $`j`$, i.e. $`S_jS_j\{x\}`$.

The algorithm obviously requires only a polynomial number of operations and calls to valuation oracles for $`v_j`$ since $`v_j(xS_j)=v_j(S_j\{x\})v_j(S_j)`$.

###### Theorem 11

If all $`v_i`$ are submodular valuations then the greedy algorithm above provides a $`2`$-approximation to the optimal one.

Proof: Let $`Q`$ be the original problem and define $`Q^{}`$ to be the problem on the $`m1`$ remaining items after item $`1`$ is removed: i.e., item 1 is unavailable and $`v_j`$ is replaced by $`v_{}^{}{}_{j}{}^{}`$ with $`v_{}^{}{}_{j}{}^{}(S)=v(S\{1\})=v(S\{1\})v(\{1\})`$, where $`j`$ is the player to which item 1 was allocated. All other valuations $`v_i`$, $`ij`$ are unchanged. Notice that the algorithm above may be viewed as first allocating item $`1`$ to $`j`$ and then allocating the other elements using a recursive call on $`Q^{}`$.

Let us denote by $`ALG(Q)`$ the value of the allocation produced by this algorithm, and by $`OPT(Q)`$ the value of the optimal allocation. Let $`p=v_j(\{1\})`$. By the definition of $`Q^{}`$, it is clear that $`ALG(Q)=ALG(Q^{})+p`$. We will now show that $`OPT(Q)OPT(Q^{})+2p`$. Let $`S_1,\mathrm{},S_n`$ be the optimal allocation for $`Q`$, and assume that $`1S_k`$, i.e., item 1 is allocated to bidder $`k`$ by the algorithm above. Let $`S^{}`$ be the solution to $`Q^{}`$ obtained from $`S`$ by ignoring item 1. Let us compare the value of $`S^{}`$ in $`Q^{}`$(which is a lower bound on $`OPT(Q^{})`$) to the value of $`S`$ in $`Q`$ (which is exactly $`OPT(Q)`$). All players except $`k`$ get the same allocation and all players except $`j`$ have the same valuation. Without loss of generality, assume $`kj`$. Player $`k`$ looses at most $`v_k(\{1\})`$ since $`v_k`$ is submodular. But $`v_k(\{1\})v_j(\{1\})=p`$ and player $`k`$ looses at most $`p`$. Player $`j`$ looses at most $`p`$ since, by monotonicity of $`v_j`$, $`v_j^{}(S_j)=v_j(S_j\{1\})v_j(\{1\})v_j(S_j)p`$. Therefore $`OPT(Q^{})`$ $`OPT(Q)2p`$. The proof is concluded by induction on $`Q^{}`$ since, by lemma 1, $`Q^{}`$ also consists of submodular valuations:

$$OPT(Q)OPT(Q^{})+2p$$

$$2ALG(Q^{})+2p=2ALG(Q).$$

Looking at the proof one may see that many variants of the above algorithm also produce a $`2`$-approximation. In particular the items $`x`$ may be enumerated in any order in the outer loop. One may think of several heuristics for choosing the next $`x`$. For example: take the item $`x`$ that maximizes the difference between the first and second values of $`v_j(xS_j)`$.

An alternative proof for a variant of this algorithm may be obtained using the results of Fisher and al.(1978) regarding the maximization of a single submodular valuation over a matroid. Indeed the winner determination problem in a combinatorial auction is a maximization problem over a matroid, and this does not seem to have been observed previously. Consider the set $`P=N\times X`$, where $`N`$ is the set of agents and $`X`$ is the set of items. A subset $`SP`$ is a partial allocation iff each item is included in at most one element of $`S`$. The family of partial allocations is a matroid. The function to be maximized is the sum of $`n=N`$ valuations. In our case, each valuation is submodular and therefore their sum is also submodular, and the existence of a polynomial-time $`2`$-approximation algorithm follows from Theorem 2.1 of Fisher and al.(1978). The NP-hardness result of section 5.2 shows we are dealing with a hard case of submodular monotonic function maximization over a matroid.

The family of greedy algorithms we consider is wider than the one considered by those authors since they request a specific ordering of the items and we do not, leaving more space for heuristic considerations. In section 7 we shall generalize this result to valuations that are not submodular, and therefore fall outside the scope of Fisher and al.(1978).

Recent work (Lehmann(2002)) shows that the allocation produced by this algorithm is not only a $`2`$-approximation to the optimal integer allocation but also a $`2`$-approximation to the optimal fractional allocation.

It is easy to see that our bound is sharp and the algorithm above may provide only a $`2`$-approximation even for submodular valuations: take $`v_1(\{1\})=`$ $`v_1(\{2\})=`$ $`v_1(\{1,2\})=`$ $`v_2(\{1\})=`$ $`v_2(\{1,2\})=1`$ and $`v_2(\{2\})=0`$.

Open Problem: Does any polynomial algorithm provide a better approximation ratio?

Conforti and Cornuéjols(1984) sharpened the results of Fisher and al.(1978). Their results offer better bounds when the submodular valuations are known to be close to linear, but not in the general case. They also provide better bounds when the matroid is close to uniform, but our matroid has very small girth ($`1`$) and large rank ($`m`$). We have also shown above that our bound is sharp. The results of Nisan and Segal(2001) provide a weak lower bound showing that achieving an approximation ratio of better than $`1+1/m`$ requires an exponential number of queries to the valuation oracles.

### 5.4 Strategic considerations

The approximation algorithm presented above may be viewed as a simple sequence of auctions of the single items, one by one. Simplistic bidders whose strategies do not take the future into account should indeed value an item $`i`$ at its current marginal value for the bidder. Thus if each auction in this sequence is designed to be incentive compatible (e.g. a second price auction) and if all bidders follow this simplistic bidding strategy (myopic bidders) then the desired $`2`$-approximate allocation would be obtained. In this subsection we ask whether there is a payment scheme to be used with this allocation algorithm that guarantees incentive-compatibility of the complete auction, i.e. that will reach this allocation when the bidders are rational and not myopic. The answer is negative.

An example will show that no payment scheme can make the greedy allocation scheme for sub-modular combinatorial auctions a truthful mechanism. In this example, the greedy scheme allocates the most expensive items first. We do not know whether the result may be generalized to any greedy scheme. The spirit of the proof is similar to that of Section 12 of Lehmann and al.(forthcoming).

###### Example 6

Two goods: a and b. Two sub-modular players: Red and Green. Red declares 10 for a, 6 for b and 11 for the set $`\{a,b\}`$. Notice this is a sub-modular declaration, but this is not crucial. Green has two personalities:

* Green1 declares 11 for a, 10 for b and 18 for the set $`\{a,b\}`$.
* Green2 declares 9 for a, 10 for b and 19 for the set $`\{a,b\}`$.

Notice both are sub-modular declarations.

The allocation between Red and Green1 goes in the following way: a is allocated first to Green1 (Green’s 11 vs. Red’s 10) and then b is allocated to Green1 (Green’s 18-11 vs. Red’s 6). Notice that if b had been allocated first Green would have obtained b but not a. Green1 is therefore allocated the set $`\{a,b\}`$ and pays a sum $`p`$. Notice that, since all declarations are fixed, $`p`$ is a number; it does not depend on anything. The allocation between Red and Green2 goes a different way: any ordering gives a to Red and b to Green. Green2 pays $`q`$ (just a number).

If the mechanism is truthful and Green is Green1, it must be the case that Green cannot gain by disguising himself as Green2: $`18p10q`$. If the mechanism is truthful and Green is Green2, it must be the case that Green cannot gain by disguising himself as Green1: $`10q19p`$. A contradiction.

## 6 False-Name Bids

This section deals with the following strategic manipulation problem that is inherent in combinatorial auctions that use the Vickrey-Clark-Groves payment rules (Vickrey(1961),Clarke(1971),Groves(1973) or see MacKie-Mason and Varian(1994)). The VCG rules dictate that a player that is allocated a set $`S`$ of items pays the external cost to society of his allocation, i.e., his payment is $`u(X)u(XS)`$, where $`X`$ is the set of all items, and $`u`$ is the combined (by OR) valuations of all other bidders (i.e. the valuation obtained by the value of the optimal allocation of items among the other bidders). A disturbing observation made in Sakurai and al.(1999) is that in many cases a bidder can manipulate a VCG combinatorial auction and reduce his payment by splitting his bid and placing two separate bids under false-names. For example, if two items $`A`$ and $`B`$ are offered and my valuation for the pair $`\{A,B\}`$ is $`6`$, while another bidder values the pair at $`5`$, the VCG rules will set my payment to $`5`$. If, instead, I place two separate bids, $`\{A\}`$ for $`4`$ and $`\{B\}`$ for $`4`$, then one may easily calculate that each of these false-name bidders pays $`1=54`$ for a total payment of $`2`$.

This issue was further discussed in Yokoo and al.(2000a, 2000b, 20001). They showed that such false-name bidding cannot be profitable for any agent if the surplus function is concave, i.e., submodular over agents. This condition is a strengthening of the agents are substitutes condition first considered in Shapley(1962) and then in Bikhchandani and Ostroy(forthcoming). We show that a different condition also guarantees that false-name bidding is not profitable. If the aggregate valuation of all other agents is submodular in the items, one cannot benefit from placing false-name bids. We then discuss this condition and show that the result is sharp: false-name attacks may be profitable even if all agents are submodular.

###### Theorem 12

A player cannot benefit from placing false name bids in a combinatorial auction using the VCG rules, whenever the combined valuation of all other players is submodular.

Proof: We shall show that two players, one of them bidding a valuation $`v_1`$ and the other a valuation $`v_2`$ will pay no less than a single player bidding $`v_1v_2`$, as long as the combined valuation function of the other players is submodular.

Consider the set of bids $`v_1,v_2,u_1,\mathrm{},u_m`$ and let $`S_1`$ be the set allocated to player 1, $`S_2`$ be the set allocated to player 2, and $`T`$ be the set allocated to all the $`u_i`$ bidders together: thus the total set of goods is $`TS_1S_2`$. Let $`u=u_1\mathrm{}u_m`$.

The VCG rules (GVA auction) specify that player 1 will pay:

$$(uv_2)(TS_1S_2)(uv_2)(TS_2).$$

Since the optimal allocation of $`TS_2`$ among the valuations $`u`$ and $`v_2`$ allocates $`T`$ to $`u`$ and $`S_2`$ to $`v_2`$, we have that $`(uv_2)(TS_2)=`$ $`u(T)+v_2(S_2)`$. By considering the allocation of $`S_2`$ to $`v_2`$ and $`TS_1`$ to $`u`$, we can bound

$$(uv_2)(TS_1S_2)u(TS_1)+v_2(T_2).$$

We thus get that player 1 pays at least $`u(TS_1)u(T)`$. Similarly player 2 will pay at least $`u(TS_2)u(T)`$.

Consider, on the other hand what happens when instead of $`v_1`$ and $`v_2`$ a single $`v_1v_2`$ bid is submitted. The allocation to this bidder is exactly $`S_1+S_2`$. The VCG payment of this player will be $`u(TS_1S_2)u(T)`$. The submodularity of $`u`$ directly implies that this is less than or equal to the sum of the payments of players 1 and 2 in the previous case.

As a simple corollary we obtain.

###### Corollary 3

A player cannot benefit from placing false name bids in a combinatorial auction using the VCG rules, where all valuations satisfy the gross substitutes property.

Proof: According to theorem 5, the combined valuation (OR) of GS valuations is GS and thus is also submodular.

A slightly weaker result could have been proven by showing that the aggregate utility (OR combination) of GS valuations is concave in the agents and using Proposition 3 of Yokoo and al.(2000a). But Common Knowledge of the fact that all players are GS would have been required.

Corollary 3 also implies a previous result of Sakurai and al.(1999) showing that in a Vickrey multi-unit auction of identical items in which all players have a downward sloping valuations, no player can benefit from placing false-name bids.

Could Theorem 12 assume, instead, that all players have a submodular valuation? The following example shows that this is not the case. The following example builds on Example 5 and presents an auction in which each player is submodular, but the combined valuation of the opponents is not and one can benefit from false-name bids.

###### Example 7

Red has budget limit 6 and values: $`red(a)=`$ $`red(c)=3`$, $`red(b)=5`$. Blue has unbounded budget: $`blue(a)=1`$, $`blue(b)=2`$, $`blue(c)=0`$. Let $`v`$ be the combined valuation, $`v=redblue`$. We have that $`v(abc)=8`$, $`v(ab)=`$ $`v(ac)=`$ $`v(bc)=6`$. Green has unbounded budget: $`green(a)=2`$, $`green(b)=0`$, $`green(c)=5`$.

If Green acts as himself, he gets $`\{a,c\}`$ (utility 7) and Red gets $`\{b\}`$ (utility 5) for a total of 12, unbeatable. Green pays: 8-5 = 3.

But, assume that Green acts under two different identities $`G1(a)=2`$ and $`G2(c)=5`$. Obviously $`G1`$ gets $`\{a\}`$ and $`G2`$ gets $`\{c\}`$. $`G1`$ pays: 11-10=1. $`G2`$ pays: 8-7=1. On the whole $`G1`$ and $`G2`$ together pay only 2 which is strictly less than 3.

This example also shows that the “agents are substitutes” condition of Shapley(1962) and Bikhchandani and Ostroy(forthcoming) does not follow from the fact that all agents have submodular valuations. Let $`T`$ be the set of agents containing: Red, Blue, G1 and G2. We have seen that $`v(T)=12`$. Let $`S`$ be the set containing G1 and G2. We have seen that $`v(TS)=8`$. But $`v(T\{G1\})=11`$ and $`v(T\{G2\})=8`$. We see that $`v(T)v(TS)<(v(T)v(T\{G1\}))+(v(T)v(T\{G2\}))`$.

## 7 Bounded Complementarity

While the definition of submodular valuations is theoretically clean, in many real world situations, valuations cannot be assumed to be submodular. In many cases, valuations exhibit complementarities. Complementarities are, indeed, one of the main reasons for the development of parallel or combinatorial auctions. In much of traditional economic theory, decreasing marginal values, or convexity, have been assumed more for mathematical expediency reasons than because they fit the data. The submodularity assumption will now be weakened in a way that allows it to encompass complementarities and nevertheless retains its mathematical structure.

In many cases it can be argued that marginal valuations should be rather decreasing, i.e., should not be increasing too much, or that if complementarities exist, they are not too large and may be bounded in some way. In this section we formalize this idea and then observe that in such cases the greedy allocation algorithm still produces provably good results. Thus our results assuming submodularity have wider implications.

The definitions and results of Section 2.4 can be generalized to deal with valuations that exhibit a limited amount of complementarity. We assume $`a1`$ is a real number. The number $`a`$ is a measure of how close we are to complement-freeness or to submodularity. The case $`a=1`$ is the one considered above in this paper: complement-freeness and submodularity. The larger the number $`a`$ the looser our assumptions.

###### Definition 14

A valuation $`v`$ is said to exhibit $`a`$-bounded complementarities if, for any set $`A`$ and item $`x`$:

$$v(A\{x\})v(A)+av(\{x\}).$$

Complementarities are bounded multiplicatively by the number $`a`$.

###### Definition 15

A valuation $`v`$ is said to be $`a`$-submodular if and only if for every subset $`W`$ of items, the marginal valuation $`v(W)`$ exhibits $`a`$-bounded complementarities.

The proofs of the following results are similar to those of Section 2.4 and will be omitted.

###### Proposition 5

A valuation $`v`$ is $`a`$-submodular if and only if any one of the following equivalent propositions holds.

* For any $`xX`$ and $`S,TX`$, such that $`ST`$ and $`xT`$: $`av(xS)v(xT)`$.
* For any $`S,T,VX`$, such that $`ST`$: $`av(VS)v(VT)`$.
* For any $`A,BX`$: $`v(A)+av(B)v(AB)+av(AB)`$.

The $`2`$-approximation result of Section 5 generalizes to a $`1+a`$-approximation.

###### Theorem 13

The greedy algorithm provides a $`(1+a)`$ approximation to the optimal one if all valuations are $`a`$-submodular.

Notice that the problem we solved is of maximizing a function that is not submodular over a matroid. We do not know whether this may have useful implications for other such problems.

## 8 Acknowledgments

We thank Sushil Bikhchandani, Motti Perry, Rakesh Vohra and Makoto Yokoo for helpful discussions, and Liad Blumrosen for comments on an earlier draft of this manuscript. An associate editor pointed to us the relevant work on optimization of submodular functions on matroids.