
%%%%%%%%%%%%%%%%%%%%%%% file typeinst.tex %%%%%%%%%%%%%%%%%%%%%%%%%
%
% This is the LaTeX source for the instructions to authors using
% the LaTeX document class 'llncs.cls' for contributions to
% the Lecture Notes in Computer Sciences series.
% http://www.springer.com/lncs       Springer Heidelberg 2006/05/04
%
% It may be used as a template for your own input - copy it
% to a new file with a new name and use it as the basis
% for your article.
%
% NB: the document class 'llncs' has its own and detailed documentation, see
% ftp://ftp.springer.de/data/pubftp/pub/tex/latex/llncs/latex2e/llncsdoc.pdf
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[runningheads,a4paper]{llncs}

\usepackage{amssymb}
\setcounter{tocdepth}{3}
\usepackage{graphicx}

\usepackage{url}

%\newtheorem{algorithm}{Algorithm}

\urldef{\mailsa}\path|ahumu@yahoo.com|

\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}

\newcommand{\comment}[2]{}
\newtheorem{algorithm}{Algorithm}


\begin{document}

\mainmatter  % start of an individual contribution

% first the title is needed
\title{On Multi-Dimensional Envy-Free Mechanisms}


% a short form should be given in case it is too long for the running head
\titlerunning{Lecture Notes in Computer Science: Authors' Instructions}

% the name(s) of the author(s) follow(s) next
%
% NB: Chinese authors should write their first names(s) in front of
% their surnames. This ensures that the names appear correctly in
% the running heads and the author index.
%
\author{Ahuva Mu'alem%
}
%

\authorrunning{}
% (feature abused for this document to repeat the title also on left hand pages)

% the affiliations are given next; don't give your e-mail address
% unless you accept that it will be published
\institute{Social and Information Sciences Laboratory,\\
California Institute of Technology, Pasadena, CA, 91106\\
\mailsa\\
}

%
% NB: a more complex sample for affiliations and the mapping to the
% corresponding authors can be found in the file "llncs.dem"
% (search for the string "\mainmatter" where a contribution starts).
% "llncs.dem" accompanies the document class "llncs.cls".
%

\toctitle{Lecture Notes in Computer Science}
\tocauthor{Authors' Instructions}
\maketitle


\begin{abstract}
We study the problem of {\it fairness design}. 
Specifically, we focus on approximation algorithms for indivisible items  
with supporting envy-free bundle prices.
We present the first polynomial-communication 
envy-free profit-maximizing combinatorial auctions for general bidders. 
In this context, envy-free prices can be interpreted as anonymous non-discriminatory prices.
Additionally, we study the canonical makespan-minimizing scheduling problem of 
 unrelated machines, in an envy-free manner. 
 For the special case of related machines model we show that tight algorithmic bounds can be achieved.  

\keywords{Mechanism Design, Anonymous Prices, Scheduling}
\end{abstract}





%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%

Fair division of goods has been a central problem in economic theory. 
In such scenarios each bidder would like to get a fair share 
from her point of view. At the same time, it might be the case that 
the social designer has a certain global goal in mind, and thus the designer seeks 
a fair partition that is as close as possible to the global goal.
Several concepts of fairness were studied over the years.
Envy-free allocations introduced by Foley~\cite{Foley}.  
An allocation is called {\it envy-free} 
if every bidder  likes his own bundle at least as well as that of anyone else. 


A contemporary motivation to study fair allocations stems from 
the emerging technology of Computational Grids.
Computational grids offer users simple access to tremendous computer resources 
for solving large scale computing problems. A typical grid is 
composed of {\it shared} resources owned by different organizational entities that may varied over time. 
The on-line nature and the different degrees of contributions and consumptions 
 suggest new fundamental fairness issues (e.g.,~\cite{AMS}). 


In this paper we study envy-free allocations 
for indivisible goods with supporting  {\it bundle} prices.
We first study Combinatorial Auctions for general bidders
with the goal of profit maximization. 
In this scenario, a collection of indivisible goods needs to be allocated concurrently, 
and bidders 
have preferences about various combinations of items, 
and not just on single items or single subsets of goods.
In this context, envy-free prices can be interpreted as anonymous non-discriminatory prices.
%Recent results for envy-free profit-maximizing auctions 
%for several interesting cases were studied in~\cite{Jason-envy,SC} 
%** add here more papers if necessary 


The second common scenario studied in this paper is a minimization problem.  
Suppose a new project with several tasks is just arrived to a company. 
The challenge is to find a fair allocation of the tasks    
among the employees such that the last task of the project 
finishes as soon as possible. 
A mechanism  is envy-free in this setting, if no employee prefers
the set of tasks and the payment assigned to some other employee.

\noindent {\bf Overview and results.}
In Section 2, we briefly state a known characterization 
of envy-free mechanisms for multi-dimensional domains 
in terms of local-efficient bundle-assignments~\cite{ef-simple-procedure}. 
Informally, an envy-free allocation must 
be locally optimum with respect to the social welfare, so that 
the overall social welfare cannot be improved by exchanging the allocated bundles among the agents.


In Section 3, we study envy-free profit-maximization Combinatorial Auctions with general bidders. 
For a very restricted special case
of the unit-demand setting,
Guruswami et al.~\cite{Jason-envy} showed that 
finding optimal envy-free prices is APX-hard.
We describe an envy-free mechanism that requires polynomial communication
and achieves $\mbox{O}(\min \{n , \sqrt{k} \log k \})$-approximation with respect to profit, 
where $k$ is the number of items and $n$ is the number of bidders. 
We then show that any envy-free profit mechanism with approximation
ratio better than 2, requires exponential communication. 

Section 4  studies envy-free scheduling mechanisms. 
We focus on the scheduling problem extensively studied
by Lenstra, Shmoys, and Tardos~\cite{LST87}. 
This NP-hard optimization problem was formulated 
as a mechanism design problem by Nisan and 
Ronen in their seminal paper on Algorithmic Mechanism Design~\cite{NR}: 
There are $k$ tasks that are to be scheduled on $m$ non-identical machines  
("unrelated machines"). 
The total cost of a subset of tasks on machine 
$i$ is the additive sum of the costs of the individual tasks on that machine.
The global goal is minimizing the makespan of the chosen schedule.
 I.e., assigning the tasks to the machines in a way that minimizes 
 the finishing time of the last task. 
Nisan and Ronen considered this global goal in the context of truthfulness 
(assuming agents are selfish
and thus should be incentivized to report their true costs).

We consider minimizing the makespan in the context of envy-free design.
Specifically, using the characterization, 
we derive general bounds on the approximability 
of deterministic envy-free mechanisms that  
seek to minimize the makespan on unrelated 
machines. We exhibit a lower bound of {\bf $2-\frac{1}{m}$} 
and an upper bound of {\bf $\frac{m+1}{2}$}
for the best approximation ratio achievable by any envy-free mechanism. 
For $m=2$ the result is tight.
However, our upper bound is not known to 
be computationally efficient for any $m \ge 2$. 
This leaves several interesting open problems. 
Similar upper bound and lower bound 
were achieved independently in a recent work by Hartline et al.~\cite{Jason-ef-sched}.
We also show that any envy-free mechanism for minimizing 
the makespan  with supporting {\it item prices} 
cannot achieve approximation ratio better than $m$. 

In Section 5, we consider the NP-hard problem of minimizing 
the makespan of related parallel machines~\cite{ptas-HS}.
We show that the envy-freeness constraint does not impose any further computational burden.
Specifically, we show that there exists a poly-time computable deterministic 
 envy-free mechanism that achieves the approximation ratio of $1+\epsilon$ with respect to the optimal makespan.
 We also show that in this case, resale of tasks among agents can be prevented in quasi-poly-time  
 (without using verifications).




\noindent {\bf Related Work}
Envy-free profit-maximization approximations for combinatorial auctions were first studied by 
 Guruswami et al.~\cite{Jason-envy}.
They showed $\mbox{O}(\log n)$-approximation for  unit demand bidders,
and $\mbox{O}(\log n + \log k)$-approximation  for {\it single-minded bidders} with unlimited supply, 
where $n$ is the number of bidders and $k$ is the number of items.  
In the unlimited supply setting 
the number of copies of 
each item is as large as the number of bidders. 
The latter result was extended to an
$\mbox{O}(\log n + \log k)$-approximation for general bidders with  unlimited-supply, by Balcan, Blum and Mansour~\cite{balcan}. 

Recently, Cheung and Swamy~\cite{swamy-envy} 
obtained $\mbox{O}(\sqrt k \log u_{\max})$-approximation 
for single-minded bidders with limited-supply,  
where $u_{\max}$ is the maximum number of item supply, by using a LP-based technique.
Achieving an approximation ratio better then $\sqrt k$ is NP-hard, even if $u_{\max}=1$~\cite{envy-free-np-hard}.  
The paper~\cite{Lipton} studies {\it envy-free allocations without money} from a computational point of view.  
In this setting envy-free allocations might not exist, and thus they
consider approximations for the minimum envyness. 
None of these papers studies  
the deterministic envy-free profit maximization pricing of combinatorial auctions for  general bidders when supply is 
limited (see~\cite{swamy-envy} for a recent detailed overview and references therein).   


The fundamental purely algorithmic scheduling problem 
of {\it minimizing the makespan of unrelated machines} 
is studied in~\cite{LST87}. This paper presents
a non-trivial 2-approximation poly-time algorithm. 
They also showed that the problem cannot be approximated in
poly-time within a factor less than $\frac{3}{2}$.

A seminal paper by Nisan and Ronen~\cite{NR}
defines the notion of {\it algorithmic mechanism design}~\cite{AGT-book}.
In this paper each machine is treated as a strategic agent. 
The paper proves that 
not only is it impossible to minimize the makespan in a {\it truthful} manner, 
but that any approximation ratio better 
than {\bf $2$} cannot be achieved by a truthful deterministic 
mechanism. They also showed that there is 
computationally efficient truthful mechanism 
that achieves an approximation ratio of {\bf $m$}. 
Their result is tight for $m=2$. 
The lower bound was recently improved (from 2 to 2.61~\cite{Elias261}).

Hochbaum and Shmoys describe a PTAS for 
{\it minimizing the makespan of related parallel 
machines}~\cite{ptas-HS}.\footnote{A PTAS is 
an $(1+\epsilon)$-approximation
algorithm that runs in poly-time, assuming $\epsilon$ is a fixed constant.}
In this NP-hard problem, the type of each machine can be described 
by a single number (single-parameter type). 
This problem was first studied from algorithmic mechanism design perspective in~\cite{AT}. 
Archer and Tardos designed  a 3-approximation mechanism based
on a randomized rounding of the optimal fractional solution~\cite{AT}.
Recently, Dhangwatnotai et al.~\cite{rfpas} presented a truthful {\it randomized} 
 $1+\epsilon$-approximation mechanism.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Characterizing Envy-Free Mechanisms}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

This section characterizes envy-free mechanisms.
The characterization is stated in terms of 
the {\it local efficiency} of the social choice function 
and applies to every domain of valuations.



\noindent {\bf The Setting}
We consider a finite set $K$ of  
$k$ indivisible items and a set $N$ of $n$ 
agents.\footnote{For the characterization theorem 
we might relax this requirement and assume that $K$ is either finite or  infinite set of items.}
We assume that agents value combinations of items.
Formally, each agent  $i \in N$ has a valuation function 
$v_i()$ that describes his valuation for each subset
$S$ of items, i.e. $v_i(S)$ is the maximum finite amount 
of money $i$ is willing to pay for $S$. 
An allocation $a=(a_1, ..., a_n)$ is a partition of items among the agents.
Formally, $a_i$ denotes the subset of items allocated to agent $i$,
$a_1 \cup a_2 \cup \cdots \cup a_n \subseteq K$ (observe that not all items need to be allocated),
and $a_i \cap a_j = \emptyset$, whenever $i \neq j$.
The set of all possible allowed allocations is denoted by $A$.
Every valuation $v_i \in V_i$ satisfies the following three conditions:
{\it No externalities} meaning that the valuation of agent $i$
 depends only on his allocated bundle. 
{\it Free disposal} meaning that the valuation is 
nondecreasing with the set of allocated items 
(for every $S$ and $T$, $S \subseteq T$ implies 
$v_i(S) \le v_i(T)$). 
{\it Normalization} meaning that the value of the empty bundle is always zero.
$V_i$ denotes the domain of all possible valuations of agent  $i$. 

Agents  have {\it quasi-linear utilities}, and so $v_i(a_i) - y$
is the overall utility agent $i$ can obtain from the subset of goods $a_i$ and paying the price $y$. 

A {\it social choice function} $f : V \rightarrow A$ maps 
an $n$-tuple of valuations 
$v = (v_1 , v_2 , \ldots, v_n) \in V_1 \times V_2 \times \cdots \times  V_n = V$ 
to an outcome $a \in  A$. In this setting, a social choice function is simply an allocation rule. 

A mechanism defines an allocation and a set of prices 
for every possible valuation of the agents.
Formally, a {\it mechanism} is a tuple $M = (f,\; p)$, 
where $f$ is a social choice function and the pricing function $p_i : V_i \rightarrow R$ 
assigns a payment to each agent $i \in N$.
Intuitively, the social choice function $f$ 
represents the global goal of the mechanism designer, 
and the payment $p$ determines the fairness of $f$.  


\begin{definition}[Envy-Free Mechanism]\label{def:EF-mechanism}
Let $M = (f,\; p)$ be a mechanism. 
Let $i, j\in N$ and let $v = (v_1 , ..., v_n)$ be an $n$-tuple 
of  valuations. Denote by $a \in A$ the allocation $f$ outputs for $v$.
The mechanism $M$ is said to be envy-free if for every agents  $i, j$ 
and valuation $v$  it  holds that:  
\[
v_i(a_i)-p_i(v) \; \geq \; v_i(a_{\bf j})-p_{\bf j}(v),
\]
where $p$ is non-negative individually-rational payment. 


We say that a social choice function $f:V \rightarrow A$ is
{\it envy-free achievable}  
if there exists a non-negative individually-rational payment $p$ such that 
the mechanism $M=(f,\;p)$ is envy-free.\footnote{We 
consider direct revelation mechanisms.
However, the agents  in our
setting are non-strategic, they always report their true valuations. 
Observe also that we use the notion of 
"achievability" rather than  the notion of "implementability". }  
\end{definition}

\begin{example}
Suppose we have two agents, and one item. 
Consider the following allocation rule: the agent with the highest value wins the item.
Additionally, the winner pays the average of both values and the other agent pays zero. 

This mechanism is envy-free: 
Suppose without loss of generality the first agent won the item. Then $v_1 \ge v_2$.
From the fact that $v_1 - \frac{v_1+v_2}{2} \ge 0 \ge v_2 - \frac{v_1+v_2}{2}$, 
we immediately get that that agent 1 does not envy agent 2, and vice versa.

 
\end{example}

\begin{definition}
%[$\Psi (v, \  a)$]
For arbitrary allocation $a \in A$ and valuation $v \in V$, 
let 
\[
\Psi (v, \  a) = \Sigma_{i=1}^n \ v_i(a)
\]
 denotes the social-welfare of the allocation $a$ with respect to $v$. 
\end{definition}

\subsection{Locally-Efficient Bundle Assignments and Allocations} 
In order to be able to state  the characterization theorem 
we proceed with some definitions. 
Let $a \in A$ be an arbitrary feasible allocation. 
We shall consider the following associated allocations based on $a$:


\begin{definition}[Bundle Allocation based on $a$ and $\beta$]
 Let $\beta: N \rightarrow N$ be an arbitrary function.
Let $a=(a_1, ..., a_n) \in A$ be an arbitrary feasible allocation.
We say that the allocation $a^{\beta}$ 
is the {\it bundle-allocation} based on $a$ and $\beta$,
if agent   $i$ in $a^{\beta}$ is allocated all bundles $a_k$ 
with $\beta(k)=i$.
\end{definition}

We also consider a special interesting case, 
in which each agent  gets exactly one bundle of $a \in A$, 
based on a given permutation:  

\begin{definition}[Bundle Assignment based on $a$ and $\pi$]
Let $\pi: N \rightarrow N$ be an arbitrary permutation.
Let $a=(a_1, ..., a_n) \in A$ be an arbitrary allocation. 
We say that the allocation $a^{\pi}$ 
is the {\it bundle-assignment} based on $a$ and $\pi$,
if the bundle allocated to agent $i$ 
in $a^{\pi}$ is exactly the  bundle $a_k$,
where $\pi(k)=i$.
\end{definition}



%(an agent  might get an empty bundle in $a^{\beta}$ even 
%if $a$ allocated at least one item to every agent  ).



\begin{definition}[Locally-Efficient Bundle Assignment]
\label{def:local-efficient-bundle-assign} 
An allocation $a=(a_1, ..., a_n)$
is said to be locally-efficient bundle assignment 
with respect to $v=(v_1, ..., v_n)$, 
if for every permutation $\pi: N \rightarrow N$ it holds that:
\[\Psi(v, \  a) \ge \Psi(v, \ a^{\pi}).\]  
\end{definition}

\begin{example}
The allocation rule $f^*(v) \in \mbox{argmax}_{a\in A} \ \Psi(v, \ a)$
  which maximizes the social-welfare,
and $f^\emptyset$ that always allocates an empty bundle for every agent,
clearly produce locally-efficient bundle assignments. 

Consider the following 
2 agents  and 2 identical items setting with: 
$v_1(1) = v_1(2) = 1.5, \ v_2(1) = v_2(2) = 2$. 
The allocation $a$ in which agent   2 gets both items  
and agent   1 gets the empty bundle is a locally-efficient bundle assignment.
Similarly, the allocation $a'$ in which every agent gets exactly one item
is also a locally-efficient bundle assignment.  
Additionally, since bundles cannot be reconfigured, $a' \neq a^{\beta}$ for every $\beta$.
However, there is $\beta'$ such that $a = a'^{\beta'}$.
\end{example}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Characterizing Envy-Freeness}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We now state a characterization of 
envy-free bundle pricing mechanisms in terms of   
locally-efficient bundle assignments. 
A similar proof technique in different contexts were used in~\cite{quinzii,rochet,debasis}.


%Interestingly, it is rather simple to show that 
%envy-free achievability implies local efficiency.  
%In contrast, it is not straightforward to see how Rochet's 
%cycle-monotonicity condition that 
%characterizes dominant-strategy implementability implies 
%global weighted efficiency when players have quasi-linear utilities~\cite{LMN2}.


%The proof relies on a convex analysis proof 
%technique~\cite{rochet,dov,MV} (see also~\cite{federico}). 
%However, despite this similarity, 
%the notion of envy-free achievability is different from 
%the notion dominant-strategy implementability 
%(see subsection \ref{subsection-ef-vs-ic}).
%Interestingly, it is rather simple to show that 
%envy-free achievability implies local efficiency.  
%In contrast, it is not straightforward to see how Rochet's 
%cycle-monotonicity condition that 
%characterizes dominant-strategy implementability implies global efficiency~\cite{LMN2}.


\begin{theorem}~\cite{ef-simple-procedure}\label{characterization-theorem}
A deterministic social choice function $f: V \rightarrow A$ is envy-free 
achievable 
if and only if the allocation $f(v)$ is 
a locally-efficient bundle assignment w.r.t. $v$, 
for every $v \in V$.
\end{theorem}

In this paper we shall extensively use both the necessary and the sufficient condition of this theorem. 
Intuitively, instead of considering the interplay between 
the the allocation rule and the  payment rule, 
the above characterization allows us to focus on 
the allocation rule alone in order to prove or disprove the envy-free achievability.  
Additionally, based on the characterization, the envy-free achievability can be decided in poly-time, more formally: 




\noindent {\bf Cost Minimization Problems}
The characterization theorem is stated for the case  
each agent wishes to maximize his value.
The characterization apply also for cost minimization problems, 
for which the agents would like to minimize their costs.
Technically, the inequality is reversed to the other direction 
in the definition \ref{def:local-efficient-bundle-assign} when 
considering cost minimization settings. 
It is easy to see that the canonical payment in this context  
has the property  that the true cost 
of each agent is covered by the mechanism. 

  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Profit-Maximizing  Combinatorial Auctions} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section we consider the problem of maximizing the seller's profit 
