text:
# Gravitational Waves in Brane World — A Midi-superspace Approach —

## 1 Introduction

The idea of the brane world has provided an active area in the field of cosmology. The main attractive point of this idea is its testability. However, to make a definite prediction, we need to understand the role of the bulk on the brane world cosmology. Before considering the complicated cosmological perturbation theory, we would like to try to understand the essence of the problem in the simple models. The aim of this paper is to study some aspects of the brane-bulk correspondence in the Bianchi Type I midi-superspace model.

Let us start to describe the $`Z_2`$ symmetric brane world model which we want to analyze from now on. The action for it is given by

$$S=\frac{1}{2\kappa ^2}d^5x\sqrt{g}\left(^5+\frac{12}{l^2}\right)\sigma d^4x\sqrt{g_{brane}}+d^4x\sqrt{g_{brane}}_{matter}$$
(1)
where $`l`$ denotes the curvature radius of the AdS spacetime, $`\kappa ^2`$ is the gravitational constant in the 5 dimensional spacetime, and $`\sigma `$ and $`g_{brane}`$ represnt the brane tension and the induced metric on the brane respectively. Here we assume the relation $`\kappa ^2\sigma =6/l`$ which is necessary to have the Minkowski vacuum.

From the above action, we obtain the 5-dimensional Einstein equations;

$$G_N^M=\frac{6}{l^2}\delta _N^M+\kappa ^2\frac{\sqrt{g_{brane}}}{\sqrt{g}}T_N^M,(M,N=y,t,x^i).$$
(2)
As for the matter confined to the brane, we consider the perfect fluid

$$T_N^M=diag(0,\rho ,p,p,p)\delta (y).$$
(3)
First, let us consider the FRW cosmology. The cosmological principle restricts the bulk metric in the following form:

$$ds^2=e^{2\beta (y,t)}(dt^2+dy^2)+e^{2\alpha (y,t)}\delta _{ij}dx^idx^j.$$
(4)
Then, the induced metric on the brane becomes

$$ds^2=dt^2+e^{2\alpha _0(t)}\delta _{ij}dx^idx^j.$$
(5)
Due to the generalized Birkoff’s theorem, only AdS-Schwarzschild black hole solutions are allowed. Correspondingly, the cosmology on the brane is also simple. Putting $`8\pi G_4=\kappa ^2/l`$, we get the effective Friedmann equation as

$$\dot{\alpha }_0^2=\frac{8\pi G_4}{3}\rho +\frac{\kappa ^4\rho ^2}{36}+e^{4\alpha _0}C_0,$$
(6)
where the parameter $`C_0`$ corresponds to the mass of the black hole. It should be noted that there exists no gravitational waves in this back ground. This makes the understanding of brane-bulk correspondence easier.

To proceed to the cosmological perturbation theory is a natural next step for understanding cosmology.  To reveal the nature of the cosmological perturbation, we need to consider the bulk spacetime with gravitational waves. However, it is too complicated to analyze in detail.

In this circumstances, we take the midi-superspace approach to attack the issue. Namely, we consider the minimal model which can allow the bulk gravitational waves. We shall consider the Bianchi type midi-superspace models:

$$ds^2=e^{2\beta (y,t)}(dt^2+dy^2)+e^{2\alpha (y,t)}g_{ij}(y,t)\omega ^i\omega ^j.$$
(7)
Apparently, there can exist (nonlinear) gravitational waves in this bulk spacetime. The induced cosmology on the brane is nothing but the anisotropic bianchi type cosmology;

$$ds^2=dt^2+e^{2\alpha _0(t)}g_{ij0}(t)\omega ^i\omega ^j.$$
(8)
It includes FRW model as a special case. Hence, it should have implications into the cosmological perturbations. For simplicity, we will consider only the Bianchi type I model in this paper, althogh the generalization is straightforward.

## 2 Anisotropic Cosmology

Bianchi Type I midi-superspace metric is given by

$$ds^2=e^{2\beta (y,t)}(dt^2+dy^2)+e^{2\alpha (y,t)}\left(e^{2(\chi _+(y,t)+\sqrt{3}\chi _{}(y,t))}dx_1^2+e^{2(\chi _+(y,t)\sqrt{3}\chi _{}(y,t))}dx_2^2+e^{4\chi _+(y,t)}dx_3^2\right).$$
(9)
As is mentioned previously, gravitational waves can propagate in the bulk. From the above metric, it is easy to calculate the components of the Einstein tensor relevant to the junction conditions as

$`G_{\mathrm{\hspace{0.25em}0}}^0`$ $`=`$ $`3e^{2\beta }(\dot{\alpha }^2+\dot{\alpha }\dot{\beta }\alpha ^{\prime \prime }2\alpha ^2+\alpha ^{}\beta ^{}\dot{\chi }_+^2\dot{\chi }_{}^2\chi _+^2\chi _{}^2)`$ (10)
$`G_{\mathrm{\hspace{0.25em}1}}^1`$ $`=`$ $`e^{2\beta }(2\ddot{\alpha }3\dot{\alpha }^2\ddot{\beta }+2\alpha ^{\prime \prime }+3\alpha ^2+\beta ^{\prime \prime }+\ddot{\chi }_++\sqrt{3}\ddot{\chi }_{}\chi _+^{\prime \prime }\sqrt{3}\chi _{}^{\prime \prime }`$ (11)
$`3\dot{\chi }_+^2+3\chi _+^23\dot{\chi }_{}^2+3\chi _{}^2+3\dot{\alpha }\dot{\chi }_+3\alpha ^{}\chi _+^{}+3\sqrt{3}\dot{\alpha }\dot{\chi }_{}3\sqrt{3}\alpha ^{}\chi _{}^{})`$
$`G_{\mathrm{\hspace{0.25em}2}}^2`$ $`=`$ $`e^{2\beta }(2\ddot{\alpha }3\dot{\alpha }^2\ddot{\beta }+2\alpha ^{\prime \prime }+3\alpha ^2+\beta ^{\prime \prime }+\ddot{\chi }_+\sqrt{3}\ddot{\chi }_{}\chi _+^{\prime \prime }+\sqrt{3}\chi _{}^{\prime \prime }`$ (12)
$`3\dot{\chi }_+^2+3\chi _+^23\dot{\chi }_{}^2+3\chi _{}^2+3\dot{\alpha }\dot{\chi }_+3\alpha ^{}\chi _+^{}3\sqrt{3}\dot{\alpha }\dot{\chi }_{}+3\sqrt{3}\alpha ^{}\chi _{}^{})`$
$`G_{\mathrm{\hspace{0.25em}3}}^3`$ $`=`$ $`e^{2\beta }(2\ddot{\alpha }3\dot{\alpha }^2\ddot{\beta }+2\alpha ^{\prime \prime }+3\alpha ^2+\beta ^{\prime \prime }2\ddot{\chi }_++2\chi _+^{\prime \prime }`$ (13)
$`3\dot{\chi }_+^2+3\chi _+^23\dot{\chi }_{}^2+3\chi _{}^26\dot{\alpha }\dot{\chi }_++6\alpha ^{}\chi _+^{}).`$
The power series expansion near the brane

$$\alpha (y,t)=\alpha _0(t)+\alpha _1(t)|y|+\frac{\alpha _2(t)}{2}y^2+\mathrm{}$$
(14)
defines our notations. From the Einstein equation, we get the junction conditions

$`\alpha _1(t)`$ $`=`$ $`{\displaystyle \frac{1}{l}}{\displaystyle \frac{\kappa ^2\rho (t)}{6}},`$
$`\beta _1(t)`$ $`=`$ $`{\displaystyle \frac{1}{l}}+{\displaystyle \frac{\kappa ^2\rho (t)}{3}}+{\displaystyle \frac{\kappa ^2p(t)}{2}},`$
$`\chi _{+1}`$ $`=`$ $`0,`$
$`\chi _1`$ $`=`$ $`0,`$ (15)
where we set $`e^{\beta _0(t)}=1`$.

The other components of the Einstein tensor

$`G_y^y`$ $`=`$ $`3e^{2\beta }(\ddot{\alpha }2\dot{\alpha }^2+\dot{\alpha }\dot{\beta }+\alpha ^2+\alpha ^{}\beta ^{}\dot{\chi }_+^2\dot{\chi }_{}^2\chi _+^2\chi _{}^2)`$ (16)
$`G_y^0`$ $`=`$ $`3e^{2\beta }(\beta ^{}\dot{\alpha }+\alpha ^{}\dot{\beta }\dot{\alpha }^{}\dot{\alpha }\alpha ^{}2\dot{\chi }_+\chi _+^{}2\dot{\chi }_{}\chi _{}^{})`$ (17)
give equations on the brane

$`\ddot{\alpha }_0+2\dot{\alpha }_0^2={\displaystyle \frac{\kappa ^2}{2l}}\left({\displaystyle \frac{\rho }{3}}p\right){\displaystyle \frac{\kappa ^4\rho (\rho +3p)}{36}}\dot{\chi }_+^2\dot{\chi }_{}^2`$
$`\dot{\rho }+3\dot{\alpha }_0(\rho +p)=0.`$
From these equations, we can deduce the Friedmann equation as

