\documentclass[11pt,twoside]{article}\makeatletter

\IfFileExists{xcolor.sty}%
  {\RequirePackage{xcolor}}%
  {\RequirePackage{color}}
\usepackage{colortbl}
\usepackage{wrapfig}
\usepackage{ifxetex}
\ifxetex
  \usepackage{fontspec}
  \usepackage{xunicode}
  \catcode`⃥=\active \def⃥{\textbackslash}
  \catcode`❴=\active \def❴{\{}
  \catcode`❵=\active \def❵{\}}
  \def\textJapanese{\fontspec{Noto Sans CJK JP}}
  \def\textChinese{\fontspec{Noto Sans CJK SC}}
  \def\textKorean{\fontspec{Noto Sans CJK KR}}
  \setmonofont{DejaVu Sans Mono}
  
\else
  \IfFileExists{utf8x.def}%
   {\usepackage[utf8x]{inputenc}
      \PrerenderUnicode{–}
    }%
   {\usepackage[utf8]{inputenc}}
  \usepackage[english]{babel}
  \usepackage[T1]{fontenc}
  \usepackage{float}
  \usepackage[]{ucs}
  \uc@dclc{8421}{default}{\textbackslash }
  \uc@dclc{10100}{default}{\{}
  \uc@dclc{10101}{default}{\}}
  \uc@dclc{8491}{default}{\AA{}}
  \uc@dclc{8239}{default}{\,}
  \uc@dclc{20154}{default}{ }
  \uc@dclc{10148}{default}{>}
  \def\textschwa{\rotatebox{-90}{e}}
  \def\textJapanese{}
  \def\textChinese{}
  \IfFileExists{tipa.sty}{\usepackage{tipa}}{}
\fi
\def\exampleFont{\ttfamily\small}
\DeclareTextSymbol{\textpi}{OML}{25}
\usepackage{relsize}
\RequirePackage{array}
\def\@testpach{\@chclass
 \ifnum \@lastchclass=6 \@ne \@chnum \@ne \else
  \ifnum \@lastchclass=7 5 \else
   \ifnum \@lastchclass=8 \tw@ \else
    \ifnum \@lastchclass=9 \thr@@
   \else \z@
   \ifnum \@lastchclass = 10 \else
   \edef\@nextchar{\expandafter\string\@nextchar}%
   \@chnum
   \if \@nextchar c\z@ \else
    \if \@nextchar l\@ne \else
     \if \@nextchar r\tw@ \else
   \z@ \@chclass
   \if\@nextchar |\@ne \else
    \if \@nextchar !6 \else
     \if \@nextchar @7 \else
      \if \@nextchar (8 \else
       \if \@nextchar )9 \else
  10
  \@chnum
  \if \@nextchar m\thr@@\else
   \if \@nextchar p4 \else
    \if \@nextchar b5 \else
   \z@ \@chclass \z@ \@preamerr \z@ \fi \fi \fi \fi
   \fi \fi  \fi  \fi  \fi  \fi  \fi \fi \fi \fi \fi \fi}
\gdef\arraybackslash{\let\\=\@arraycr}
\def\@textsubscript#1{{\m@th\ensuremath{_{\mbox{\fontsize\sf@size\z@#1}}}}}
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\def\abbr{}
\def\corr{}
\def\expan{}
\def\gap{}
\def\orig{}
\def\reg{}
\def\ref{}
\def\sic{}
\def\persName{}\def\name{}
\def\placeName{}
\def\orgName{}
\def\textcal#1{{\fontspec{Lucida Calligraphy}#1}}
\def\textgothic#1{{\fontspec{Lucida Blackletter}#1}}
\def\textlarge#1{{\large #1}}
\def\textoverbar#1{\ensuremath{\overline{#1}}}
\def\textquoted#1{‘#1’}
\def\textsmall#1{{\small #1}}
\def\textsubscript#1{\@textsubscript{\selectfont#1}}
\def\textxi{\ensuremath{\xi}}
\def\titlem{\itshape}
\newenvironment{biblfree}{}{\ifvmode\par\fi }
\newenvironment{bibl}{}{}
\newenvironment{byline}{\vskip6pt\itshape\fontsize{16pt}{18pt}\selectfont}{\par }
\newenvironment{citbibl}{}{\ifvmode\par\fi }
\newenvironment{docAuthor}{\ifvmode\vskip4pt\fontsize{16pt}{18pt}\selectfont\fi\itshape}{\ifvmode\par\fi }
\newenvironment{docDate}{}{\ifvmode\par\fi }
\newenvironment{docImprint}{\vskip 6pt}{\ifvmode\par\fi }
\newenvironment{docTitle}{\vskip6pt\bfseries\fontsize{22pt}{25pt}\selectfont}{\par }
\newenvironment{msHead}{\vskip 6pt}{\par}
\newenvironment{msItem}{\vskip 6pt}{\par}
\newenvironment{rubric}{}{}
\newenvironment{titlePart}{}{\par }

\newcolumntype{L}[1]{){\raggedright\arraybackslash}p{#1}}
\newcolumntype{C}[1]{){\centering\arraybackslash}p{#1}}
\newcolumntype{R}[1]{){\raggedleft\arraybackslash}p{#1}}
\newcolumntype{P}[1]{){\arraybackslash}p{#1}}
\newcolumntype{B}[1]{){\arraybackslash}b{#1}}
\newcolumntype{M}[1]{){\arraybackslash}m{#1}}
\definecolor{label}{gray}{0.75}
\def\unusedattribute#1{\sout{\textcolor{label}{#1}}}
\DeclareRobustCommand*{\xref}{\hyper@normalise\xref@}
\def\xref@#1#2{\hyper@linkurl{#2}{#1}}
\begingroup
\catcode`\_=\active
\gdef_#1{\ensuremath{\sb{\mathrm{#1}}}}
\endgroup
\mathcode`\_=\string"8000
\catcode`\_=12\relax

\usepackage[a4paper,twoside,lmargin=1in,rmargin=1in,tmargin=1in,bmargin=1in,marginparwidth=0.75in]{geometry}
\usepackage{framed}

\definecolor{shadecolor}{gray}{0.95}
\usepackage{longtable}
\usepackage[normalem]{ulem}
\usepackage{fancyvrb}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{marginnote}

\renewcommand{\@cite}[1]{#1}


\renewcommand*{\marginfont}{\itshape\footnotesize}

\def\Gin@extensions{.pdf,.png,.jpg,.mps,.tif}

  \pagestyle{fancy}

\usepackage[pdftitle={Iterative Combinatorial Auction for Two-Sided Grid Markets: Multiple users and Multiple Providers},
 pdfauthor={}]{hyperref}
\hyperbaseurl{}

	 \paperwidth210mm
	 \paperheight297mm
              
\def\@pnumwidth{1.55em}
\def\@tocrmarg {2.55em}
\def\@dotsep{4.5}
\setcounter{tocdepth}{3}
\clubpenalty=8000
\emergencystretch 3em
\hbadness=4000
\hyphenpenalty=400
\pretolerance=750
\tolerance=2000
\vbadness=4000
\widowpenalty=10000

\renewcommand\section{\@startsection {section}{1}{\z@}%
     {-1.75ex \@plus -0.5ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
     {-1.75ex\@plus -0.5ex \@minus- .2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
     {-1.5ex\@plus -0.35ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\large}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
     {-1ex \@plus-0.35ex \@minus -0.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\normalsize}}
\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
     {1.5ex \@plus1ex \@minus .2ex}%
     {-1em}%
     {\reset@font\normalsize\bfseries}}


\def\l@section#1#2{\addpenalty{\@secpenalty} \addvspace{1.0em plus 1pt}
 \@tempdima 1.5em \begingroup
 \parindent \z@ \rightskip \@pnumwidth 
 \parfillskip -\@pnumwidth 
 \bfseries \leavevmode #1\hfil \hbox to\@pnumwidth{\hss #2}\par
 \endgroup}
\def\l@subsection{\@dottedtocline{2}{1.5em}{2.3em}}
\def\l@subsubsection{\@dottedtocline{3}{3.8em}{3.2em}}
\def\l@paragraph{\@dottedtocline{4}{7.0em}{4.1em}}
\def\l@subparagraph{\@dottedtocline{5}{10em}{5em}}
\@ifundefined{c@section}{\newcounter{section}}{}
\@ifundefined{c@chapter}{\newcounter{chapter}}{}
\newif\if@mainmatter 
\@mainmattertrue
\def\chaptername{Chapter}
\def\frontmatter{%
  \pagenumbering{roman}
  \def\thechapter{\@roman\c@chapter}
  \def\theHchapter{\roman{chapter}}
  \def\thesection{\@roman\c@section}
  \def\theHsection{\roman{section}}
  \def\@chapapp{}%
}
\def\mainmatter{%
  \cleardoublepage
  \def\thechapter{\@arabic\c@chapter}
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \pagenumbering{arabic}
  \setcounter{secnumdepth}{6}
  \def\@chapapp{\chaptername}%
  \def\theHchapter{\arabic{chapter}}
  \def\thesection{\@arabic\c@section}
  \def\theHsection{\arabic{section}}
}
\def\backmatter{%
  \cleardoublepage
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \setcounter{secnumdepth}{2}
  \def\@chapapp{\appendixname}%
  \def\thechapter{\@Alph\c@chapter}
  \def\theHchapter{\Alph{chapter}}
  \appendix
}
\newenvironment{bibitemlist}[1]{%
   \list{\@biblabel{\@arabic\c@enumiv}}%
       {\settowidth\labelwidth{\@biblabel{#1}}%
        \leftmargin\labelwidth
        \advance\leftmargin\labelsep
        \@openbib@code
        \usecounter{enumiv}%
        \let\p@enumiv\@empty
        \renewcommand\theenumiv{\@arabic\c@enumiv}%
	}%
  \sloppy
  \clubpenalty4000
  \@clubpenalty \clubpenalty
  \widowpenalty4000%
  \sfcode`\.\@m}%
  {\def\@noitemerr
    {\@latex@warning{Empty `bibitemlist' environment}}%
    \endlist}

\def\tableofcontents{\section*{\contentsname}\@starttoc{toc}}
\parskip0pt
\parindent1em
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\newenvironment{reflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemsep}{0pt}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\itshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{sansreflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\itemsep}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\upshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{specHead}[2]%
 {\vspace{20pt}\hrule\vspace{10pt}%
  \phantomsection\label{#1}\markright{#2}%

  \pdfbookmark[2]{#2}{#1}%
  \hspace{-0.75in}{\bfseries\fontsize{16pt}{18pt}\selectfont#2}%
  }{}
      \def\TheFullDate{2018 2018-01-15 (revised: 48 Year 2018 15 January 2018)}
\def\TheID{\makeatother }
\def\TheDate{2018 2018-01-15}
\title{Iterative Combinatorial Auction for Two-Sided Grid Markets: Multiple users and Multiple Providers}
\author{}\makeatletter 
\makeatletter
\newcommand*{\cleartoleftpage}{%
  \clearpage
    \if@twoside
    \ifodd\c@page
      \hbox{}\newpage
      \if@twocolumn
        \hbox{}\newpage
      \fi
    \fi
  \fi
}
\makeatother
\makeatletter
\thispagestyle{empty}
\markright{\@title}\markboth{\@title}{\@author}
\renewcommand\small{\@setfontsize\small{9pt}{11pt}\abovedisplayskip 8.5\p@ plus3\p@ minus4\p@
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus2\p@
\belowdisplayshortskip 4\p@ plus2\p@ minus2\p@
\def\@listi{\leftmargin\leftmargini
               \topsep 2\p@ plus1\p@ minus1\p@
               \parsep 2\p@ plus\p@ minus\p@
               \itemsep 1pt}
}
\makeatother
\fvset{frame=single,numberblanklines=false,xleftmargin=5mm,xrightmargin=5mm}
\fancyhf{} 
\setlength{\headheight}{14pt}
\fancyhead[LE]{\bfseries\leftmark} 
\fancyhead[RO]{\bfseries\rightmark} 
\fancyfoot[RO]{}
\fancyfoot[CO]{\thepage}
\fancyfoot[LO]{\TheID}
\fancyfoot[LE]{}
\fancyfoot[CE]{\thepage}
\fancyfoot[RE]{\TheID}
\hypersetup{citebordercolor=0.75 0.75 0.75,linkbordercolor=0.75 0.75 0.75,urlbordercolor=0.75 0.75 0.75,bookmarksnumbered=true}
\fancypagestyle{plain}{\fancyhead{}\renewcommand{\headrulewidth}{0pt}}

\date{}
\usepackage{authblk}

\providecommand{\keywords}[1]
{
\footnotesize
  \textbf{\textit{Index terms---}} #1
}

\usepackage{graphicx,xcolor}
\definecolor{GJBlue}{HTML}{273B81}
\definecolor{GJLightBlue}{HTML}{0A9DD9}
\definecolor{GJMediumGrey}{HTML}{6D6E70}
\definecolor{GJLightGrey}{HTML}{929497} 

\renewenvironment{abstract}{%
   \setlength{\parindent}{0pt}\raggedright
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
   \textcolor{GJBlue}{\large\bfseries\abstractname\space}
}{%   
   \vskip8pt
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
}

\usepackage[absolute,overlay]{textpos}

\makeatother 
      \usepackage{lineno}
      \linenumbers
      
\begin{document}

             \author[1]{Aminul  Haque}

             \affil[1]{  Daffodil International University}

\renewcommand\Authands{ and }

\date{\small \em Received: 15 December 2017 Accepted: 3 January 2018 Published: 15 January 2018}

\maketitle


\begin{abstract}
        


Heterogeneity and different ownerships of grid computing resources impose complexity in evaluating the market value of these resources. Auction protocols are proposed to meet this challenge efficiently. Auction models are also suitable for achieving better payoff and resource allocation for grid providers. Grid users and providers are usually geographically distributed. The number of users in grid computing could also be very high. Hence, models provide seamless support to multiple users and providers would be useful to promote grid computing. In this paper, we implement a novel First Price Open Cry auction (ascending-bid auction) that supports for multiple users and providers simultaneously. We explain about (i) bundle generation (resource packages by providers), (ii) creating corresponding agents to bundles, (iii) allowing users to choose their suitable bundles, and (iv) clearing bundles through solving winner determination problem. The simulation results predict when and how to map providers? private values on resource bundles, such that maximum revenue and better utilization of idle resources.  K

\end{abstract}


\keywords{grid computing; economic models; auction; bid; profit; tight budget.}

\begin{textblock*}{18cm}(1cm,1cm) % {block width} (coords) 
\textcolor{GJBlue}{\LARGE Global Journals \LaTeX\ JournalKaleidoscope\texttrademark}
\end{textblock*}

\begin{textblock*}{18cm}(1.4cm,1.5cm) % {block width} (coords) 
\textcolor{GJBlue}{\footnotesize \\ Artificial Intelligence formulated this projection for compatibility purposes from the original article published at Global Journals. However, this technology is currently in beta. \emph{Therefore, kindly ignore odd layouts, missed formulae, text, tables, or figures.}}
\end{textblock*}


\let\tabcellsep& 	 	 		 
\section[{Introduction}]{Introduction}\par
rid computing is a buzzword in computational science, which was initiated in the mid-1990s \hyperref[b0]{[1]}. The grid computing tends to aggregate distributed resources (storage, memory, and CPU) over the Internet and to provide stronger computational power for computationally complex applications such as protein analysis, weather forecasting, and image processing.\par
However, multidimensionality (e.g., architecture, operational state, and ownership) of grid resources impose a challenge on seamless collaboration. Different economic models (e.g., commodity market, bargaining, and auction) are proposed to overcome the barrier of resource coordination across multiple administrations \hyperref[b1]{[2]}. Among the models, auction protocols are different regarding their price setting and resource allocation policies. Additionally, auction mechanisms are suitable to evaluate the market value and maximize economic efficiency, which ultimately motivates resource providers to contribute their resources on the grid.\par
In a distributed self-interested agent environment (such as the grid), auction theory analyzes different protocols and agents' behavior in auctions. An auction consists of an auctioneer (provider-side) and potential bidders (user-side). In an auction setting, the auctioneer tries to maximize his/her revenue through selling an item to the bidder, who values it the highest, while the bidders try to acquire the item at the lowest possible price. Depending on how a bidder values a particular item, there are three different auction settings; (i) private value auction states that there is a private value for the auctioned item, which means, the value of the particular item by a bidder does not depend on how others value the item. Each bidder has its preferences on the auction, (ii) common value auction describes that a bidder's value of an item depends entirely on other agents' values of it, (iii) correlated value auction is the blend of the two, that is, the value of an item by a bidder partly depends on its preferences and partly on others' values. However, regarding grid computing, it is hard to comment on which setting would fit all grid scenarios, since in some cases, bidders have their individual preferences on resources and in some other cases, multiple bidders may impose a value on a particular resource.\par
In this paper, we focus on provider-side and employ a private value auction by assuming that bidders have their value on resources. Based on this setting, different auction protocols (Dutch, First-price-sealedbid, Vickrey, and English) can be viewed differently in a grid perspective. Dutch auction model could not achieve much popularity in the grid environment, since it continuously lowers resource price until one of the bidders takes the resource. Hence, the auction does not provide sufficient incentives to providers. In the Firstprice-sealed-bid auction model, each bidder submits one bid without knowing the others' bids. The highest bidder wins the item and pays the amount of his/her bid. From a provider's point of view, the auction may be suitable under a private value auction setting, since it is a single shot auction and bidders do not have a chance to counter bid. However, an auctioneer cannot guarantee that all bidders will value the auctioned item. Hence there is a chance that the providers may not maximize the revenue. The similar case happens to Vickrey auction, in which, the highest bidder wins the item and pays the amount of the second highest bidder. The average revenue for providers may not be G maximized in this model as well. The best policy for a provider would be First price open cry ascending-bid auction (English auction) model under private value auction setting. In such auction, each bidder is free to raise his/her bid and exceed others over iterations. When no bidder is willing to rise any more, the auction ends, and the highest bidder wins the item at the price of his/her bid. Considering English auction model under such a setting would be economically efficient since it increases the chance of extracting competitive bids from the bidders through iterative bidding and finally awarding it to the highest bidder.\par
Due to the high interdependency of grid resources, the single-item auction may not be suitable for grid applications. Parkes and Ungar first propose combinatorial auctions, where bidders are allowed to bid directly for bundles of resources \hyperref[b2]{[3]}. Parkes appreciates the importance of bundles to the distributed resource allocation problem. However, bundle generation in grid environment requires taking into consideration resource state (availability), heterogeneity and control over the resources at a particular time and location. In this paper, we explain how bundles are generated based on providers' availability. After completion of bundle generation, bundle agents are created, which are delegated to offer their respective bundles. Each auctioneer corresponding to a particular bundle then invites bid from its suitable bidders. At each round, the ask price by an auctioneer is the highest bid of the previous round. When no bidder would like to increase their bids anymore, auction ends. The auctioneer then awards the bid to the highest bidder as long as the bid meets auctioneer's private value for the bundle. The presence of the private value for a particular bundle by an auctioneer is important since it prevents the auctioneer to release the bundle with a lower price. We develop a two-sided grid market, where multiple bidders can choose their suitable bundles from any of the multiple providers and providers to offer their bundles via bundle-correspondents. Two-sided grid market helps us to comprehend the real picture of a large-scale distributed grid. We conduct the experiments under two cases; firstly, it considers the bidders with Relaxed Budgets and secondly, bidders with Tight Budgets. We find that, under certain reservation prices on bundles imposed by the auctioneers, achieved revenue and utilization are better in the relaxed case than the latter. This outcome inspires us to map auctioneers' private values with bundles to ensure better payoff and utilization by the providers.\par
We organize the remainder of the paper as follows: Section 2 presents related work conducted on different auction protocols. In Section 3, we describe our system architecture in details. Section 4 explains the implementation of our model and Section 5 shows experimental results. Finally, in Section 6, we conclude and propose some future research directions. 
\section[{II.}]{II.} 
\section[{Related Work}]{Related Work}\par
Liu and Zhao propose an iterative combinatorial auction to facilitate resource allocation problem in grid environment \hyperref[b3]{[4]}. They study preliminaries of iterative combinatorial auction mainly on different pricing functions such as ask prices by an auctioneer and priceupdate methods by bidders. They compare their results by varying the number of resources and the number of single-unit auctions. However, they do not consider auctioneers' reservation prices for bundles which may lead to less revenue for providers, since some bidders may not be intending to increase their bids and hence, a particular bidder could get that bundle at a lower price. In such a scenario, evaluation of true market value for a particular bundle becomes impossible. These bidders typically work for a particular group or organization. Hence, from an auctioneer's point of view, it would be better to have some private values on bundles. Also, how grid resources are bundled for an auction through engaging suitable bidders is not clear.\par
GEMSS (Grid Infrastructure for Medical Service Provision) has been proposed to support the provision of medical simulation services for clients such as hospitals \hyperref[b4]{[5]}. In \hyperref[b4]{[5]}, they develop a reverse English auction model to harness suitable reservations available for clients. Reverse English auction is a type of set up, in which, the role of bidders and providers are reversed, with the primary objective to drive purchase price downward. However, the approach is likely to be suitable for client-side but not for increasing providers' profits. In this paper, we focus on the provider-side and propose an ascending-bid auction to maximize revenue for providers.\par
Attanasio et al. \hyperref[b5]{[6]} investigate the co-relation between auction mechanism and Lagrangian-based scheduling mechanism. They show that their proposed Lagrangean-based auction heuristic outperforms traditionally centralized heuristics. Though, they have proposed several methods for updating resource prices, however which particular one they have applied to their experiments is not clear. Apart from this, some auction entities such as auction setting (methodology to update a bidder's bid), winner determination problem and evaluating the market value of resources are not taken into consideration. Without such criteria, the market mechanism might lose its desired objective of successful resource provisioning.\par
A protocol for evaluating the economic efficiency and how it impacts on system performance has been studied by Das and Grosu \hyperref[b6]{[7]}. They analyze the creation of possible bundles by providers, allocation of computing resources to the winners and perform simulations regarding budget and resource utilization. They propose Generalized Vickrey auction where bidders submitted their bids only once and assumed to reveal their value on bundles. However, providers 46 Year 2018 cannot guarantee the expression of value from all bidders, since some bidders could participate in the auction only to extract the information of how other bidders value the bundle. Hence, from providers' point of view, the chance of evaluating market value on bundles decreases. Nevertheless, the expected revenue by the providers might not be achieved by using such a single shot auction. A similar approach using Secondprice Sealed-bid auction (i.e., highest bidder wins the auction at the price of the second highest bidder) is proposed by Young et al. \hyperref[b7]{[8]}. They employ a greedy approximation algorithm for efficient allocation among winners to reduce the amount of time needed to compute a set of winners. However, their particular auction setting does not consider iterative bidding, which reduces the chance of identifying the true market value. We develop an iterative combinatorial auction which assists in manipulating the value of resource bundles and hence in maximizing economic efficiency.\par
By realizing the complexity of successful bundle formation in situations, where multidimensionality (distributed resource bundling) of the resources occurs, Peter proposes multiple single-item auctions across administrations rather than a combinatorial auction \hyperref[b8]{[9]}. However, single-item auctions on grid applications may not be suitable due to the interdependency of grid resources. In other words, as long as the bundle formation through multiple single-item auctions is not completed, the application cannot start execution. Hence, from a bidder's point of view, he/she starts auctioning with the uncertainty of completion his/her resource bundle. Also, how a bidder breaks down his/her budget to precede single-item auctions is not clear. Such an approach of using multiple single-item auctions would produce communication overhead and might create network congestion. In our work, bundles are formed based on providers' availability. Bidders can choose and bid for their suitable bundles.  
\section[{System Model}]{System Model}\par
We propose the agent-based framework shown in Figure \hyperref[fig_0]{1}. This framework supports auctions happening with multiple providers concurrently in a distributed environment. We model our framework with three types of agents, which are bidder-agent, provideragent and auctioneer-agent or bundle-correspondent (BC). The model can be viewed as a game, where each of the players (agents) tries to optimize its objective. In a provider's point of view, his/her agent tries for optimal allocation through maximizing revenue. A bundlecorrespondent aims to clear its bundle by selecting the highest bidder among its competitors, whereas a bidder-agent's strategy is to acquire its suitable bundle through budget optimization. However, in this paper, we focus on provider strategy and employ an ascendingbid auction to support providers' benefit. 
\section[{a) Bundle Generation}]{a) Bundle Generation}\par
A bundle by a grid provider typically consists of several distinct resources (e.g., storage, CPU, and operating system). Bundles, in such an environment, can be generated in two ways. One is decentralized, in which bundles are formed across multiple organizations. Another is centralized, which refers to bundle generation within the same organization. However, decentralized bundle generation becomes challenging, when multidimensionality of resources occurs. In this paper, we consider centralized bundle formation for simplicity. According to our model, bundle(s) by a particular provider are formed dynamically based on the provider's availability. Similarly, multiple providers generate their respective bundles and invite potential bidders to compete for them through BCs.\par
Let ? i denote the set of bundles which are offered by a particular provider P i (i = 1, ?, n). Let J ? \{1, ?, j\} be the set of j bidders. Bidders are free to choose their suitable bundles from any of the providers (S ji ? ? i ), where S ji denotes the bundle belonging to i th provider found to be suitable by the j th bidder. Each bidder bids, which consists of a pair (S, B), where B refers to the budget by the bidder for the bundle S, which he/she is willing to pay for and B ? ? + . In our model, each B can further be split into minimum budget B min and maximum budget B max so that minimal bid increment (? > 0) by the competitors can be applied during the iterative auction. Also, each bidder possesses a finite value, v j (S i ), for any subset S and we may normalize, v j (?) = 0. Bidders are assumed to have a quasi-linear utility function u j (S) = v j (S) -B(S) for bundle S at a price B. Once the bundle generation is finished, BCs is created based on available bundles, ? i dynamically. 
\section[{b) Engage Bundle Competitors}]{b) Engage Bundle Competitors}\par
Bundle correspondents are the most significant part in our model, since they (i) invite suitable bidders, (ii) proceed auctions by initiating an ask-bid (typically a value below the market price), (iii) propose a new askbid in each iteration and (iv) finally release the bundle by selecting an appropriate winner (the highest bidder). The number of BCs by a provider i is equal to the length of ? i which means, each BC handles only one bundle. Let the number of possible bundles by a particular provide; i is M ? \{1, ?, m\} which is a function of resource availability by the provider. Hence, BC im refers to the BC of m th bundle belonging to the provider, i. One bundle is usually chosen by multiple bidders, if the bidders' requirements match with the bundle items. However, in our system, an auction for a particular bundle S i is proceeded if |j| ? 2 for the bundle, otherwise auction dismisses with an auction cancelation message to the bidder. If cancellation occurs, the BC waits for other bidders (typically the failed bidders, since we allow them to re-negotiate with BCs corresponding to other bundles) to proceed with the competition. In an ascending-bid auction, the utility for a BC increases, if the number of competitors for that bundle is high. Moreover, the number of competitors for an auction depends on the total number of bundles by a provider as well as the number of providers in a market.\par
The winner determination problem in an auction protocol that describes the selection of an appropriate bidder while ensuring maximum revenue. In an ascending-bid set up, when no bidders would like to rise their bids any more, the auction terminates, and the auctioneer (BC) awards the highest bidder with the price of his/her bid. It is BC's responsibility to ensure that the appropriate bundle and no more than one bundle are allocated to the winner. The respective bundle is then removed from ? i , and the BC is terminated. 
\section[{c) Private Value}]{c) Private Value}\par
Once available bundles by the BCs are published and invited for auction; bidders select their suitable bundles to compete. Bidders are assumed to have exclusive-or bids for bundles, which means, one bidder can only choose either bundle S 1 or bundle S 2 , but not both. The primary strategy of bidders in an ascending-bid auction under private value setting is to minimally increase (?) their bids in each iteration over the ask-bid so that they can compete for a maximum time. Hence, the minimal-increment method can be used as a price-update-method for bidders. Each bidder starts off his/her competition by initiating a minimum bid B min (above the current ask-bid) and continues to increase the bid until it reaches B max or receives notification from the BC about the completion of winner determination. If a bidder reaches his/her B max without any notification from BC, he/she is removed from the potential-bidder-list for the bundle. The provider side, each provider has his/her private value or reservation price for each resource bundle. If the private value for a particular bundle is not met, it is not provisioned, which ensures the auction delivered with a sufficient price. However, if the number of competitors for a particular bundle is less or competitors are with Tight Budget, the reservation price for the auction is not likely to be achieved. 
\section[{IV.}]{IV.} 
\section[{Implementation}]{Implementation}\par
A simulation environment is established, and the proposed model is implemented using a crossplatform multi-agent programmable modeling environment known as NetLogo \hyperref[b9]{[10]}, \hyperref[b10]{[11]}. We choose NetLogo because,\par
? NetLogo is a FIPA (Foundation for Intelligent Physical Agent) conformant platform \hyperref[b11]{[12]}. ? It has extensive built-in models to deal with multiagents. ? It can work as a 'simulated parallel' environment \hyperref[b9]{[10]}. ? It is platform (Mac, Windows, and Linux) independent \hyperref[b10]{[11]}.\par
users are engaged to compete for these bundles. We implement a FIPA (Foundation for Intelligent Physical Agents) conformant English auction protocol  {\ref [13]}. In this protocol, the auctioneer (BC) seeks to find the market price of a bundle by initially announcing an ask-bid below the supposed market value, and gradually raising the ask-bid over iterations. If any bidder accepts the bid and declares a counter-bid which is greater than the ask-bid, auctioneer immediately announces the counterbid as a new ask-bid. The auction continues until no bidder is prepared to counter-bid against the ask-bid. If the last bid by the bidder exceeds the auctioneer's reservation price, the bundle is sold. Otherwise it is not sold. The reservation price C of a bundle B by a particular provider P i can be formalized by Equation (1).\par
Figure  {\ref 2}: A NetLogo screenshot depicts the offering of bundles by a provider and competitor engagement on available bundles memory), which means most grid applications require same resources. Hence, in our simulation, we consider two types of resources (storage and CPU) for each bundle and bidders' requirements are also assumed to be the two types of the resources. Figure  {\ref 2} illustrates how available bundles by a provider are expressed and bidders choose their suitable bundles for competition. According to the figure, provider 5 has six bundles available to offer, whereas the first element of a bundle refers to storage and the second element to the number of processors. Bidder (user) 18 chooses bundle-1 out of the 6, since bundle-1 matches or exceeds the bidder's requirement. However, the auction for the bundle does not happen, since only one bidder selects the bundle.\par
The BCs corresponding to bundle-3 and bundle-5 would be allowed to proceed with their auctions, since multiple Where, r refers to a particular resource element in the bundle. Typically, this can be storage, CPU, or memory. q is the total number of elements in the bundle, Req r refers to the resource amount of type r in the bundle U r is the unit price (e.g., price/GB for storage) of resource type r. This function is for a provider, i\par
We develop an algorithm supporting auctions to be conducted with multiple bundles. Algorithm 1 explains the details.\par
Figure 3 presents a screenshot illustrating the multiple auctions for multiple bundles. This also includes the history for multiple providers. The variation of reservation price (provider demand) indicates that there are different reservation prices for different bundles. If a reservation price for a bundle is under the bidders' bids, the bundle is provisioned. If it is above the bidders' bids, the bundle is not provisioned. When there are no potential providers, our two-sided market is terminated. A provider is taken out from the potential-provider-list dynamically, if the provider does not receive sufficient bidders to compete for at least one bundle.  
\section[{V. Experimentation}]{V. Experimentation}\par
Table \hyperref[tab_1]{1} presents the resource configuration we use to conduct our experiments. Column 1 of Table \hyperref[tab_1]{1} represents different parameters that a bidder and a provider use to set their respective agents. In our simulation environment, one can accommodate a large number of bidders as well as providers. In this paper, we examine 5000 bidders and 200 providers. To set this large number of bidders and providers with different requests and offers respectively, we use ranges of values, so that each participant can select a value from its respective range. All bidders' requests are set using the Column 2 ranges, and all providers' offers are set using the Column 3 ranges automatically. Resource bundles are then generated based on the providers' offers. We conduct our experiments in two scenariosbidders with Relaxed Budgets and bidders with Tight Budgets. Then we investigate the system performance in both cases. Typically, the reservation price for a Iterative Combinatorial Auction for Two-Sided Grid Markets: Multiple users and Multiple Providers bundle is manipulated using the maximum demand range \hyperref[b5]{[6]}\hyperref[b6]{[7]}\hyperref[b7]{[8]}\hyperref[b8]{[9]}\hyperref[b9]{[10]} (U storage for equation-1), which refers to the price for 1 GB storage and [20-30] (U CPU for equation 1)\par
refers to the price for the processor of 1 MIPS (Million Instructions Per Second) capacity. For simplicity, we consider all the processors identical. We use maximum demand for the reservation price so that maximum revenue can be achieved. However, we find that using maximum demand as reservation price may work well for the scenario when bidders come with Relaxed Budgets but not when bidders come with Tight Budgets.\par
Experiment-1 and 2 explain in details. Also, we assume concurrent arrival of different requests and offers.\par
(1) Where l denotes the number of the bundle that is sold, t denotes the total number of sold bundles, and Z l defines the highest bid by a bidder for the sold bundle. The solid trend in Figure 4 illustrates the revenue (\$160×10 5 ) in combination with all providers in the market. The X-axis shows the total number of auctions that are successful in the market. This number is high (3037) for relaxed budget due to certain reasons. Firstly, the number of providers and the number of bundles are high, since under a single provider there could be a lot of bundles to offer. Secondly, it also depends on the number of bidders. There are 5000 bidders in our system. Due to this large quantity, the competition for a particular bundle increases and thus the possibility of the bundle being sold also increases. Thirdly, because of Relaxed Budgets by the bidders, the chance of meeting a bundle's reservation price is increased. The trends are straight, since we only consider successful auctions to calculate the revenue, and each successful auction brings some revenue, which is added immediately to the total revenue. Regarding the scenario with Tight Budget, the number of successful auctions is significantly low. Hence, the total revenue achieved, in this case, is remarkably lower than that for the Relaxed Budget. Due to Tight Budget, at most times, bidders could not reach the expected reservation prices imposed by the respective providers. This scenario yields fewer successful auctions on bundles.\par
The second evaluation criteria, resource utilization, R for a resource of type, r by a particular provider, i can be formalized using the following equation, For resource utilization, we obtain similar patterns for both disk-space and processors. Hence, we explain the utilization for processors only in Figure 5. The figure demonstrates utilization pattern for 200 providers (along X-axis). Figure 5 describes the computational analysis of the two scenarios. Providers in the Relaxed Budget scenario can utilize their resources massively, whereas, in the Tight Budget scenario, resource utilization by the providers is significantly lower. \par
(3) We can explain this difference using the same explanation we used regarding revenue. Due to Tight Budgets of the bidders, providers are most often unable to sell their bundles. On the other hand, for the same reservation prices, providers perform better with Relaxed Budget. Now, a question arises, what is the need for reservation price during the Tight Budget? As mentioned earlier in Section 3.3, the significance of reservation price in an agent-oriented environment is that, bidders cannot win a bundle without much competition. One could often receive such a scenario when participant engagement to auctions is free of cost, and some participants are intended to participate only to retrieve the market value of a bundle through lying the auctioneer (counter-speculation). Hence, a need arises to map reservation prices for a particular scenario (Tight Budget) dynamically so that maximum revenue and better utilization can be achieved. However, there is one question about how to recognize whether the bidders are coming with Relaxed Budgets or Tight Budgets. To answer this question, we define a parameter, Q that is used to obtain runtime auction success rate by a particular provider, i. We define Q as,?? ?? = ?????????? ???????????? ???? ???????? ?????????????? ?????????? ???????????? ???? ?????????????? ??????????????\par
The value of Q ranges from 0 to 1. An agent (BC) is now able to sense whether the bidders are coming with Relaxed Budgets or Tight Budgets based on Q and map the reservation price accordingly. To map the reservation price, a BC can dynamically switch between the provider's minimum demand and the maximum demand (Table \hyperref[tab_1]{1}). If the value of Q tends to lower, BCs change the reservation prices to lower, so that the value of Q can be high again.\par
However, in order to define that at which value of Q, a BC needs to lower the reservation price, we define another parameter called threshold success rate, Q th of Q. We experiment with different threshold values (ranging from 0 to 1) under Tight Budget condition and find that, Q th = 1 yield better results than other values.\par
Experiment 2 -Bidders with Tight Budgets (Traditional versus Optimized): We repeat the experiment under Tight Budget, where reservation prices are changed based on the success factor, Q dynamically during the runtime. We compare the results with the same results obtained for Tight Budget without considering Q. Figure 6 shows the comparison of revenue. Because of sensing success rate and mapping reservation prices accordingly, even under the same scenario (Tight Budget), our strategy performs better (\$129.52×10 5 ) than the traditional one (\$44.74×10 5 ). The number of successful auctions increases from 1173 to 3846. Figure 7 presents the comparison of utilization of the two cases. Due to high success rate, the mechanism even at the Tight Budget condition utilizes more resources than the former Tight Budget condition. The average utilization is improved by 56\%.   
\section[{VI. Conclusions}]{VI. Conclusions}\par
The evolution of distributed collaboration is hindered due to insufficient incentives to providers to contribute their resources on the grid. Hence, economic models are proposed to successfully collaborate resources. English auction is well known due to its strengths of evaluating market price and maximizing revenue. In this paper, we developed an English auction interaction protocol supporting multiple users and providers to exhibit the performance pattern of a large scale distributed grid environment. Resources are bundled to facilitate auction process. We explained details regarding bundle generation, participant engagement, bundle correspondence generation, auction process and finally provision of bundle allocation through solving winner determination problem. We analyzed our two-sided grid markets under two different scenarios -Relaxed Budget and Tight Budget. To overcome the exhibited variation in performance, we defined a new parameter to manipulate runtime success rate. Our proposed methodology provides competitive performance even under the Tight Budget scenario regarding revenue and utilization.\par
In future, we would like to vary resource supply and demand to analyze the system performance further and investigate suitable values for threshold success rate. The bundle generation presented in this paper is currently centralized. Future work would investigate the suitability of our work in a decentralized environment.\begin{figure}[htbp]
\noindent\textbf{1}\includegraphics[]{image-2.png}
\caption{\label{fig_0}Figure 1 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-3.png}
\caption{\label{fig_1}}\end{figure}
         \begin{figure}[htbp]
\noindent\textbf{1} \par 
\begin{longtable}{P{0.589406099518459\textwidth}P{0.10778491171749599\textwidth}P{0.03138041733547352\textwidth}P{0.12142857142857141\textwidth}}
User/provider-level parameter\tabcellsep \multicolumn{2}{l}{User-level-range}\tabcellsep Provider-level-range\\
Number of participants\tabcellsep 5000\tabcellsep \tabcellsep 200\\
Storage/disk-space (GB)\tabcellsep \multicolumn{2}{l}{400-600}\tabcellsep 6000-10000\\
Number of\tabcellsep \tabcellsep \tabcellsep \\
CPUs (MIPS\tabcellsep \multicolumn{2}{l}{20-30}\tabcellsep 500-700\\
per CPU)\tabcellsep \tabcellsep \tabcellsep \\
Minimum Budget/deman d (\$)\tabcellsep Relaxe d 800-1500\tabcellsep Tight 500-1000\tabcellsep 1-5 (/GB), 12-16 (/MIPS)\\
Maximum Budget/deman d(\$)\tabcellsep 4000-6000\tabcellsep 2500-4000\tabcellsep 6-10 (/GB), 20-30 (/MIPS)\\
\multicolumn{4}{l}{Experiment 1 -Bidders with Relaxed and Tight Budgets:}\\
\multicolumn{4}{l}{In our first experiment, we consider the bidders with}\\
\multicolumn{4}{l}{relaxed and Tight Budgets separately. Results are}\\
\multicolumn{4}{l}{evaluated and compared regarding revenue and}\\
\multicolumn{4}{l}{resource utilization. Revenue, E earned by a particular}\\
\multicolumn{2}{l}{provider, i is given by,}\tabcellsep \tabcellsep \\
\tabcellsep ??\tabcellsep \tabcellsep \\
\tabcellsep \multicolumn{2}{l}{?? ?? = ? ?? ??}\tabcellsep \\
\tabcellsep ??=1\tabcellsep \tabcellsep \end{longtable} \par
 
\caption{\label{tab_1}Table 1 :}\end{figure}
 		 		\backmatter  			 			 			  				\begin{bibitemlist}{1}
\bibitem[Liu and Zhao ()]{b3}\label{b3} 	 		‘A Method Based on Iterative Combinatorial Auction Mechanism for Resource Allocation in Grid Multi-agent Systems’.  		 			X Liu 		,  		 			L Zhao 		.  	 	 		\textit{International Conference on Intelligent Human-Machine Systems and Cybernetics},  				2009.  	 	 (IHMSC '09) 
\bibitem[Damaceanu ()]{b10}\label{b10} 	 		‘An agent-based computational study of wealth distribution in function of resource growth interval using NetLogo’.  		 			R.-C Damaceanu 		.  		 10.1016/j. amc.2007.12.042.  	 	 		\textit{Applied Mathematics and Computation}  		2008. 2008. 201  (1-2)  p. .  	 
\bibitem[Attanasio et al. ()]{b5}\label{b5} 	 		‘Auction algorithms for decentralized parallel machine scheduling’.  		 			A Attanasio 		,  		 			G Ghiani 		,  		 			L Grandinetti 		,  		 			F Guerriero 		.  		 \xref{http://dx.doi.org/10.1016/j.parco.2006.03.002}{10.1016/j.parco.2006.03.002}.  	 	 		\textit{Parallel Computing}  		2006. 2006. 32  (9)  p. .  	 
\bibitem[Anubhav and Grosu ()]{b6}\label{b6} 	 		‘Combinatorial auction-based protocols for resource allocation in grids’.  		 			D Anubhav 		,  		 			D Grosu 		.  	 	 		\textit{19th IEEE International Symposium on Parallel and Distributed Processing},  				2005. 2005.  	 
\bibitem[Peter ()]{b8}\label{b8} 	 		‘Distributed combinatorial resource scheduling’.  		 			G Peter 		.  	 	 		\textit{Proceedings of the 1st International Workshop on Smart Grid Technologies (SGT-2005)},  				 (the 1st International Workshop on Smart Grid Technologies (SGT-2005))  		2005.  	 
\bibitem[Buyya ()]{b1}\label{b1} 	 		\textit{Economic-based distributed resource management and scheduling for Grid computing},  		 			R Buyya 		.  		2002. 2002. Monash University; Melbourne.  	 	 (Ph.D thesis.) 
\bibitem[Michael et al. ()]{b11}\label{b11} 	 		‘Experiences creating three implementations of the repast agent modeling toolkit’.  		 			J N Michael 		,  		 			T C Nicholson 		,  		 			Jerry 		,  		 			R V Doi = \{hyperlink 		.  		 \xref{http://dx.doi.org/10.1145/1122012.1122013"}13.2000}{10.1145/1122012.1122013"\}13.2000}.  		 \url{http://www.fipa.org/specs/fipa00031/54Year2018}  	 	 		\textit{FIPA English Auction Interaction Protocol Specification. Foundation for Intelligent Physical Agents}  		2006. 2006. 16  (1)  p. .  	 	 (ACM Trans. Model. Comput. Simul.) 
\bibitem[David and Lyle ()]{b2}\label{b2} 	 		\textit{Iterative combinatorial auctions: theory and practice},  		 			C P David 		,  		 			H U Lyle 		.  		2000. 2000.  	 
\bibitem[Middleton et al. ()]{b4}\label{b4} 	 		\textit{Quality of Service Negotiation},  		 			S E Middleton 		,  		 			M Surridge 		,  		 			S Benkner 		,  		 			G Engelbrecht 		.  		2007.  	 
\bibitem[Alvin ()]{b7}\label{b7} 	 		‘Resource Allocation in Federated Distributed Computing Infrastructures’.  		 			A Alvin 		.  	 	 		\textit{Proceedings of the 1st Workshop on Operating System and Architectural Support for the Ondemand IT Infrastructure},  				 (the 1st Workshop on Operating System and Architectural Support for the Ondemand IT Infrastructure)  		2004. 2004.  	 
\bibitem[Sallez et al. ()]{b9}\label{b9} 	 		‘Simulating intelligent routing in flexible manufacturing systems using NetLogo’.  		 			Y Sallez 		,  		 			T Berger 		,  		 			C Tahon 		.  	 	 		\textit{IEEE International Conference on Industrial Technology},  				2004. 2004.  	 
\bibitem[Roure et al. (ed.) ()]{b0}\label{b0} 	 		\textit{The Evolution of the Grid, in Grid computing: making the global infrastructure a reality F},  		 			D D Roure 		,  		 			M A Baker 		,  		 			N R Jennings 		.  		 \xref{http://dx.doi.org/10.1002/0470867167.ch3"}}{10.1002/0470867167.ch3"\}}.  		 \url{http://dx.doi.org/10.1002/0470867167.ch3"\}}  		Berman, G. Fox, and T. Hey (ed.)  		2003. 2003. John Wiley \& Sons Ltd. p. .  	 
\end{bibitemlist}
 			 		 	 
\end{document}