in a combinatorial auction with general agents. 
We shall show an envy-free mechanism that requires polynomial communication
and achieves $\mbox{O}(\min \{n , \sqrt{k} \log k \})$-approximation with respect to the maximal envy-free profit. 
This result uses the characterization theorem and 
is built on the work of Blumrosen and Nisan~\cite{BN} for general bidders and Guruswami et al.~\cite{Jason-envy} for unit demand bidders. 
We then show that a envy-free mechanism with approximation
 ratio better than 2 
w.r.t.  the optimal profit requires exponential communication.


\begin{theorem}
There exists an envy-free profit maximizing mechanism for Combinatorial Auctions with general agents 
that achieves an $\mbox{O}(\min \{n , \sqrt{k} \log k \})$-approximation
 and requires polynomial communication.
\end{theorem}

If $n< \sqrt{k}$ then we can use the simple algorithm that always 
allocate the grand bundle to the agent  with the highest value and setting the price to be this value. This gives 
an $n$-approximation to the profit.
We now need to describe the allocation algorithm for the general case. 
Our first building block is the BN-algorithm for Combinatorial Auctions with general agents 
by Blumrosen and Nisan~\cite{BN}. 
The BN-algorithm uses polynomial number of demand queries (and thus polynomial communication) 
to achieve $4\sqrt{k}$-approximation ratio with respect to  
the overall social welfare. 
The BN-algorithm constructs two allocations and outputs the one with the highest social welfare. 
The first allocation is simply the allocation that gives all the goods to the agent with the highest value.
The second allocation is based on a "greedy" procedure that in step $i$ 
allocates a subset of the remaining unallocated goods $S$ to an unallocated agent $j$ 
satisfying 
\[
S_i \in \mbox{argmax}_{\mbox{ $S, j$ is unallocated subset of goods and agent, respectively} } \frac{v_j(S)}{|S|}.
\]