$`H^2`$ $`=`$ $`{\displaystyle \frac{8\pi G_4}{3}}\rho +\dot{\chi }_{+0}^2+\dot{\chi }_0^2+{\displaystyle \frac{\kappa ^4}{36}}\rho ^2+C_0e^{4\alpha _0}e^{4\alpha _0}{\displaystyle 𝑑\alpha _0e^{2\alpha _0}\frac{d}{d\alpha _0}[e^{6\alpha _0}(\dot{\chi }_{+0}^2+\dot{\chi }_0^2)]}`$ (18)
$`=`$ $`{\displaystyle \frac{8\pi G_4}{3}}\rho +\dot{\chi }_{+0}^2+\dot{\chi }_0^2+{\displaystyle \frac{\kappa ^4}{36}}\rho ^2+C_0e^{4\alpha _0}2e^{4\alpha _0}{\displaystyle 𝑑te^{4\alpha _0}\left[\dot{\chi }_{+0}\chi _{+2}+\dot{\chi }_0\chi _2\right]},`$ (19)
where we have used equations for $`\chi _{\pm 0}`$ to obtain the last line.

The last term represents the effect of gravitational waves in the bulk on the brane world cosmology. This correction term is apparently non-local and hence we need the information of the bulk.

## 3 Vacuum Brane

As we want to understand the effects of gravitational waves on the brane cosmology, the existence of the matter is not essential. Hence, we consider the vacuum brane.

### 3.1 Trivial bulk and boundary theory

It is well known that there exist exact solutions in the form

$$ds^2=(\frac{l}{y})^2\left[dy^2+g_{\mu \nu }(x^\lambda )dx^\mu dx^\nu \right],$$
(20)
where $`g_{\mu \nu }`$ is the 4-d vacuum metric. All of the Bianchi type vacuum solutions can be elevated to the exact brane world solutions.

In the case of the Bianchi type I model, we have the exact Kasner type solution

$$ds^2=(\frac{l}{y})^2\left(dt^2+dy^2+t^{2p_1}dx_1^2+t^{2p_2}dx_2^2+t^{2p_3}dx_3^2\right).$$
(21)
Notice that the brane is located at $`y=l`$ in this coordinate system. As is usual, the parameters are constrained by the following relations

$`p_1+p_2+p_3`$ $`=`$ $`1,`$ (22)
$`p_1^2+p_2^2+p_3^2`$ $`=`$ $`1.`$ (23)
It would be interesting to consider the free scalar field on this background. As this system is separable, we can put

$$\varphi =\chi (t)f(y)e^{ik_1x_1+ik_2x_2+ik_3x_3}$$
(24)
then the Klein-Gordon equation leads to

$`\ddot{\chi }+{\displaystyle \frac{1}{t}}\dot{\chi }+\omega ^2\chi +\left(k_1^2t^{12p_1}+k_2^2t^{12p_2}+k_3^2t^{12p_3}\right)\chi =0,`$ (25)
$`f^{\prime \prime }+{\displaystyle \frac{3}{y}}f^{}=\omega ^2f.`$ (26)
Thus, we can define the boundary field theory as is done in AdS case. It is a generalization of the AdS/CFT correspondence to Gravity/Quantum Field Theory correspondence.

### 3.2  Effects of non-trivial bulk

Now we would like to consider how the cosmogical evolution on the brane is affected by the gravitational waves in the bulk. The strategy we take is the following. First we solve the equation on the brane which can be written using the variables solely on the brane. We call this type of the equation as the constraint equation. Then we calculate the non-local term from the explicit solution and identify its effective equation of state.

The constraint equation on the brane is given by

$$\ddot{\alpha }_0+2\dot{\alpha }_0^2+\dot{\chi }_{+0}^2+\dot{\chi }_0^2=0.$$
(27)
An interesting subclass of the solutions is

$$\alpha _0=A\mathrm{log}t,\chi _{\pm 0}=B_\pm \mathrm{log}t.$$
(28)
Substitution this ansatz into the constraint equation gives the relation:

$$2(A\frac{1}{4})^2+B_+^2+B_{}^2=\frac{1}{8}.$$
(29)
Allowed region for $`A`$ becomes $`0A\frac{1}{2}`$. The previous relations now become

$`p_1+p_2+p_3`$ $`=`$ $`3A,`$ (30)
$`p_1^2+p_2^2+p_3^2`$ $`=`$ $`6A9A^2.`$ (31)
In case $`A=1/3`$, this reduces to exact Kasner type solution. For $`B_\pm =0,A=1/2`$, we obtain the dark radiation dominated universe.

From the above solutions, we get $`\chi _{\pm 2}=(3A1)B_\pm /t^2`$. Using the previous formula, the effective Friedmann equation can be deduced as

$$H^2=\dot{\chi }_+^2+\dot{\chi }_{}^2+A(3A1)e^{2\alpha _0/A}.$$
(32)
If $`A>1/3`$, the bulk effect accelerate the expansion. The holographic projection of gravitational waves behaves as the fluid:

$$p=w\rho ,w=\frac{2}{3A}1.$$
(33)
In case $`A<1/3`$, the sound speed exceeds the velocity of light. So it violates the holographic principle formulated by Fishler and Susskind.

## 4 AdS/CFT correspondence

To analyze more general situations, we need a new apparatus. Here, we propose to use the AdS/CFT correspondence for that purpose. From AdS/CFT correspondence, we can deduce the low energy effective action for the brane world as

$`S_{5dEH}+\sigma {\displaystyle d^4x\sqrt{g_{brane}}}+S_{matter}={\displaystyle \frac{1}{16\pi G}}{\displaystyle d^4x\sqrt{g_{brane}}R}+S_{matter}`$
$`+W_{CFT}{\displaystyle \frac{l^3}{8\kappa ^2}}\mathrm{log}{\displaystyle \frac{ϵ}{l}}{\displaystyle d^4x\sqrt{g_{brane}}\left[R^{\mu \nu }R_{\mu \nu }\frac{1}{3}R^2\right]},`$ (34)
where $`ϵ`$ denotes the arbitraly parameter. In the case of FRW cosmology, the last term vanishes like as

$$d^4x\sqrt{g_{brane}}\left[R^{\mu \nu }R_{\mu \nu }\frac{1}{3}R^2\right]=4𝑑t\frac{d}{dt}[(\frac{\dot{a}}{N})^3]=0.$$
(35)
This result is consistent with the low energy effective Friedmann equation

$$\dot{\alpha }_0^2=\frac{8\pi G_4}{3}\rho +e^{4\alpha _0}C_0.$$
(36)
In contrast, for the Bianchi type I model, we have

$`{\displaystyle d^4x\sqrt{g_{brane}}\left[R^{\mu \nu }R_{\mu \nu }\frac{1}{3}R^2\right]}`$
$`=6{\displaystyle 𝑑te^{3\alpha }\left[(\ddot{\chi }_++3\dot{\alpha }\dot{\chi }_+)^2+(\ddot{\chi }_{}+3\dot{\alpha }\dot{\chi }_{})^2+4(\dot{\chi }_+^2+\dot{\chi }_{}^2)^2+2(\ddot{\alpha }\dot{\alpha }^2)(\dot{\chi }_+^2+\dot{\chi }_{}^2)\right]}.`$ (37)
This does not vanish in general. Hence, the correction which we found in this work must be identified with this term. It would be interesting to analyze the effcts of the gravitational waves on the brane world cosmology using this correspondence.

## 5 Conclusion

First we have suggested a possible extension of the AdS/CFT correspondence to Gravity/Quantum Field Theory correspondence in the case of the Kasner type exact solution

$$ds^2=(\frac{l}{y})^2\left(dt^2+dy^2+t^{2p_1}dx_1^2+t^{2p_2}dx_2^2+t^{2p_3}dx_3^2\right).$$

We have also shown that the bulk gravitational waves affect on the brane evolution as a perfect fluid with equation of state, $`p=w\rho ,w=2/3A1`$. As $`0A1/2`$, we obtain $`w1/3`$. In particular, if $`A1/3`$, the bulk effect is very stiff. Hence, it seems that the holographic principle is violated in the brane world. It is also pointed out that the effects of gravitational waves on the brane world cosmology can be investigated using the effective action derived from the AdS/CFT correspondence.


format: text

text:
# Thermodynamical aspects of the Casimir force between real metals at nonzero temperature

## I Introduction

Recent advances in experimental investigation of the Casimir effect (see Refs.  and the review ) have given impetus to extensive theoretical studies of different corrections to the Casimir force. Casimir force arises between two closely spaced neutral bodies due to the existence of zero-point electromagnetic fluctuations. It is one of the rare macroscopic manifestations of quantum phenomena. For this reason, it received widespread attention. Moreover, currently the Casimir effect finds applications in fundamental physics for constraining hypothetical forces predicted by different extensions to the standard model  and also in nanotechnology .

Originally the Casimir force was computed between two infinitely large plane parallel plates made of ideal metal . Corrections to this ideal result are caused by the geometrical factors (restricted area of the plates and surface roughness), finite conductivity of the boundary metal and nonzero temperature. Geometrical factors are detailly examined in the literature (see, e.g., their study in Refs.  and also in ). Corrections caused by the finite conductivity of a metal  and by nonzero temperature , when considered separately, also received much attention and wholly satisfactory results were obtained (see also ).

For experimental purposes the combined effect of different corrections to the Casimir force was found to be of large importance. The effect of surface roughness, combined with any other corrections, can be effectively computed by the method of geometrical averaging . So one comes face to face with the problem how to find the combined action of finite conductivity and nonzero temperature onto the Casimir force. At first glance it would seem that there is an easy way to solve this problem. Use could be made of the famous Lifshitz formula  for the Casimir force at nonzero temperature acting between two dielectric semispaces by the substitution of the dielectric permittivity function describing real metals (on the basis of the plasma model, Drude model or optical tabulated data for the complex refractive index). This was done recently by different authors  and unexpectedly led to conflicting results.

