A method in a root agent for network-aware decentralized service placement, wherein the root agent executes at an electronic device and acts as a parent to a plurality of intermediate agents in a hierarchy of agents, wherein each of the plurality of intermediate agents acts as a parent to one or more descendant agents (108A-108C) associated with one or more electronic devices (110H-110J) having resources (114A-114C) available for service placement, the method comprising: transmitting a service request description to each of the plurality of intermediate agents, wherein the service request description specifics the requirements for a plurality of components of an application; receiving, at the root agent, a plurality of sets of solution encodings (180A-180N) corresponding to the plurality of intermediate agents from the plurality of intermediate agents, wherein each of the plurality of sets of solution encodings indicates possible placements of some or all of the plurality of components of application that the one or more electronic devices (110H-110J) associated with the one or more descendant agents of the intermediate agent can locally provide while satisfying requirements of the some or all of the components; generating, by the root agent based upon the plurality of sets of solution encodings, one or more cover sets indicating feasible placement solutions that can successfully satisfy the requirements of all of the components of the application; partitioning, by the root agent for each of the one or more cover sets, the components of the application into a plurality of assignment sets corresponding to the plurality of intermediate agents while adhering to the feasible placement solutions of the cover set to indicate placements of the plurality of components that minimize network traffic travelling between electronic devices associated with the plurality of intermediate agents that would result from the placements, to yield one or more candidate placement solutions, wherein the partitioning includes generating, by the root agent, an application graph including a plurality of vertices corresponding to the plurality of components of the application and a plurality of edges connecting pairs of the plurality of vertices, wherein each of the plurality of edges is associated with a data transfer amount expected to be transmitted between the pair of components connected by the edge; and transmitting, by the root agent to a first intermediate agent of the plurality of intermediate agents, a service placement solution indicating one or more of plurality components that are to be placed by the first intermediate agent according to a selected one of the one or more candidate placement solutions. transmitting a service request description to each of the plurality of intermediate agents, wherein the service request description specifics the requirements for a plurality of components of an application; receiving, at the root agent, a plurality of sets of solution encodings (180A-180N) corresponding to the plurality of intermediate agents from the plurality of intermediate agents, wherein each of the plurality of sets of solution encodings indicates possible placements of some or all of the plurality of components of application that the one or more electronic devices (110H-110J) associated with the one or more descendant agents of the intermediate agent can locally provide while satisfying requirements of the some or all of the components; generating, by the root agent based upon the plurality of sets of solution encodings, one or more cover sets indicating feasible placement solutions that can successfully satisfy the requirements of all of the components of the application; partitioning, by the root agent for each of the one or more cover sets, the components of the application into a plurality of assignment sets corresponding to the plurality of intermediate agents while adhering to the feasible placement solutions of the cover set to indicate placements of the plurality of components that minimize network traffic travelling between electronic devices associated with the plurality of intermediate agents that would result from the placements, to yield one or more candidate placement solutions, wherein the partitioning includes generating, by the root agent, an application graph including a plurality of vertices corresponding to the plurality of components of the application and a plurality of edges connecting pairs of the plurality of vertices, wherein each of the plurality of edges is associated with a data transfer amount expected to be transmitted between the pair of components connected by the edge; and transmitting, by the root agent to a first intermediate agent of the plurality of intermediate agents, a service placement solution indicating one or more of plurality components that are to be placed by the first intermediate agent according to a selected one of the one or more candidate placement solutions.