The next algorithmic step is to convert the output $a$ of the BN-algorithm into a locally-efficient 
bundle assignment $a^{\pi^*}$, where $\pi^*$ is the permutation such that 
$\Psi(v, \  a^{\pi^*}) \ge \Psi(v, \ a^{\pi})$ for every $\pi$.
Clearly, this cannot decrease the achieved social welfare as $\Psi(v, \  a^{\pi^*}) \ge \Psi(v, \ a)$,
 and can be done in polynomial communication. 
By the characterization theorem \ref{characterization-theorem}, $a^{\pi^*}$ is envy-free achievable. 


We now need to describe the pricing method. 
If the the chosen allocation $a$ in the previous step gives all the goods to one agent 
% (w.l.o.g, $a=a^{\pi^*}$)  
then this agent will pay his bid for the grand bundle,
and all other agents pay zero. Clearly this is an envy-free pricing and the achieved 
profit $P$ in this case is exactly the welfare achieved by the 
BN-algorithm. 
Otherwise, $a$ is based on the greedy method. 
Our second building block is the envy-free pricing method 
designed for unit demand agents by Guruswami et al.~\cite{Jason-envy}, 
based on a careful  poly-time selection of {\it reserved} prices.   
The achieved  envy-free pricing is within factor of 
$2\ln n$ for the maximum profit. 
In particular, the profit $P$ in this case is within a factor of 
$2\ln n$ of the social welfare $\Psi(v, a^{\pi^*})$.
It is immediate to see that the factor in their proof is  $2\ln (\min\{n, k\})$, 
since the number of possible non-trivially allocated agents is at most $\min\{n, k\}$.  
Additionally, it is not hard to see that we can use this pricing method for our setting as well 
(since as in the unit demand setting,
an agent in our setting can only envy an entire bundle 
that is allocated to another agent defined by $a^{\pi^*}$, 
and not any other arbitrary bundle).


 
\proof 
Clearly, the  maximum envy-free profit $P^*$ is at most the  maximum social welfare $W^*$, and thus: 
\[  
\frac{P^*}{4\sqrt{k}} \le \frac{W^*}{4\sqrt{k}} 
\le \Psi(v, a) \le \Psi(v, a^{\pi^*}) 
\le 2 P \ln (\min\{n, k\}). 
\]

 All together we get the desired bound.  