In Refs.  the corrections to the Casimir force due to the combined effect of the finite conductivity and nonzero temperature were calculated in the framework of the Lifshitz formula and of the free electron plasma model. The obtained results are in agreement. Temperature corrections are positive and smoothly transform to those for an ideal metal in the limit of infinite plasma frequency.

In Refs.  the Drude dielectric function was substituted into the Lifshitz formula. The temperature corrections to the Casimir force were found to be negative at small space separations between the plates. The asymptotic values of the Casimir force at high temperature (large separations) were found to be two times smaller than for ideal metal irrespective of how high the conductivity of real metal is. Thus, the results of  do not convert smoothly to the results, given by the plasma model, when the relaxation goes to zero and also to the results, found for an ideal metal, when the plasma frequency goes to infinity. So extraordinary properties of the obtained results were attempted to explain in  by the principal role of nonzero relaxation. Mathematically these properties are caused by the zero value of the reflection coefficient at zero frequency as given by the Lifshitz formula for photons with perpendicular polarization in the framework of the Drude model.

In Refs.  both the plasma and the Drude models were used supplemented by the special prescription modifying the zero-frequency term of the Lifshitz formula in the same way as was done in Ref.  for the case of an ideal metal. As a result, large temperature corrections arise to the Casimir force at small separations that are linear in temperature. At large separations (high temperatures), asymptotic of the Casimir force in  do not demonstrate any finite conductivity correction starting from a separation of several micrometers.

As explained in Refs. , actually the Drude model is outside of the application range of the Lifshitz formula and, specifically, the zero-frequency term of this formula must be modified in an appropriate way in order to incorporate the dissipative media. This was demonstrated on the basis of a new derivation of the Lifshitz formula  in the framework of quantum field theory in Matsubara formulation. In Ref.  the new prescription for the zero-frequency term of the Lifshitz formula was proposed which is not subject to the above-mentioned disadvantages (see also ). Discussions regarding the correct description of the thermal Casimir force between real metals are, however, being continued (see recent Comments  and Replies  supporting just the opposite points of view). The necessity to conclusively resolve a problem is apparent when it is considered that the experiment is already nearing the registration of the thermal corrections to the Casimir force.

In the present paper we analyse the thermal Casimir force between real metals on the basis of the fundamental principles of thermodynamics. Entropy for a system of photons between the realistic metallic plates is calculated. It is shown that in the approach of Refs. , entropy is negative within the separation range where the temperature correction to the Casimir energy density computed in  is negative. It is proved also that both in Refs.  on the one hand, and in  on the other hand the Nernst heat theorem, or the third law of thermodynamics, is violated. Thus, the approaches of Refs.  are unacceptable from the thermodynamical point of view. As for the results of Refs.  (for plasma model) and Refs.  (for Drude model), they are shown to be in agreement with the general principles of thermodynamics.

This paper is organized as follows. In Sec. II the general expression for the entropy of a system of photons between metallic plates is presented. Sec. III contains the computational results for the entropy in the framework of the Drude model using different approaches. In Sec. IV the analogical results obtained in the framework of the plasma model are given. In Sec. V the reader finds conclusions and discussion.

## II Entropy for photons between plates made of real metal

We consider two plane parallel plates made of real metal which are in thermal equilibrium with a heat reservoir at some nonzero temperature $`T`$. Let $`a`$ be the space separation between plates. The modern derivation of the free energy per unit area for the system under consideration is based on quantum field theory in the Matsubara formulation and $`\zeta `$-regularization method. The result is

$`F_E(a,T)={\displaystyle \frac{k_BT}{4\pi }}{\displaystyle \underset{l=\mathrm{}}{\overset{\mathrm{}}{}}}{\displaystyle _0^{\mathrm{}}}k_{}𝑑k_{}`$ (1)
$`\times \left\{\mathrm{ln}\left[1r_{||}^2(\xi _l,k_{})e^{2aq_l}\right]+\mathrm{ln}\left[1r_{}^2(\xi _l,k_{})e^{2aq_l}\right]\right\},`$ (2)
where

$$r_{||}^2(\xi _l,k_{})=\left[\frac{\epsilon (i\xi _l)q_lk_l}{\epsilon (i\xi _l)q_l+k_l}\right]^2,r_{}^2(\xi _l,k_{})=\left(\frac{q_lk_l}{q_l+k_l}\right)^2$$
(3)
with $`q_l=(\xi _l^2/c^2+k_{}^{}{}_{}{}^{2})^{1/2}`$, $`k_l=[\epsilon (i\xi _l)\xi _l^2/c^2+k_{}^{}{}_{}{}^{2}]^{1/2}`$ are the reflection coefficients for the modes corresponding to two different polarizations. Here $`\epsilon `$ is the frequency dependent dielectric permittivity of a plate material computed along imaginary frequency axis at discrete Matsubara frequencies $`\xi _l=2\pi lk_BT/\mathrm{}`$ with $`l=\mathrm{}2,1,\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}2}\mathrm{}`$, $`k_B`$ is the Boltzmann constant, and $`k_{}`$ is the modulus of the wave vector component in the plane of the plates.

The result (1) is obtained by the solution of a one-dimensional scattering problem on the axis perpendicular to the plates. In fact, an electromagnetic wave which is coming from the left in one semispace is scattered on the vacuum gap between semispaces and there are reflected and transmitted waves (see Refs.  for details).

It is important to keep in mind that the scattering problem leading to Eqs. (1), (3) has the definite solution only under the requirement that

$$\underset{\xi 0}{lim}\xi ^2\epsilon (i\xi )=C0.$$
(4)
If this is not the case (like for metals described by the Drude model or for dielectrics, see the next section) some additional conditions must be used to fix a solution of the scattering problem at zero frequency. As an example, for dielectrics the results (1), (3) are restated including the zero-frequency contribution by using the unitarity condition and dispersion relation. However, as to the case of the Drude model, describing a medium with dissipation, the unitarity condition is not applicable, and, therefore, a solution of the scattering problem at zero frequency remains indefinite. Due to this fact, metals described by the Drude model are outside of the application range of formulas (1), (3) for the Casimir free energy density at nonzero temperature. The special prescription concerning the zero-frequency term of Eq. (1) must be introduced in order that the dissipative media could be described on the basis of this equation. This prescription must be in accordance with the laws of thermodynamics and other general physical requirements.

It is easily seen that Eqs. (1), (3) lead to the famous Lifshitz formula  for thermal Casimir force between two semispaces which is obtained as $`F(a,T)=F_E(a,T)/a`$. Thus we arrived at the conclusion that the Drude metals are outside of the application range of the Lifshitz formula at nonzero temperature and a special prescription is needed in order to describe them in a consistent way.

In the limit of zero temperature, the Casimir energy density of the zero-point electromagnetic oscillations is reobtained from Eq. (1) as

$`E(a)={\displaystyle \frac{\mathrm{}}{4\pi ^2}}{\displaystyle _0^{\mathrm{}}}d\xi {\displaystyle _0^{\mathrm{}}}k_{}dk_{}\{\mathrm{ln}[1r_{||}^2(\xi ,k_{})e^{2aq_l}]`$ (5)
$`+\mathrm{ln}[1r_{}^2(\xi ,k_{})e^{2aq_l}]\}.`$ (6)
From (6) the Lifshitz formula for the Casimir force at zero temperature is obtained $`F(a)=E(a)/a`$. It is a nontrivial result that the Lifshitz formula at zero temperature is applicable for nondissipative as well as for dissipative media. This was demonstrated in Ref.  (see also ) through the consideration of a supplementary electrodynamical problem and is explained by the fact that the only point $`\xi =0`$ which gives an important contribution to the discrete sum (1) does not contribute to the integral (6).

Note that the generally accepted terminology “the Casimir energy density and force at zero temperature” is of some ambiguity. It is really correct in the sense that the sum of the zero-point energies (not the free energies) is computed. This terminology, however, disregards the fact that there is a significant thermal dependence of the energy density and force through the thermal dependence of the dielectric permittivity (see the next section). Because of this, when one calculates the Casimir energy density at, say, $`T=300`$K, the value of $`\epsilon (i\xi ,T)`$ is substituted into Eq. (6), not $`\epsilon (i\xi ,T=0)`$ (see, e.g., Refs. ). Thus, instead of $`E(a)`$, a more exact notation for the quantity (6) would be $`E_T(a)`$.

If we multiply (1) or (6) by $`2\pi R`$, where $`Ra`$ is a radius of a sphere at a separation $`a`$ from the semispace, one obtains the Casimir force in the configuration of a sphere near a plate at a temperature $`T`$, or at zero temperature, respectively .

According to thermodynamics, the entropy per unit area of the system under consideration is

$$S(a,T)=\frac{1}{T}\left[E_T(a)F_E(a,T)\right],$$
(7)
where $`F_E(a,T)`$ is given by Eq. (1) and $`E_T(a)E(a)`$ from Eq. (6). In the next sections entropy is calculated for the plates made of real metal as described by the Drude or plasma model dielectric functions. In doing so, special attention is paid to the zero-frequency term ($`l=0`$) in Eq. (1) and to the fulfilment of Eq. (4).

## III Entropy in the case of metallic plates described by the Drude model