\qed



The following proposition shows that any envy-free mechanism needs an exponential communication 
in the worst-case to produce approximation ratio better than 2 for the profit. 
This result uses the construct of Nisan and Segal~\cite{NS} for efficient allocations. 



\begin{proposition}
Any envy-free profit maximizing mechanism for 
Combinatorial Auctions that achieves an approximation
ratio better than $2$ requires exponential communication.
\end{proposition}



\subsection{Item Prices}

Item prices is a special case of bundle prices. 
If item prices are defined, then the price of a bundle is the total 
prices of the items in the bundle. 
Thus an agent can envy a bundle or any sub-bundle allocated to some other agent.
Envy-free mechanisms with item prices for combinatorial-auction can extract only a small profit 
regardless of any computational considerations (equivalently, any auction with anonymous item-price extracts a small profit in the worst-case).

\begin{proposition}
Any deterministic envy-free mechanism for profit maximization 
with supporting item prices 
cannot achieve approximation ratio better than $k$. 
\end{proposition}

\comment{
\proof
Consider 2 agents  and $k$ items.
Agent 1 is a single minded bidder with  
$v_1(S) = k - \epsilon$ if $|S| = k$, otherwise $v_1(S) =0$ for any $|S|<k$. 
Agent 2 is a unit demand bidder with $v_2(S) = 1$ if $|S| \ge 1$, otherwise $v_2(S) = 0$.

If we allocate the $k$ items to the first agent, this is a locally-efficient allocation, 
and we can collect the profit of $k-\epsilon$. 
However, if we require item prices the maximum profit is at most 1.
Clearly the minimum price for an item cannot be $< 1$, since the second agent will demand one item.
But then the bundle price for the $k$ items is at least $k$, and so agent 1 will prefer the empty bundle. 
\qed 
  
}



 
  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Envy-Free Approximability of Unrelated Machines} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The Unrelated Machines Model was studied in the seminal paper of 
Algorithmic Mechanism Design~\cite{LST87,NR}.
For this model we prove that not only it is  impossible 
to minimize the makespan in an envy-free manner, but
that any approximation ratio better than $2-\frac{1}{m}$ 
cannot be achieved by any envy-free \emph{deterministic} mechanism.
We then present an envy-free  mechanism that 
achieves  $\frac{m+1}{2}$-approximation. 
Our mechanism make use on the optimal 
allocation w.r.t. makespan, and thus is not computationally efficient. 
For $m=2$ our result is tight. 
Similar upper and lower bounds were achieved recently and independently by Hartline et al.~\cite{Jason-ef-sched}. 

\noindent {\bf The Setting}
The unrelated machine scheduling setting {\it $(R||C_{\max})$} 
is a special case of the combinatorial 
auction setting. 
There are $k$ tasks
 that are to be scheduled on $m$ machines.\footnote{We chose $m$ to be the number of machines 
to be consistent with the
formulation of Nisan and Ronen. Recall that we used $n$ previously
to denote the number of agents, 
whereas here the agents are the machines.} 
Every machine $i$ is an agent with a nonnegative valuation
function $v_i()$.  Formally, $v_i(\{j\})$ (or simply $v_i(j)$) 
specifies the \emph{cost} of task $j$ on machine $i$. One
can think of the cost of task $j$ on machine $i$ as the time it
takes $i$ to complete $j$.  The total cost of a set of
tasks $S$ on machine $i$ is the {\it additive} sum of the costs of the
individual tasks on that machine. Formally, $v_i(S)=\Sigma_{j\in S} \ v_i(j)$ for every $S$.  
In the unrelated machines setting these costs can be arbitrary 
(every $(k \cdot m)$-tuple of non-negative costs is feasible),
and thus it is a multi-dimensional scheduling problem. 



Let $a \in A$ be an arbitrary allocation of tasks to the machines ("scheduling"). 
The load of machine $i$ is its cost $v_i(a_i) = \Sigma_{j\in a_i} \ v_i(j)$.  
Let $r(a,v)= \max \{v_1(a_1), v_2(a_2), ..., v_m(a_m)\}$, 
be the load of the most loaded machine. 
To simplify notation we shall use the notation $r(a)$ instead of $r(a,v)$,
 when $v$ is clear from the context.  