It is common knowledge that the Drude dielectric function

$$\epsilon _D(\omega )=1\frac{\omega _p^2}{\omega (\omega +i\gamma )},$$
(8)
where $`\omega _p`$ is the plasma frequency and $`\gamma \omega _p`$ is the relaxation frequency, gives a good approximation of the dielectric properties for some metals, e.g., for aluminum. This approximation was widely used in combination with the Lifshitz formula (6) to calculate the finite conductivity corrections to the Casimir force at zero temperature . To do so the Drude dielectric function along the imaginary frequency axis was considered

$$\epsilon _D(i\xi )=1+\frac{\omega _p^2}{\xi (\xi +\gamma )}.$$
(9)
Before we proceed further, we note that the dielectric function (9) violates the requirement (4) for any nonzero value of the relaxation frequency $`\gamma `$. Due to this, as discussed in the previous section, the Drude metals are outside of the application range of the Lifshitz formula (1) at nonzero temperature with an unmodified zero-frequency term. If, nevertheless, one substitutes Eq. (9) into Eq. (1), as was done, e.g., in Refs. , several questionable results follow which are in contradiction with the limiting cases of metal described by the plasma model (see the next section) and of an ideal metal (see Introduction and a detailed discussion in Refs. ). Using the dielectric function of Eq. (9), the values of reflection coefficients (3) at zero frequency are the following

$$r_{||}^2(0,k_{})=1,r_{}^2(0,k_{})=0.$$
(10)
From the formal point of view, some troubles are connected with the second of Eqs. (10) because for an ideal metal $`r_{}^2(0,k_{})=1`$.

In order to present the crucial argument against the substitution of the Drude dielectric function (9) into the unmodified Lifshitz formula (1) at nonzero temperature, we calculate the entropy per unit area given by Eq. (7) in the framework of the Drude model. Thus, as an example, consider $`Al`$ plates with the parameters

$`\omega _p12.5\text{eV}1.9\times 10^{16}\text{rad/s},`$ (11)
$`\gamma 0.063\text{eV}9.6\times 10^{13}\text{rad/s}.`$ (12)
In Fig. 1 the computational results for the entropy are presented at $`T=300`$K as a function of the separation between the plates. Note that the plasma frequency practically does not depend on temperature. As to the value of the relaxation frequency from Eq. (11), it is given for the temperature under consideration. It is seen from the figure that the entropy is negative within a wide separation range that it not acceptable from a thermodynamical point of view. The separation interval $`0<a<4.1\mu `$m, where the entropy is negative, coincides with the interval where the negative temperature corrections arise in the approach used in  (see the detailed discussion in ). Negative temperature corrections are in conflict with the evident physical arguments (with increase of temperature the number of photons in the modes and thereby force modulus should increase). Here we show that they are also in contradiction with the general physical principles.

As noted in the Introduction, except of the immediate application of the Lifshitz formula in combination with the Drude model , different prescriptions were proposed in literature modifying the zero-frequency term of this formula in the case of real metals. In  it was postulated that

$$r_{||}^2(0,k_{})=r_{}^2(0,k_{})=1,$$
(13)
as in the case of an ideal metal. This prescription was criticized on physical grounds in .

In Ref.  the other prescription was proposed which is the generalization of the prescription of Ref. , formulated for an ideal metal. According to  in the framework of the Drude model the reflection coefficients at zero frequency are

$$r_{||}^2(0,k_{})=1,r_{}^2(0,k_{})=\left(\frac{ck_{}\sqrt{\frac{\omega _p^2ck_{}}{ck_{}+\gamma }+c^2k_{}^2}}{ck_{}+\sqrt{\frac{\omega _p^2ck_{}}{ck_{}+\gamma }+c^2k_{}^2}}\right)^2.$$
(14)
As shown in , prescription (14) leads to wholly satisfactory results.

In order to test all the above approaches for conformity to the general principles of thermodynamics, we find the dependence of the entropy (7) on temperature at some fixed plate separation, say, $`a=2\mu `$m. To accomplish this, one should take into consideration that except of the evident dependence of Eqs. (1) and (7) on temperature there is the aforementioned significant thermal dependence of $`\epsilon _D`$ given by Eq. (9) through the relaxation parameter $`\gamma =\gamma (T)`$ (coinciding with the thermal dependence of resistance). The dependence $`\gamma (T)`$ is linear at temperatures higher than $`0.25T^{}`$, where $`T^{}`$ is the Debye temperature ($`T^{}=428`$K for $`Al`$ ). At lowest temperatures $`\gamma (T)`$ follows the power law $`T^n`$ ($`n=25`$ depending on the metal). The complete dependence of the nondimensional normalized quantity $`\stackrel{~}{\gamma }(T)2a\gamma (T)/c`$ on the temperature is plotted in Fig. 2 by the use of tabulated data for $`Al`$  (here we neglect the small residual resistivity caused by the scattering of electron waves by static defects that is outside of the frameworks of the Drude model ).

Now we are in a position to calculate the dependence of entropy on temperature for all the above approaches. Calculation was performed using Eq. (7) and also Eqs. (1), (6), (9) and Fig. 2. The results are presented in Fig. 3. The long-dashed curve is obtained on the basis of the Lifshitz formula with an unmodified zero-frequency term (i.e., Eq. (10) was used for the reflection coefficients at zero frequency). Remind that this approach was exploited in Refs. . The short-dashed curve is calculated with the modification of the zero-frequency term of the Lifshitz formula in accordance with Eq. (13) (approach of Refs. ). The solid curve is calculated with the modification of the zero-frequency term according to Eq. (14) suggested in Ref. . Note that all the above approaches differ by the value of the zero-frequency term only for perpendicular polarization.

As is quite clear from Fig. 3, for both long-dashed and short-dashed curves the values of entropy at zero temperature are not equal to zero. In the approach used in  $`S_1(0)=0.5\text{MeV}\text{m}^2\text{K}^1`$, and in the approach used in  $`S_2(0)=0.016\text{MeV}\text{m}^2\text{K}^1`$. In both cases the value of $`S(0)`$ depends on the parameters of the system under consideration (like the separation between the plates and the plasma frequency) that is in manifest contradiction with the third law of thermodynamics (the Nernst heat theorem ). It is notable that the entropy density given by the long-dashed curve is negative in a wide temperature range (compare with Fig. 1 where the result at a fixed temperature is presented). It is easily shown that the values of entropy density at zero temperature, given by the dashed curves, are related by

$$S_2(0)S_1(0)=\frac{k_B\zeta (3)}{16\pi a^2},$$
(15)
where $`\zeta (3)`$ is the Riemann zeta function. The right-hand side of Eq. (15) is equal to one-half of the coefficient near temperature in the zero-frequency term of the Lifshitz formula for an ideal metal. This is because in  the same values (13) for the reflection coefficients at zero frequency were postulated as for an ideal metal, whereas in , according to (10), one-half of the result for an ideal metal was used. In fact the correct result for a real metal lies in between of these two possibilities.

Contrary to the dashed curves, for the solid curve (approach of Ref. ), $`S(0)=0`$ and therefore, in accordance with the laws of thermodynamics.

## IV Entropy in the case of metallic plates described by the plasma model

For the free-electron plasma model the dependence of dielectric function on the frequency is given by

$$\epsilon _p(\omega )=1\frac{\omega _p^2}{\omega ^2},\epsilon _p(i\xi )=1+\frac{\omega _p^2}{\xi ^2}.$$
(16)
This dependence was widely used to calculate the finite conductivity corrections to the Casimir force at the separations of order $`1\mu `$m . In Refs.  it was applied to compute the effect of nonzero temperature and finite conductivity in the framework of the Lifshitz formula (1). Note that the plasma dielectric function practically does not depend on temperature.

The preference for the plasma model as compared with the Drude one is the fulfilment of condition (4) with the dielectric function (16). As a consequence, the scattering problem underlying the Lifshitz theory has a definite solution leading to Eqs. (1), (3), (6) including the zero-frequency contribution. The reflection coefficients (3) at zero frequency in the framework of the plasma model take the form

$$r_{||}^2(0,k_{})=1,r_{}^2(0,k_{})=\left(\frac{ck_{}\sqrt{\omega _p^2+c^2k_{}^2}}{ck_{}+\sqrt{\omega _p^2+c^2k_{}^2}}\right)^2.$$
(17)
Note that Eq. (17) can be obtained from Eq. (14) when the relaxation frequency goes to zero. Because of this, in the approach of  the results for the plasma model are obtainable from the results for the Drude model in a limitimg case $`\gamma 0`$ (the results obtained in  by the use of the Drude model on the basis of Eq. (10) have no smooth connection with a plasma model approach; the plasma model by itself is not considered in ). In the alternative approach , as distinct from both  and , the conditions (13) are postulated in the framework of both Drude and plasma models.

Now let us find the dependence of the entropy density on temperature in the framework of the plasma model on the basis of different approaches. As an example, $`Al`$ plates are used once more at a separation $`a=2\mu `$m. The value of the plasma frequency for $`Al`$ is given by Eq. (11) . Calculations were performed using Eqs. (1), (6), (7), (9) and (16). The results are presented in Fig. 4. The dashed curve is obtained in the framework of Refs.  using prescription (13). The solid curve is calculated on the basis of Refs.  with no modification of the Lifshitz formula, i.e. with the zero-frequency reflection coefficients (17).