{\it The global goal is minimizing the
makespan.} I.e., it is a minmax goal: assign the tasks to 
machines so that the last task finishes 
as soon as possible (each task is assigned to exactly one machine).
Formally, fix an arbitrary $v \in V$. 
The allocation $\widehat{a}$ is 
{\it optimal w.r.t.  the makespan} if 
 $r(\widehat{a}) \le r(a)$ for every $a \in A$. 

\comment{ 
Let $f$ be a social choice function. 
If $r(f(v)) \le c \cdot r(\widehat{a})$ 
for every $v \in V$ then we say that $f$ 
is a {\it $c$-approximation algorithm}
($c \ge 1$ might be a constant or any function of $v$). 
A mechanism 
$M(f,p)$ is called a {\it $c$-approximation mechanism} 
if $f$ is a $c$-approximation.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Lower Bound}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{theorem}
Any envy-free mechanism cannot achieve an approximation
ratio better than $2-\frac{1}{m}$ with respect to the makespan.
\end{theorem}

\comment{
\proof 
Suppose not. Let $M(f,p)$ be a deterministic envy-free mechanism that achieves
an approximation factor $2-\frac{1}{m} - \epsilon$. 
Let $\epsilon'< \epsilon$.  
We shall consider two cases. 
For the case  $m=2$, consider the following valuation instance with two tasks: 
$v_1(1) =1, \ v_1(2) =0.5, \ v_2(1) = 1.5 - \epsilon',\  v_2(2) =1$, 
(see the matrix below): 

\[
\left(
\begin{array}{cc}
 1 & 0.5  \\
 1.5 -\epsilon' & 1 \\
\end{array}
\right)
\]


The first line represents the costs of running the 
first task on the first and the second machine, respectively.
Similarly, the second line represents the possible costs 
of the second task on each of the machines. 
 
Clearly, there are exactly 4 possible allocations. 
The optimal allocation w.r.t. the makespan assigns 
the first task to the first machine, and the second task to the second machine. 
All together the makespan is $1$. 
However, this allocation is not a locally-efficient bundle assignment
and thus by theorem \ref{characterization-theorem} is not envy-free achievable,
as one can easily verify that:  
$2 = v_1(1) + v_2(2)  > v_1(2) + v_2(1) = 2 - \epsilon'$ 
(recall that this is a cost minimization setting). 
Any other allocation has a makespan 
$ \ge 1.5 -\epsilon' > 1.5 -\epsilon$, a contradiction.

For $m \ge 3$, consider the following matrix 
(for the ease of exposition we assume  $m=4$): 
 \[
\left(
\begin{array}{ccccc}
 1 & {\it 1-\frac{1}{m}} & \infty & \infty\\\\
 \infty & 1 & {\it 1-\frac{1}{m}}  & \infty \\\\
 \infty & \infty & 1 & {\it 1-\frac{1}{m}}   \\\\
 {\it 2-\frac{1}{m} -\epsilon'} & \infty & \infty & 1  \\\\
\end{array}
\right)
\]

First, consider the allocation $b$ in which task $i$ is assigned to machine $i$.
The makespan of this allocation is 1. 
Thus the optimal makespan must be $ \le 1$.
However, it cannot be strictly smaller than 1,
since the cost of the last task on each machine is at least 1.
We get that $b$ is the optimal allocation w.r.t. the makespan. 
However, $b$ is not a locally-optimal bundle assignment
(compare to the assignment marked with {\it italics} in the matrix above)  
as $m > (m-1) (1 - \frac{1}{m}) + 2 -\frac{1}{m} - \epsilon' = m - \epsilon'$.
It is easy to verify that 
every other allocation has approximation ratio strictly larger than  
$2 -\frac{1}{m} -\epsilon$ w.r.t. to the makespan, a contradiction. 
\qed
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Upper Bound}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In general the optimal allocation w.r.t.  the makespan is not locally efficient,
and in particular is not envy-free achievable. 
We will thus need to modify this optimal allocation in a careful way. 
We need the following: 

\begin{definition}[The Function $\beta^*$]
Let $a=(a_1, ..., a_m) \in A$ be an arbitrary allocation. 
Define the function $\beta^*: [m] \rightarrow [m]$ as follows. 
 
Let $\beta^*(j) \in \mbox{argmin}_{\ i=1,...,m}\; v_i(a_j)$, $j \in [m]$. 
That is, $\beta^*(j)$
is the machine with the minimal cost for the bundle $a_j$ (breaking ties arbitrarily).
\end{definition}

Intuitively, $a^{\beta^*}$ is defined by independent "bundle-auctions":
in each step $j=1..m$ we allocate the bundle $a_j$ of some given allocation $a$
to the lowest cost machine for this bundle
(independently of the history of former steps).


{\it Fact:}
If the valuation of each machine is additive, then $b=a^{\beta^*}$ 
is a locally-efficient bundle assignment. That is, 
for every permutation $\pi$ it holds that:
\[\Psi(v, \  b) \le \Psi(v, \ b^{\pi}).\]  


\begin{definition}[The Permutation $\pi^*$]
Let $a=(a_1, ..., a_m) \in A$ be an arbitrary allocation.
Define $\pi^*$ to be a permutation such that 
$a^{\pi^*}$ is locally-efficient bundle assignment.
If there is more than one permutation, then arbitrarily choose one. 
\end{definition}

 
Clearly, $a^{\pi^*} \neq a^{\beta^*}$ in general.    
We now describe our algorithm.  

\begin{algorithm}[Bundle-Local-Search]
Input: $v = v_1, v_2, ..., v_m$. 

Let $ \ \widehat{a}$ be the optimal allocation with respect to the makespan of $v$.
\begin{itemize}
\item 
If the makespan of $\ \widehat{a}^{\; \pi^*}$ 
is at most $\frac{m+1}{2}$ times the 
makespan of $ \ \widehat{a}$, then output $ \ \widehat{a}^{\; \pi^*}$. 
\item 
Otherwise, output  $ \ \widehat{a}^{\; \beta^*}$.
\end{itemize}
\end{algorithm}

Informally, we permute the bundles dictated by $ \ \widehat{a}$ to achieve the 
locally lowest cost  
social welfare. If the resulted makespan has not increased by much, then we output this allocation.
Otherwise, we re-assign each bundle $\widehat{a_i}$ 
to the machine with the minimal cost for this bundle.
 
\begin{theorem}\label{thm-upper-bound-unrelated}
Algorithm bundle-local-search  guarantees an approximation
ratio of $\frac{m+1}{2}$ with respect to the makespan.
Moreover, algorithm bundle-local-search is envy-free achievable.
All together we get that there exists an envy-free 
$\frac{m+1}{2}$-approximation mechanism
for minimizing the makespan on unrelated machines. 
\end{theorem}

\comment{
\proof
Algorithm bundle-local-search always outputs 
a locally-efficient bundle assignment and thus 
by theorem \ref{characterization-theorem}
is envy-free achievable.
%Specifically for every $\pi$, 
%$\Psi(v, \  \widehat{a}^{\; \pi^*}) \le  \Psi(v, \ (\widehat{a}^{\; \pi^*})^{\pi})$, and
%$\Psi(v, \  \widehat{a}^{\; \beta^*}) \le \Psi(v, \ (\widehat{a}^{\; \beta^*})^{\pi})$.

If the algorithm outputs the allocation $\ \widehat{a}^{\; \pi^*}$, 
then clearly $ \ r(\widehat{a}^{\; \pi^*}) \ \le \ \frac{m+1}{2} \cdot  r(\widehat{a})$. 
Otherwise, there exists a high loaded machine 
(without loss of generality machine 1) 
such that: 
\[
v_1(\widehat{a}^{\; \pi^*}) \  = \  r(\widehat{a}^{\; \pi^*}) \  > \ \frac{m+1}{2} \cdot r(\widehat{a}).
\]

That is, machine 1 determines the makespan, and based on the fact that 
the output of algorithm is  $ \ \widehat{a}^{\; \beta^*}$ we get that the
makespan of  $ \ \widehat{a}^{\; \pi^*}$ is quite large. 
Additionally, 
\[ 
\Psi(v, \  \widehat{a}^{\; \beta^*}) \ \le \
\Psi(v, \  \widehat{a}^{\; \pi^*}) \ \le \  
\Psi(v, \ \widehat{a}) \ \le \ 
m \cdot r(\widehat{a}).
\]

All together: 
\[
\Psi(v, \  \widehat{a}^{\; \beta^*}) \ \le \
m \cdot r(\widehat{a}) - \frac{m+1}{2} \cdot r(\widehat{a}) + r(\widehat{a}) \ = \ \frac{m+1}{2} \cdot r(\widehat{a}), 
\]

where $m \cdot r(\widehat{a}) - \frac{m+1}{2} \cdot r(\widehat{a})$ is an upper bound to the load of the bundles
$v_i(\widehat{a}^{\; \pi^*}), \ i \ge 2$.
Intuitively, to get $\widehat{a}^{\; \beta^*}$ we first auction the bundle of machine 1 
in the allocation $\widehat{a}^{\; \pi^*}$ among the agents, 
and by our construction we know that there exists 
an agent with  cost at most $r(\widehat{a})$ for this bundle.

 
 In the worst case,
all  bundles will be allocated to the same machine.
 Hence we have the following:

\[
r(\widehat{a}^{\; \beta^*}) \ \le \ 
\Psi(v, \  \widehat{a}^{\; \beta^*}) \ \le \
\frac{m+1}{2} \cdot r(\widehat{a}).\;\;\; \qed
\] 

}

%Finally, it will be interesting to understand budgeting issues for this setting. 
%Let $T$ be an arbitrary collections of tasks. 
%Under what conditions an envy-free mechanism will always pay the agents 
%less money if at least one of the tasks in $T$ is removed? 

\comment{
\begin{remark}
Theorem \ref{thm-upper-bound-unrelated} describes 
an envy-free $\frac{m+1}{2}$-approximation mechanism.
It is not a poly-time computable mechanism since 
algorithm bundle-local-search is based on the optimal allocation w.r.t. makespan. 
Observe that this is the only reason.  Suppose that we are given an oracle
access to the optimal allocation w.r.t. makespan for every $v$. 
Then all other steps in algorithm bundle-local-search and in the 
computation of the associates envy-free canonical payments 
(proposition \ref{conc:payment-in-poly-time}) 
can be done in poly-time. 
\end{remark}

}

\subsection{Item Prices}
In this subsection we shall see that for minimizing the makespan,  any envy-free mechanism with item prices 
cannot achieve approximation ratio better than  $m$ w.r.t to the makespan
 (regardless of any computational considerations), and this tight.
Recall that if item prices are defined, the price of a bundle is the total prices of the items in the bundle. 
The following proposition is applicable for both the unrelated machines model and the related parallel machines model 
(see the next section for exact definition).   
 

\begin{proposition}
Any deterministic envy-free mechanism for minimizing 
the makespan with supporting item prices 
cannot achieve approximation ratio better than $m$, and this is tight. 
\end{proposition}

\comment{
\proof 
First the ratio of $m$ can be achieved by Nisan and Ronen's~\cite{NR} mechanism
 (that auctions each task separately using a second price auction for each task). 
 It is easy to show that this results in 
 a locally efficient allocation, and that the item prices ensure envy-free achievability.
  
  To show the inapproximability, consider $m$ tasks and $m$ agents. 
  Agent 1's cost for each task is $1-\epsilon$.
  Agent $i$'s cost for each task is 1, where $i=2..m$.
  Clearly, if the item price  of a task is $< 1-\epsilon$ then no agent would agree to preform the task.
  Now, if the price is $ \ge 1$, then agent 1 will be strictly envious if he hasn't got the task. 
  Otherwise, if the price of a task is $< 1$ and at least $1-\epsilon$,
   then only agent 1 will agree to preform the task.
  All together, for every reasonable item price,  agent 1 must gets all the tasks.  
  This gives a schedule with a makespan $m \cdot (1-\epsilon)$, 
  while the optimal schedule w.r.t. the makespan is to give each agent exactly one task.
  \qed 
  
}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Near-Optimality of Related Parallel Machines}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section we study an interesting 
case in which the envy-freeness constraint do not impose a further 
computational burden. 
Specifically, we consider minimizing the makespan of related parallel 
machines in an envy-free manner. 
We show that there exists a {\it poly-time}
black-box procedure that takes an allocation and 
converts it to an "envy-free" allocation  
without any loss in the approximation ratio,  
and specifies supporting envy-free bundle prices.
We then show that there exists a poly-time
envy-free $(1+\epsilon)$-approximation mechanism 
for every fixed $\epsilon$, using the deterministic PTAS
by Hochbaum and Shmoys~\cite{ptas-HS}.
We shall start by the formal setting.  