As is obvious from Fig. 4, for the dashed curve the value of entropy at zero temperature $`\stackrel{~}{S}(0)=S_2(0)=0.016\text{MeV}\text{m}^2\text{K}^1`$ and is not equal to zero. It depends on the parameters of the system that is in contradiction with the third law of thermodynamics. In contrast to this, for the solid curve obtained on the basis of the fundamental Lifshitz formula, $`S(0)=0`$ as it must be from the third law of thermodynamics.

In the framework of the plasma model it is not difficult to obtain the analytical expression for the entropy at low temperatures $`k_BTk_BT_{eff}\mathrm{}c/(2a)`$. For this purpose the perturbation expansion of the Casimir energy and free energy in powes of two small parameters $`\delta _0/a=c/(a\omega _p)`$ and $`T/T_{eff}`$ can be used (see Refs.  where these expansions are presented in details; they are applicable for separations $`a\lambda _p=2\pi c/\omega _P`$ where $`\lambda _p`$ is the effective plasma wavelength). Substituting the mentioned perturbation expansions into Eq. (7), one obtains

$`S(a,T)={\displaystyle \frac{k_B\zeta (3)}{8\pi a^2}}\left({\displaystyle \frac{T}{T_{eff}}}\right)^2\{1{\displaystyle \frac{\pi ^3}{45\zeta (3)}}{\displaystyle \frac{T}{T_{eff}}}`$ (18)
$`+2{\displaystyle \frac{\delta _0}{a}}[1{\displaystyle \frac{2\pi ^3}{45\zeta (3)}}{\displaystyle \frac{T}{T_{eff}}}]\}.`$ (19)
Here the terms up to $`(T/T_{eff})^3`$ were included. The powers of $`\delta _0/a`$ higher than one are contained only with powers $`(T/T_{eff})^n`$, $`n>3`$. This analytical expression corresponds to the solid curve in Fig.4. It is seen from Eq. (18) that the entropy approaches zero as the second power of temperature in the framework of the unmodified Lifshitz formula.

On the basis of the approach proposed in Refs.  the perturbation expansion of entropy is given by

$$\stackrel{~}{S}(a,T)=\frac{k_B\zeta (3)}{4\pi a^2}\frac{\delta _0}{a}\left(13\frac{\delta _0}{a}\right)+S(a,T),$$
(20)
where $`S(a,T)`$ is expressed by Eq. (18). The first contribution in the right-hand side of Eq. (20) is the value of entropy at zero temperature

$$\stackrel{~}{S}(a,0)=\frac{k_B\zeta (3)}{4\pi a^2}\frac{\delta _0}{a}\left(13\frac{\delta _0}{a}\right)0.$$
(21)
At $`a=2\mu `$m one obtains from Eq. (21) the above value of $`S_2(0)`$. $`\stackrel{~}{S}(a,0)`$ depends on both the separation between the plates $`a`$ and the penetration depth of the electromagnetic oscillations into the plate material $`\delta _0`$ in contradiction with the third law of thermodynamics .

## V Conclusion and discussion

In the foregoing we have considered the thermodynamical aspects of the Casimir force acting between real metals at nonzero temperature. The necessity of considering these aspects stems from the controversial results obtained by different authors (see Refs. ) and continuing polemic . The further importance to this problem is added by the rapid progress in experiment on measuring the Casimir force. At the moment, there is a contradiction between the experimental results of  and the theoretical approach of  which leads to large negative temperature corrections at separation of about $`1\mu `$m (see the discussion in ). On the other hand, the experimental results of  do not agree with the computations of  that lead to large (although positive) linear in temperature corrections to the Casimir force at separations of about 100 nm (see ).

Bearing in mind that there are many influential factors in so precise experiments, it is highly desirable to offer some decisive theoretical arguments providing a way to give preference to one of the theoretical approaches. As shown above, thermodynamics gives the possibility to make a selection and to reject the approaches that are not in accordance with the most fundamental physical principles.

In the present paper we calculated the entropy density for photons between two parallel plates made of real metals described by the Drude or plasma models. It is shown that in the approach of Refs. , based on a direct application of the unmodified Lifshitz formula in the case of Drude metals, entropy takes negative values in a wide range of related parameters. The value of entropy density at zero temperature, as given by the approach of , is shown to be nonzero and dependent on the parameters of the system under consideration in contradiction with the Nernst heat theorem. These unacceptable properties of entropy confirm the conclusion of Refs.  that the dissipative metals described by the complex dielectric permittivity of real frequency are outside of the application range of the Lifshitz formula at nonzero temperature. To describe the thermal Casimir force for such metals a special prescription should be adopted modifying the zero-frequency term of the Lifshitz formula.

One prescription of this kind (the same as was proposed in  for the case of ideal metal) was suggested in Refs. . We show that although the entropy density in the approach of  is positive, the value of entropy at zero temperature is not equal to zero and depends on the parameters of the system. Thus, this approach is also in contradiction with the third law of thermodynamics.

One more prescription for the zero-frequency term of the Lifshitz formula was proposed in . It is the generalization of the receipt of  for the case of real metals. We show that for the prescription suggested in , entropy is non-negative at all temperatures and takes zero value at zero temperature. Hence the prescription of Ref.  is in agreement with the general principles of thermodynamics.

In this paper we report also the results of the computation of the entropy in the framework of the plasma model. The plasma model does not take dissipation into account. It belongs to the application range of the Lifshitz formula. It is shown that the application of the unmodified Lifshitz formula in combination with the plasma model leads to wholly satisfactory results: the entropy density is positive and takes zero value at zero temperature. The application of the modified Lifshitz formula, as in Refs. , leads to the violation of the third law of thermodynamics.

To conclude, the approach of Refs.  on the one hand and of Refs.  on the other hand must be rejected as they are in contradiction with the general principles of thermodynamics. In the case of the Drude metals only the approach of Ref.  fits thermodynamical requirements. It is also in accordance with the present experimental results. As to the case of the plasma metals with no account of dissipation, the unmodified Lifshitz formula is applicable and the results of Refs.  are in agreement between themselves and with the general principles of thermodynamics.

## ACKNOWLEDGMENTS

The authors are grateful to CNPq for partial financial support.


text:
# Optimal Solutions for Multi-Unit Combinatorial Auctions: Branch and Bound Heuristics

## 1 Multi-unit combinatorial auctions (MUCAs)

Auctions have been used from times immemorial, but the renewed modern interest in auctions stems from:

* their increased use for selling off government property after WWII and later in extensive denationalizations, and
* the theoretical breakthroughs started by .

A very recent surge of interest in auctions stems from their surprising success on the internet. Many foresee internet auctions in which:

* the number of buyers will be large
* the number of items for sale will be large
* the mechanism used to determine the allocation and the payment will be complex both from the game-theoretic strategic and from the computational points of view.

This work deals with computational aspects of winner determination in multi-unit combinatorial auctions. Combinatorial auctions are mechanisms in which a number of items are up for sale and bidders bid for subsets of those items. In combinatorial auctions one typically assumes that all items for sale are different. Computational aspects of combinatorial auctions have been considered in . Multi-unit combinatorial auctions are those combinatorial auctions in which certain of the items for sale are identical. We assume $`n`$ different commodities and $`k_j`$ identical items of commodity $`j`$ for $`j=1,\mathrm{}n`$. The problem we are trying to solve is that of determining the optimal allocation of the items. A set of bids is given: each bid requests a number of units (possibly zero) from each commodity and offers a price $`p`$ for the whole set. A subset of the set of all bids is conflict-free if, for each commodity, the sum of the units requested does not surpass the number of units for sale. The problem is to find a conflict-free subset that maximizes the sum of the prices proposed. Multi-unit combinatorial auctions have been considered in .

## 2 Branch-and-Bound search

The problem of finding the optimal solution of a multi-unit combinatorial auction is a hard problem, i.e., requires extensive resources, as will be shown formally in Section 5. It is therefore essential that one designs carefully the algorithm and uses the available resources smartly. The method we propose to use is based on the branch-and-bound search technique developed by operations researchers . The use of some branch-and-bound techniques for finding optimal solutions for combinatorial auctions has been considered in  and more thoroughly in . The case of multi-unit combinatorial auctions is considered in  where a wealth of heuristics are proposed. This paper concentrates on the fundamentals and characterizes the best ordering heuristics.

The general description of the branch-and-bound technique below is well-known. The resource in shortest supply is space (i.e. memory) and therefore we propose to use a depth-first search, with backtracking to cover the whole search space. At any time we essentially keep in memory only a partial solution, i.e., a set of non-conflicting bids. We look for a bid that can be added to the partial solution without creating a conflict and if there is none, know we have attained a possible solution and backtrack. The additional information of which we need to keep track consists only of the best solution found so far and backtracking information. On the whole the space requirements are linear in the size of the problem. Note that, at any time, we have allocated part of the items and are left with a smaller problem of the same type: finding the optimal solution of another, smaller, MUCA.

An exhaustive search such as sketched above will require exponential time for all possible inputs. One may hope to find an algorithm that will run faster on the easy inputs. Even though the theoretical considerations of Section 5 seem to preclude that there be a majority of easy cases, one may hope that many of the problems that will have to be solved in practice will turn out to be easy. We are hoping for an algorithm that will run fast on those easy problems. The powerful branch-and-bound idea is that, in many situations, we may be able to conclude on the spot that adding a specific bid to our partial solution is hopeless and that we can immediately backtrack, saving us the exploration of a whole sub-tree, i.e., enabling us to prune a whole sub-tree. All we need for that is a good upper-bound for the value of the optimal solution of the smaller MUCA concerning the items still unallocated. If we have such an upper bound and if the sum of this upper bound and the values of the bids of our partial solution is not larger than the value of the best solution found so far, we may backtrack immediately: no extension of our partial solution may have a value larger than that of the solution we already know. In Section 3, we shall propose a number of ways to bound from above the value that can be obtained from auctioning the still unallocated goods. There is obviously no need to commit to a single method: one may use many such methods, obtain a number of different upper bounds and use the smallest of all.

The pruning described above is most effective if the best solution found so far, that is used to decide whether to prune or not, is in fact a good solution. If we find the optimal (or a very good) solution early on, even though we shall not know that it is the optimal solution (or how good it is), we shall be able to prune more sub-trees than if we had a best solution so far that is not as good. It is therefore essential that we find the best solutions early on. We should, therefore, carefully choose the order in which we try to enter the bids into partial solutions and try the most promising bids first. To summarize, we need a good heuristic to pick the most promising bid in a set of bids, and this is the third component of branch-and-bound method. We shall use such a heuristic to find the most promising bid in the smaller MUCA concerning the items still unallocated iteratively to find the most promising of those bids that does not conflict with the partial solution at hand. We shall then use the upper-bound described above to decide whether to prune the whole sub-tree or not. Notice that we do not propose to rank the bids once and for all: the most promising bid may depend on the partial solution at hand. For example, the normalized criteria described below in Equations 5 and 7 imply such a dependency. In  the heuristic proposed to choose the next bid takes into account the whole set of bids. We restrict our attention to heuristics that consider each bid separately. In Section 4 we shall consider different criteria for this task and in Section 5 we shall characterize the best one. It turns out that this optimal criterion does not depend on the partial allocation, or, equivalently, on the set of items still unallocated, and therefore one can simply order the bids according to this criterion once and for all at the start of the algorithm.

In this paper, we shall assume that any subset of bids such that, for any commodity, the sum of the units requested does not exceed the total number of units available is a legal solution. We shall not consider explicitly the case in which certain bids are exclusive, i.e., no legal solution can contain certain pairs of bids. The generalization of our (and essentially any) branch and bound algorithm to the case of possibly exclusive bids is quite straightforward, though: when considering whether to add a specific bid to a partial allocation, check not only whether there are enough units left to satisfy it and whether the sub-tree can be pruned, check also whether the bid considered is not excluded by some bid of the partial solution.

## 3 Bounding from above

We noticed that, at any point, we have a partial allocation, i.e. a set of non-conflicting bids, and are trying to extend it. The best possible extension is, again, the optimal solution to the MUCA of the remaining units to the remaining bids. We shall therefore look for ways to bound from above the value of any MUCA. We also noticed that one may use a number of different methods, obtain numerous upper-bounds, and take the smallest one. We propose three different types of methods.

### 3.1 Linear Programming

The first method we propose is Linear Programming. Our problem is an integer-programming problem: find $`x_i`$ $`\{0,1\}`$ for each bid $`i`$ that maximizes $`_ix_ip(i)`$ while satisfying the linear constraints: $`_ix_iq(i,j)k_j`$. The variable $`x_i`$ indicates whether bid $`i`$ is in the optimal solution ($`x_i=1`$) or out of it ($`x_i=0`$). The relaxed linear programming problem in which we allow $`x_i[0,1]`$ will provide a value $`_ix_ip(i)`$ that is an upper-bound for the value of the optimal solution to the original MUCA. Notice that the solution of the relaxation allows for fractional allocation of bids: $`x_i=1/2`$ may be interpreted as allocating half of the quantities requested by $`i`$ at half the price proposed. In the worst case, for theoretical reasons, it seems that the upper bound provided by LP cannot be good, but there are reasons to think that in practice, and especially for large $`k_j`$’s the bound could be pretty good quite often. An extended discussion of the relation between the solutions to the original and the relaxed problems may be found in .

Notice also that, if the optimal solution to the relaxed problem is integral, then we know it is the optimal solution to the original problem. The integrality of the solution to the LP problem is the signal for backtracking.

### 3.2 Projections

Another, quite different, idea is to consider only one commodity. By projecting bid $`i`$ on commodity $`j`$, to $`i^{}=`$ $`0,\mathrm{}`$, $`q(i,j),\mathrm{}`$, $`0,p(i)`$, we transform our original MUCA into a knapsack problem. The optimal solution to the knapsack problem is obviously an upper bound for the optimal solution of the original MUCA. The knapsack being polynomially-approximable at any precision, one may easily obtain an upper bound in this way, in fact $`n`$ such upper bounds, one for each commodity.

### 3.3 Average price consideration

The bounds described above are not difficult to compute and quite different in spirit (and probably results). Our next bound is related to the Linear Programming one of Section 3.1: it always provide an upper bound that is larger than or equal to the one provided by LP, but it is extremely easy to compute. Consider the average price per unit for bid $`i`$: $`a(i)=p(i)/_{j=1}^nq(i,j)`$. Suppose $`a`$ is the largest of the $`a(i)`$’s. Then clearly the value of the optimal solution to the MUCA is bounded from above by $`a_{j=1}^nk_j`$. The value of the optimal solution to the relaxed LP problem is also bounded by this quantity.

## 4 Choosing the most promising bid

Given positive integers $`k_1,\mathrm{},k_n`$, how should one compare the attractiveness, at first sight, of two bids $`a=`$ $`q_1,q_2,\mathrm{}`$, $`q_n,p`$ and $`a^{}=`$ $`q_1^{},q_2^{},\mathrm{}`$, $`q_n^{},p^{}`$? We may as well say we are looking for a criterion $`r`$, i.e. a real-valued function of the bid $`a`$, possibly depending on the parameters $`k_j`$’s such that $`r(a)r(a^{})`$ iff $`a`$ is more promising than $`a^{}`$.

Some obvious considerations may be made immediately. The corresponding heuristics have been incorporated in . If the quantities $`q_j`$ and $`q_j^{}`$ are equal, but $`p`$ is larger than $`p^{}`$, one should obviously prefer $`a`$ to $`a^{}`$ and in fact, since the two bids conflict, one can remove $`a^{}`$ from consideration. Similarly, if the prices $`p`$ and $`p^{}`$ are equal and $`q_jq_j^{}`$ for every $`j`$, $`1jn`$, then one should prefer $`a`$ to $`a^{}`$ and remove $`a^{}`$ from consideration. In other terms, the function $`r`$ should be monotonic in $`p`$ and anti-monotonic in the $`q_j`$’s. Notice that any such function will have the effect of removing from consideration all the dominated bids as above.

Many functions come to mind. The simplest one is probably:

$$r(a)=p,$$
(1)
i.e., order the bids by the price they propose. The most natural function that comes to mind is probably:

$$r(a)=\frac{p}{_{j=1}^nq_j},$$
(2)
that orders the bids by average price per unit. But one may prefer to normalize the elements of the sum by the number of units of each commodity that are available and use:

$$r(a)=\frac{p}{_{j=1}^nq_j/k_j}.$$
(3)
If one has a geometrical bind one may prefer the Euclidean:

$$r(a)=\frac{p}{\sqrt{_{j=1}^nq_j^2}},$$
(4)
or the normalized:

$$r(a)=\frac{p}{\sqrt{_{j=1}^n(q_j/k_j)^2}}.$$
(5)
A previous result on combinatorial auctions  suggests the consideration of:

$$r(a)=\frac{p}{\sqrt{_{j=1}^nq_j}},$$
(6)
or of:

$$r(a)=\frac{p}{\sqrt{_{j=1}^nq_j/k_j}}.$$
(7)
Many other criteria could be considered, of the form:

$$r(a)=\frac{p}{(_{j=1}^nq_j^l)^m}$$

or

$$r(a)=\frac{p}{(_{j=1}^n(q_j/k_j)^l)^m}$$

It is extremely difficult to guess what is the best criterion to use in a branch-and-bound algorithm. Experimental results would be interesting and we are in the process of obtaining such results but the lack of real-life data casts a doubt on the applicability of the conclusions that can be drawn from synthesized data.

Based on each of those criteria, one can devise a (different) greedy algorithm to find a solution to MUCAs: pick the most promising bid in the partial solution, then find the most promising remaining bid that does not conflict with the partial solution, and so on until no bid can be added. We are looking for the criterion that gives the best greedy algorithm. In what sense? We choose to compare greedy algorithms by the approximation ratio they provide in the worst-case. A greedy algorithm that provides, on any MUCA, a solution that is at least one-tenth of the optimal solution will be preferred to any algorithm that provides only one-hundredth of the optimal solution on some MUCA. Notice that we could assume a probability distribution on the inputs and compare the expected values of the solutions found (or their ratio to the optimal one), but this is not what we propose to do. Our choice is consistent with that of the theoretical CS community. The next section is devoted to theoretical considerations leading to the characterization of the best criterion.

## 5 Theoretical considerations:
the weighted multi-set packing (WMSP) problem

The problem of finding an optimal allocation in a multi-unit combinatorial auction is best described as a generalization of the weighted set packing problem : the weighted multi-set packing problem. It seems the same problem has been studied in .