\noindent {\bf The Setting}
The related parallel machine scheduling setting {\it $(Q||C_{\max})$} is 
a special case of the unrelated model {\it $(R||C_{\max})$}.
In this model each task $j$ has a load $l_j > 0$.   
Additionally, every machine $i$ represents an agent with type $t_i$.
It takes $t_i \cdot l_j$ time units to perform task $j$ on machine $i$.
More formally,  $v_i(\{j\}) = t_i \cdot l_j$. 
The total cost of a set of
tasks on machine $i$ is the additive sum of the costs of the
individual tasks on that machine. 
In this setting machines are comparable: if machine $i_1$ 
is faster than machine $i_2$ on task $j$, 
then machine $i_1$ is always faster than machine $i_2$. 
For convenience we use the notation $l(S) = \Sigma_{j\in S} \  l_j$,
 to denote the total load of a subset of tasks $S$. 
We also assume without loss of generality that $t_1 \ge t_2 \ge \cdots \ge t_m$.

\subsection{The envy-free mechanism}

\begin{lemma}\label{related-characterization}
$f$ is envy-free achievable if and only if it allocates more load to the fastest machines. 
\end{lemma}

\comment{
\proof 
Suppose $f(v)=a, t_i \ge t_j$ and $l(a_i) \ge l(a_j)$ with at least one strict inequality.
But then switching the loads between machines $i$ and $j$, 
strictly decreases the overall social cost by the amount of $l(a_i)t_i + l(a_j)t_j  - l(a_i)t_j-  l(a_j)t_i >0$,
 contradicting (the cost minimization version of)  theorem \ref{characterization-theorem}.
 For the other direction, clearly if $f$ is not envy-achievable, then it is not locally efficient, and by the fact that 
 the machines are related and thus comparable 
 it must be the case that there are two machines $i, j$ 
 such that $t_i \ge t_j$ and $l(a_i) \ge l(a_j)$ with at least one strict inequality. 
\qed
 
}

\begin{lemma}\label{wlog-sorted-allocation-related-machine}
Let $f$ be a deterministic $c$-approximation algorithm. 
We can assume without loss of generality that 
$f$ always allocates more load to the fastest machines (this will only improve the makespan).
\end{lemma}

\comment{
\proof 
We can reassign the loads in a sorted manner.
Formally, let $f(v)=a$. We will give the fastest machine $m$ 
the subset of tasks $a_i$ with the highest load: $argmax_{i=1, ...,m} \ l(a_i)$, 
and machine $m-1$  the second highest loaded subset of tasks, and so on.
First, this reassignment can be done in poly-time.  
Second, we need to show that the resulted allocation $a'$ (after switching the
assigned loads) is a $c$-approximation.
For the two machine case $m=2$: if $a \neq a'$ then clearly $r(a)=t_1 \cdot l(a_1)$.
However if we exchange the loads between the machines then: 
$r(a') = \max\{t_1 \cdot l(a_2), \; t_2 \cdot l(a_1)\} \le r(a)$.
For $m>2$, we can sort $a$ in poly-time as in the 
bubble-sort algorithm ("2 machines at each step"), 
and in each step the makespan can only improve.
\qed
}

\begin{definition}[Frugal Payment]
Suppose $f(v)=a$, and $a$ allocates higher load to faster machines. 
The frugal payment to each machine is defined recursively as follows: 
$p_1(v) = l(a_1) \cdot t_1$,  
and 
 $p_i(v) =  p_{i-1}(v) + (l(a_i)-l(a_{i-1})) \cdot t_i$, for $i = 2, ..., m$. 
\end{definition}


Intuitively, the average payment for a  unit of load decreases for faster machines in the above payment rule.



\begin{theorem}\label{thm-polytime-convert-related}
Any $c$-approximation deterministic algorithm 
w.r.t. makespan for related parallel machines model 
can be converted in poly-time to a $c$-approximation envy-free mechanism
using the frugal payments.
\end{theorem}

\comment{
\proof
We first show that machine $i$ cannot envy a faster machine $d$ with higher load.
Indeed, $p_i(v) - l_i(a_i) \cdot t_i $ 
is greater than $p_d(v) - l_i(a_d) \cdot t_i$ by the following: 
\[
l_i(a_d)\cdot t_i - l_i(a_i)\cdot t_i \; \ge \; (l(a_{i+1})-l(a_{i})) \cdot t_{i+1} + \cdots +
 (l(a_d)-l(a_{d-1})) \cdot t_{d} \; \ge \; p_d(v) - p_i(v).
\] 

Similarly, machine $i$ cannot envy a slower machine $d'$ with less load. Indeed,
$p_i(v) - l_i(a_i)t_i$ is greater than $p_{d'}(v) - l_i(a_{d'})t_i$, 
by the fact that: 