We consider $`n`$ commodities and assume $`k_j`$ units of each of $`n`$ commodities: $`j=1,\mathrm{},n`$ are available. The $`k_j`$’s are positive natural numbers. We shall denote by $`k`$ the quantity $`_{j=1}^nk_j`$. On the whole $`k`$ items are to (may) be allocated. A bid is written: $`q_1,q_2,\mathrm{},q_n,p`$, where the $`q`$’s are natural numbers with $`q_jk_j`$ and $`p`$ is a natural number (or a rational nonnegative number). A bid is an offer to acquire $`q_j`$ units of each commodity $`j`$ for a total sum of $`p`$. Given a set of bids we want to find a subset that maximizes the sum of the $`p`$’s such that for every $`j`$, $`1jn`$, the sum of the $`q_j`$’s is less than or equal to $`k_j`$. A number of special cases are worth noticing:

* if all $`k_j`$’s are equal to one, the problem is the weighted set packing (WSP) problem,
* if there is only one commodity ($`n=1`$), the problem is the knapsack problem.

Our first result, a trivial generalization from , shows that the WMSP problem is not only NP-hard but also hard to approximate.

###### Theorem 1

Unless NP=ZPP111A language $`L`$ belongs to ZPP if and only if there is some constant $`c`$ such that there is a probabilistic Turing machine $`M`$ that on input $`x`$ runs in expected time $`O(x^c)`$ and outputs $`1`$ if and only if $`xL`$, the WMSP problem cannot be approximated within $`n^{1/2ϵ}`$ in polynomial time, for any $`ϵ>0`$.

###### Proof 5.2.

A graph with $`v`$ vertices and $`e`$ edges defines a WMSP problem in the following way. Consider $`e`$ commodities ($`n=e`$) and assume $`k_j`$ units of commodity $`j`$ are for sale. The $`k_j`$’s are arbitrary. There are $`v`$ bids. Bid $`i`$ offers a price of $`1`$ for $`k_j`$ units of each of the commodities (i.e. edges) $`j`$ that vertex $`i`$ is adjacent to. Any feasible allocation defines a set of independent vertices and its value is the size of the independent set. The solution of the WMSP problem is therefore equivalent to finding a maximal independent set. An $`f(n)`$-approximation of the WMSP problem provides an $`f(e)`$-approximation of the Maximal Independent Set problem. By , no efficient $`k^{1ϵ}`$-approximation exists for the maximal independent set problem, therefore no $`e^{1/2ϵ}`$-approximation, unless NP=ZPP.

In  it is shown that the WSP problem admits a polynomial-time $`n^{1/2}`$-approximation and that there is a greedy algorithm that achieves this (optimal) approximation ratio. Notice that finding a polynomial-time $`k^1`$-approximation of the Maximal Independent Set is trivial, but finding such an $`n^{1/2}`$-approximation for WSP is not. In the more general case of WMSP problems, we shall characterize the approximation quality of greedy algorithms as $`\sqrt{k}=\sqrt{_{j=1}^nk_j}`$ in Theorems 5.3 and 5.5, but we do not know how to match the lower bound of Theorem 1. For reasons explained above, we are interested in solving (approximately) WMSP problems by a greedy algorithm. For such algorithms, we may prove a result that is stronger than Theorem 1.

###### Theorem 5.3.

No (polynomial-time) greedy algorithm can guarantee an approximation of better than $`\sqrt{k}`$.

###### Proof 5.4.

Define a unit bid as a bid offering a sum of $`1`$ for a single unit of a single commodity: $`0,0,\mathrm{},1,\mathrm{},0,1`$. There are $`n`$ different unit bids, but the same unit bid may appear a number of times in the list of bids. Given a greedy algorithm, let $`u`$ be the unit bid that is ranked first among all unit bids by the algorithm.

Two problems, i.e., sets of bids, will be described. A greedy algorithm will perform badly, i.e. propose a solution that is only a $`\sqrt{k}`$-approximation, on one of those two problems. In the first problem, there are only two bids:

1. a bid for all the units available: $`A=`$ $`k_1,k_2,\mathrm{}`$, $`k_n,\sqrt{k}`$, and
2. a bid $`u`$.

In the second situation, there are $`k+1`$ bids:

1. a bid $`A`$ for all the units available as above, and
2. for every $`j`$, $`j=1,\mathrm{},n`$, $`k_j`$ unit bids for commodity $`j`$: $`0,0,\mathrm{},1,\mathrm{},0,1`$.

If bid $`A`$ is ranked before $`u`$, then, in the second situation, the greedy method obtains $`\sqrt{k}`$ instead of the optimal $`k`$, a $`\sqrt{k}`$-approximation. If bid $`u`$ is ranked before bid $`A`$, then, in the first situation the greedy method obtains $`1`$ instead of the optimal $`\sqrt{k}`$, again a $`\sqrt{k}`$-approximation. For any greedy method, one of the two situations will give a solution that is a factor of $`\sqrt{k}`$ less than optimal.

The following positive result provides an upper-bound that matches the lower bound of Theorem 5.3.

###### Theorem 5.5.

A greedy algorithm (to be described) provides a polynomial-time $`\sqrt{k}`$-approximation for the WMSP problem.

###### Proof 5.6.

We shall use the index $`i`$ to range over the bids. The bid $`i`$ is: $`i=q(i,1),q(i,2),\mathrm{},q(i,n),p(i)`$. We define $`w(i)=\sqrt{_{j=1}^nq(i,j)}`$. The algorithm we propose is greedy allocation based on the following criterion $`r`$ to rank the bids, in descending order:

$$r(i)=\frac{p(i)}{w(i)}$$
(8)
Let $`OP`$ be the optimal solution, i.e., the set of bids contained in the optimal solution. The value of the optimal solution is $`\alpha =_{iOP}p(i)`$. Let $`GR`$ be the solution obtained by the greedy allocation and $`\beta `$ its value: $`\beta =_{iGR}p(i)`$. We want to show that:

$$\alpha \beta \sqrt{k}.$$
(9)
Notice, first, that we may, without loss of generality, assume that the sets $`OP`$ and $`GR`$ have no bid in common. Indeed, if they have, one considers the problem in which the common bids and all the units they request have been removed. The greedy and optimal solutions of the new problem are similar to the old ones and the inequality for the new smaller problem implies the same for the original problem.

Let us consider $`\beta `$. By elementary algebraic considerations:

$$\beta =\underset{iGR}{}p(i)\sqrt{\underset{iGR}{}p(i)^2}=\sqrt{\underset{iGR}{}r(i)^2w(i)^2}=$$

$$\sqrt{\underset{iGR}{}r(i)^2\underset{j=1}{\overset{n}{}}q(i,j)}=\sqrt{\underset{j=1}{\overset{n}{}}\underset{iGR}{}r(i)^2q(i,j)}.$$

Consider $`\alpha `$. By the Cauchy-Schwarz inequality:

$$\alpha =\underset{iOP}{}r(i)w(i)\sqrt{\underset{iOP}{}r(i)^2}\sqrt{\underset{iOP}{}w(i)^2}.$$

But:

$$\underset{iOP}{}w(i)^2=\underset{iOP}{}\underset{j=1}{\overset{n}{}}q(i,j)=\underset{j=1}{\overset{n}{}}\underset{iOP}{}q(i,j).$$

The expression $`_{iOP}q(i,j)`$ represents the total number of units of commodity $`j`$ allocated in the optimal allocation $`OP`$ and is therefore bounded from above by $`k_j`$, the number of units available. We conclude that:

$$\alpha \sqrt{\underset{iOP}{}r(i)^2}\sqrt{k}.$$

To prove (9), it will be enough, then, to prove that:

$$\underset{iOP}{}r(i)^2\underset{j=1}{\overset{n}{}}\underset{iGR}{}r(i)^2q(i,j).$$

Consider the optimal solution $`OP`$. By assumption, the bids of $`OP`$ did not enter the greedy solution $`GR`$. This means that, at the time such a bid $`i`$ is considered during the execution of the greedy algorithm, it cannot be entered in the partial allocation already built. This implies that there is a commodity $`j`$, not enough units of which are still unallocated to satisfy the quantity $`q(i,j)`$ requested by bid $`i`$. In other terms the sum of $`q(i,j)`$ and the $`q(,j)`$ of all the bids of the greedy solution already considered was larger than $`k_j`$:

$$q(i,j)+\underset{lGR,r(l)r(i)}{}q(l,j)>k_j.$$

In particular it follows that $`q(i,j)>0`$ and therefore $`q(i,j)1`$. We attach to every bid $`i`$ of $`OP`$ such a commodity $`c(i)`$. If more than one such suitable commodity exists, we choose one arbitrarily. Let $`OP_j`$ be the subset of $`OP`$ that contains those bids $`i`$ for which $`c(i)=j`$. The $`OP_j`$ provide a partition of $`OP`$ and:

$$\underset{iOP}{}r(i)^2=\underset{j=1}{\overset{n}{}}\underset{iOP_j}{}r(i)^2.$$

Let us denote by $`m_j`$ the size of the set $`OP_j`$. We shall conclude the proof by showing that, for every $`j`$, $`1jn`$:

$$\underset{iOP_j}{}r(i)^2\underset{iGR}{}r(i)^2q(i,j).$$

Let $`l_j`$ be a bid of $`OP_j`$ whose $`r`$ is maximal (among bids of $`OP_j`$) and let $`r_j=r(l_j)`$. We know that:

$$\underset{iOP_j}{}r(i)^2r_{j}^{}{}_{}{}^{2}m_j.$$

We want to bound $`m_j`$ from above. We remarked above that:

$$q(l_j,j)+\underset{lGR,r(l)r_j}{}q(l,j)>k_j.$$

and that $`q(l,j)1`$ for every $`lOPT_j`$. Therefore:

$$k_j\underset{lOP_j}{}q(l,j)q(l_j,j)+m_j1>$$

$$k_j\underset{lGR,r(l)r_j}{}q(l,j)+m_j1$$

and therefore $`m_j_{lGR,r(l)r_j}q(l,j)`$. Clearly, then:

$$r_{j}^{}{}_{}{}^{2}m_jr_{j}^{}{}_{}{}^{2}\underset{lGR,r(l)r_j}{}q(l,j)$$

$$\underset{lGR,r(l)r_j}{}r(l)^2q(l,j)\underset{lGR}{}r(l)^2q(l,j)$$

Theorems 5.3 and 5.5 show that the criterion of Equation 6 is optimal, in a worst-case sense.

###### Corollary 5.7.

The criterion proposed in Equation 6 for choosing the most promising bid guarantees, in the worst-case, the best possible approximation ratio.

None of the other criteria examined in Section 4 achieves the same approximation ratio. Let us show this explicitly for the normalized criterion of Equation 7, and characterize exactly the approximation ratio achieved by this criterion.

Along the lines of the proof of Theorem 5.5, one can show that using the normalized ranking criterion:

$$r(i)=p(i)/\sqrt{\underset{j=1}{\overset{n}{}}q(i,j)/k_j}$$

achieves a $`\sqrt{Mn}`$-approximation where $`M`$ is the maximum of the $`k_j`$’s. The following example shows that this upper bound is exact. Therefore the normalized criterion is not optimal.

Consider two commodities, and assume there are $`k`$ units of the first one ($`k_1=k`$) and one unit of the second one ($`k_2=1`$). There are two bids. The first one is $`k,1,\sqrt{2}`$ and the second one is $`1,0,1/\sqrt{k}`$. Both bids have the same normalized ranking criterion ($`1`$). Assume the greedy method places the second bid first. It obtains $`1/\sqrt{k}`$ instead of the optimal $`\sqrt{2}`$: an $`\sqrt{2k}`$-approximation, not as good as the $`\sqrt{k+1}`$-approximation provided by the unnormalized criterion. In Section 2, we indicated that we were willing to consider dynamic, and not only static, ordering criteria for the bids. Our conclusion is that the optimal criterion is a static one, quite a surprising conclusion.

## 6 Practical considerations for
choosing the most promising bid

As noted in Section 3 the choice of a method for bounding the possible value of an auction from above is quite unproblematic in practice: one may use a wealth of methods and take the smallest upper-bound obtained. In practice, one will, on the basis of the record of past runs, easily find out which of the methods are useless and stop using them. The choice of the most promising bid studied in Section 4 and 5 is much more of a problem. The criterion described in (6) is shown to be theoretically optimal in Corollary 5.7, but is it the best in practice? It is the criterion that guarantees the best approximation ratio in the worst case, does it provide the best solution in practice? The truth of the matter is that only experience with real MUCAs can tell and, at this moment, no such data exists. We can only point out at two considerations. First, the examples of Section 5 present quite tellingly why the criterion defined in (6) strikes a balance between a criterion favoring large bids and a global view such as the one defined in (1) or one that favors small bids and fine tuning such as defined in (2) or in (4). The proof of Theorem 5.5 also shows why the unnormalized criterion of (6) should be preferred to the normalized criterion of (7). Secondly, we have confidence in the applicability of theoretical results: techniques that can be proved to be optimal in theory tend to work well.

In , the authors use a complex method for choosing the most promising bid: their choice depends on the other bids and also on the results of the bounding-from-above procedure. Since the ordering of the commodities does not depend on the price offered by the bids, but may determine the solution that will be considered first, it seems that this first candidate solution may be arbitrarily worse than the optimal solution. The basic criterion used inside bins is similar to that of (2) and therefore not optimal in theory.

## 7 Experimental results

Experimental results are crucial in the assessment of the ideas developed above. Three basic questions should be answered.

1. Does the criterion for choosing the most promising bid that has been shown to be optimal in Corollary 5.7 perform well in practice, i.e., does a search algorithm that uses this criterion find rapidly the optimal solution?
2. Do the different methods for bounding from above the value of the optimal solution lead to the pruning of many large subtrees? Which of those methods are most useful?
3. Are those bounding methods fast enough to be usable in practice or does their use imply that the algorithm spends an unbearable amount of time in computing upper bounds? A trade-off between the amount of effort spent in pruning and in examining new nodes must be struck.

The best would obviously be to examine those questions on data obtained from real-life combinatorial auctions. Such data is very difficult to find and we could not put our hands on such data. The next best thing that can be done is to use auctions artificially generated. In , the authors define a probability distribution over combinatorial auctions and test the average behavior of their algorithm on this distribution. We chose to use the same distribution, with the same values for the parameters.

Let us address the second question first. The answer is emphatically positive. The methods proposed above provide upper bounds that allow for an extremely thorough pruning of the search tree. Linear Programming provides a very tight upper bound that leads to a very short search path over the tree: only a very small fraction of the nodes have to be expanded. For example, considering $`40`$ bids, we found that only $`1.6\times 10^9`$ of the nodes were visited.

The projections bounds are not as good, and provide, for the distribution we used, bounds that are not better than the bound provided by average price considerations. This is probably due to the specific distribution chosen, in which it is rarely the case that a single good is dominant, such as, e.g., in the case all bids request all the units of a certain specific good. One of the characteristics of the distribution suggested in  is that bids tend to request only a small number of units per good. This kind of distribution leads to an auction with no dominant good for which the projection bounds are quite loose. R. Holte  found that, on another distribution, the projection bound is very good. Nevertheless, projection bounds allow us to visit only $`1.6\times 10^8`$ of the nodes.

The average price upper bound is not as good as the Linear Programming one, but is, on average, as good as the projection bound. It allows for a very thorough pruning of the search tree. Considering $`40`$ bids, we found that only $`1.6\times 10^8`$ of the nodes had to be visited. This number is the same as the one for the projection bound and ten times larger than the one for Linear Programming.

Let us now address the third question. We found Linear Programming to be extremely costly (in time) to use, so costly as to render its use infeasible for large combinatorial auctions. Since we have only just begun experimenting, we hope that we shall learn in the future how to use Linear Programming effectively. The average price upper bound is, on the contrary, computed very fast. The projection bounds are not computed as fast. Since we explained above that the projection bounds were, on our distribution, not better, the results to be presented below have all been obtained by using the average price upper bound exclusively.

Let us discuss the first question now. The best test of the quality of our ordering heuristic is probably to examine how fast the optimal solution is obtained. We found that, using the ordering criterion described in Equation 6, the optimal solution is found extremely rapidly and the algorithm spends an overwhelming part of its time in showing that this solution is indeed optimal. In Figure 1, we plot the time spent until the optimal solution is found divided by the total time spent in the search for auctions of different sizes. All auctions include $`14`$ goods, the number of bids is found on the $`x`$ axis. For small auctions this number is of the order of $`4\%`$; for larger auctions this number decreases about linearly on a logarithmic scale and for auctions of $`150`$ bids, the optimal solution is found after only $`0.014\%`$ of the total execution time. It seems that this percentage decreases at least exponentially. Those results seem to improve significantly on those of . The Percentage Optimality graph there seems to indicate than more than $`10\%`$ of the time is spent before the optimal solution is found. Those results indicate that the criterion of Equation 6 that we proved theoretically optimal is extremely good in practice.

Figure 2 describes the execution times of our branch and bound algorithm using the average price upper bound and the ordering heuristic of Equation 6: on the $`x`$-axis the number of bids, on the $`y`$-axis the execution time. Four different curves are plotted, corresponding to a different number of goods. Our experimental data was collected on a Pentium III-450 running Linux, using 640K of memory. Figure 2 is comparable to the Number of Bids vs. Time figure in . Our running times are larger, by orders of magnitude, than theirs. For this reason, we were not even capable of solving the smallest auctions they considered. Figure 2 shows very clearly a sub-linear (on a logarithmic scale) growth in execution time, indicating that the growth is sub-exponential. This feature is also found, but less clearly, in ’s graph. We intend to look into the reasons for the huge gap in running times between our algorithm and CAMUS. The huge discrepancy between the amount of memory they use (25 MB) and ours (640K) is certainly part of the explanation.

Figure 3 examines the dependence of the running time on the number of goods. The number of bids is fixed at $`50`$, and the number of goods is described on the $`x`$ axis. CAMUS  exhibits an exponential sensitivity to the number of goods (as opposed to the number of bids). Figure 3 clearly shows a sub-exponential growth.

## 8 Conclusions and further work

We proposed a simple branch-and-bound framework to solve MUCAs. We succeeded in characterizing the theoretically optimal method for sorting bids. Two main directions for research are left open:

* characterize the power of different methods for bounding from above the value of MUCAs
* run more extensive experiments to compare the performance of different heuristics both for bounding and for ordering and to compare our proposal to others such as in .
* consider more efficient ways of using Linear Programming, using the results of previous computations to speed up the search for a solution.

## 9 Acknowledgements

Conversations with Michel Bercovier and Michael Ben-Or and remarks from Amir Ronen are gratefully acknowledged. The first author is partially supported by Grant 15561-1-99 from the Israel Ministry of Science, Culture and Sport and by the Jean and Helene Alfassa fund for research in Artificial Intelligence.