\[ p_i(v) - p_{d'}(v)\; \ge \; 
(l(a_{d'+1})-l(a_{d'})) \cdot t_{d'+1} + \cdots + (l(a_{i})-l(a_{i-1})) \cdot t_{i} 
\; \ge \; l_i(a_i) \cdot t_i - l_i(a_{d'})\cdot t_i. \;\; \qed
\]

}



Based on the deterministic PTAS
by Hochbaum and Shmoys~\cite{ptas-HS} and theorem \ref{thm-polytime-convert-related}
we can show the following theorem. The theorem also suggests that the resale of items ("tasks") 
among the agents can be prevented without using verification (see next subsection for a proof). 


\begin{theorem}\label{thm-1+epsilon-mechanism-related}
There exists a poly-time computable 
envy-free $(1+\epsilon)$-approximation mechanism 
for minimizing the makespan on related parallel 
machines for every fixed $\epsilon$. 
Moreover, resale among the agents can be prevented (in quasi-poly-time).
\end{theorem}



\subsection{Frugal Payments and Preventing Resales}
In many cases, a presence of a secondary resale market is not very desirable. 
Firstly, the secondary market might have a strong impact on the designer's goal (in our case, the makespan objective). 
Second, the existence of a secondary market indicates that there is a potential profit that was not fully extracted 
by the mechanism.  

In what follows  we shall first briefly address the issue of frugality.
This will be helpful for preventing resales.  
Additionally, we show that our deterministic envy-free mechanism is not truthful 
(and thus it is different from the randomized truthful mechanism in~\cite{rfpas})\footnote{Archer 
and Tardos~\cite{AT} showed that the optimal allocation w.r.t. the makespan 
is truthfully implementable. We thus show here that the frugal payment is  different 
from the truthful payment for the optimal allocation with respect to the makespan.}.
Specifically we show that the frugal payment method might encourage an agent to pretend to be slower. 
Obviously, laziness cannot be easily detected (unlike the case that a machine pretend to be faster).  

\begin{proposition}\label{prop-characterizing-frugality}
The frugal payment provides the cheapest individually-rational envy-free payment.
\end{proposition}

\comment{
\proof
Suppose $f(v)=a$, and $a$ allocates higher load to faster machines.
Clearly the the frugal payment is individually rational. 
Recall that the frugal payment for the slowest machine is $p_1(v) = l(a_1) \cdot t_1$. 
This exactly covers the cost of the first machine, 
and thus it is the cheapest among all individually rational payments.
Now any envy-free payment for the second machine $p_2(v)$ 
cannot be strictly smaller than $p_{1}(v) + (l(a_i)-l(a_{i-1}))\cdot t_2$ for every $p_{1}(v)$, 
otherwise machine  
2 would envy machine 1. 
Using similar argument, we can show that the cheapest envy-free payment 
for machine $i$ is completely determined by the payment of machine $i-1$.
\qed



\proof (of theorem \ref{thm-1+epsilon-mechanism-related}) 
The first part of the theorem is an immediate consequence of~\cite{ptas-HS} and the poly-time 
conversion theorem \ref{thm-polytime-convert-related}. 

Suppose now that the allocation $a$ is envy-free achievable 
(that is, an allocation with higher loads to faster machines). 
Using a frugal payment rule, the only 
resale can be made if a slow machine transfers an assigned task to a faster machine. 
Agent $i$ utility without reselling is 
$p_{i-1}(v) + (l(a_i)-l(a_{i-1})) \cdot t_i - l(a_i) \cdot t_i = p_{i-1}(v) - l(a_{i-1}) \cdot t_i$.
Now if this agent resale $d$ units to a slower agent, say agent $i' < i$, then his utility must be smaller than
$p_{i-1}(v) + (l(a_i)-l(a_{i-1})) \cdot t_i - (l(a_i) - d)  \cdot t_i - d \cdot t_{i'} \le p_{i-1}(v) - l(a_{i-1}) \cdot t_i$, since agent $i$ will need to cover the costs of agents $i'$. 
 

To prevent reselling of the remaining case, the $(1+\epsilon)$-mechanism can preform the  following shifting procedure:
For every slower machine $i$ and a faster machine $j$ if there is a task assigned to $i$ in $a$, such that 
reassigning the task to $j$ will {\it not} increase the makespan, then do: 
First, reassign the task to machine $j$. Second, sort the loads on each machine such that faster machines 
get higher load. Repeat until no
such task exists. Now, if a resale was done, the mechanism designer can easily detected this: every resale must cause a delay in the makespan. 

Each shifting step can be done in poly-time.  
Let $L^i_j$ be the total load assigned to the $j$'th machine in the $i$'th step. 
To show that the procedure will finish in finite amount of time, observe that in each step $i$ the 
tuple $(L^i_1, L^i_2,\ldots, L^i_m)$ strictly improves, lexicographically (both right  after the reassignment 
and right after the sorting).
In the worst case, the smallest possible improvement can be made with shifting one unit of load.  
This gives the quasi-polynomial bound of $l_1 + l_2 + \cdots + l_k$. 
\qed 
}
 
\begin{proposition} 
Any envy-free $(1+\epsilon)$-mechanism supported by the frugal payment is not truthful. 
\end{proposition}

\comment{
\proof
Consider two machines with $t_1=3, t_2=2$, and a single task with $l_1=1$. 
Any envy-free mechanism must assign this task to the fastest machine, that is machine 2. 
The frugal payment for the second machine will be 2. 
However, if agent 2 would pretend to be slower declaring $t'_2 = 3-\epsilon$, he would still be assigned 
the task,  getting the payment of  $3-\epsilon > 2$. 
\qed 
}

  


\subsubsection*{Acknowledgments.} 
I would like to thank anonymous referees, Liad Blumrosen, Federico Echenique, David Kempe, John Ledyard,
Debasis Mishra, Mohamed Mostagir, Mahyar Salek and Michael Schapira for helpful discussions. 



\begin{thebibliography}{4}

\bibitem{AMS}
Lior Amar, Ahuva Mu'alem, and Jochen Stoesser.
\newblock On the importance of migration for fairness in online grid markets.
\newblock In {\em GRID}, 2008.

\bibitem{AT}
Aaron Archer and Eva Tardos.
\newblock Truthful mechanisms for one-parameter agents.
\newblock In {\em FOCS}, pages 482--491, 2001.

\bibitem{balcan}
N.~Balcan, A.~Blum, and Y.~Mansour.
\newblock Item pricing for revenue maximization.
\newblock In {\em EC}, 2008.

\bibitem{BN}
Liad Blumrosen and Noam Nisan.
\newblock On the computational power of iterative auctions $\mathrm{I}$: Demand
  queries.
\newblock In {\em EC}, 2005.

\bibitem{swamy-envy}
Maurice Cheung and Chaitanya Swamy.
\newblock Approximation algorithms for single-minded envy-free
  profit-maximization problems with limited supply.
\newblock In {\em FOCS}, 2008.

\bibitem{kouts-2-player-scheduling-char}
George Christodoulou, Elias Koutsoupias, and Angelina Vidali.
\newblock A characterization of 2-player mechanisms for scheduling.
\newblock In {\em ESA}, 2008.

\bibitem{rfpas}
P. Dhangwatnotai, S. Dobzinski, S. Dughmi, and T. Roughgarden.
\newblock Truthful approximation schemes for single-parameter agents.
\newblock In {\em FOCS}, 2008.

\bibitem{Foley}
D.~Foley.
\newblock Resource allocation and the public sector.
\newblock {\em Yale Economics Essays}, 7:45--98, 1967.

\bibitem{envy-free-np-hard}
A. Grigoriev, J. van Loon, R. Sitters, and M. Uetz.
\newblock How to sell a graph: Guidelines for graph retailers.
\newblock In {\em Lecture Notes in Computer Science 4271}, 2006.

\bibitem{Jason-envy}
Venkatesan Guruswami, Jason~D. Hartline, Anna~R. Karlin, David Kempe, Claire
  Kenyon, and Frank McSherry.
\newblock On profit-maximizing envy-free pricing.
\newblock In {\em SODA}, pages 1164--1173, 2005.

\bibitem{ef-simple-procedure}
Claus-Jochen Haake, Matthias~G. Raith, and Francis~Edward Su.
\newblock Bidding for envy-freeness: A procedural approach to n-player
  fair-division problems.
\newblock {\em Social Choice and Welfare}, 19(4):723--749, 2002.

\bibitem{Jason-ef-sched}
Jason Hartline, Sam Ieong, Michael Schapira, and Aviv Zohar.
\newblock Private communication.
\newblock 2008.

\bibitem{MV}
B.~Heydenreich, R.~Mller, M.J. Uetz, and R.~Vohra.
\newblock Characterization of revenue equivalence.
\newblock {\em Econometrica}, 77(1):307--316, 2009.

\bibitem{ptas-HS}
Dorit~S. Hochbaum and David~B. Shmoys.
\newblock A polynomial approximation scheme for scheduling on uniform
  processors: Using the dual approximation approach.
\newblock {\em SIAM J. Comput.}, 17(3):539--551, 1988.

\bibitem{Elias261}
Elias Koutsoupias and Angelina Vidali.
\newblock A lower bound of 1+phi for truthful scheduling mechanisms.
\newblock {\em MFCS}, pages 454--464, 2007.

\bibitem{LST87}
Jan~Karel Lenstra, David~B. Shmoys, and Eva Tardos:.
\newblock Approximation algorithms for scheduling unrelated parallel machines.
\newblock In {\em FOCS}, 1987.

\bibitem{Lipton}
Richard~J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi.
\newblock On approximately fair allocations of indivisible goods.
\newblock In {\em EC}, 2004.

\bibitem{debasis}
Debasis Mishra and Dolf Talman.
\newblock Characterization of walrasian equilibria of the assignment model,
  working paper, 2007.

\bibitem{NR}
Noam Nisan and Amir Ronen.
\newblock Algorithmic mechanism design.
\newblock {\em Games and Economic Behavior}, 35:166--196, 2001.

\bibitem{AGT-book}
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V.~Vazirani (eds.).
\newblock {\em Algorithmic Game Theory}.
\newblock Cambridge University Press, expected 2007.

\bibitem{NS}
N. Nisan and I. Segal.
\newblock The communication requirements of efficient allocations and
  supporting prices.
\newblock {\em Journal of Economic Theory}, 129(1):192--224, July 2006.

\bibitem{papa-steiglitz-book}
Christos~H. Papadimitriou and Kenneth Steiglitz.
\newblock {\em Combinatorial Optimization: Algorithms and Complexity}.
\newblock {Dover Publications}, 1998.

\bibitem{quinzii}
M.~Quinzii.
\newblock Core and competitive equilibria with indivisibilities.
\newblock {\em International Journal of Game Theory}, 13(1):41--60, March 1984.

\bibitem{rochet}
J.C. Rochet.
\newblock A necessary and sufficient condition for rationalizability in a
  quasi-linear context.
\newblock {\em Journal of Mathematical Economics}, 16:191--200, 1987.

\end{thebibliography}




\end{document}
