Ti-6Al-4V is a material of high interest in various industrial sectors including biomedical, automotive and aerospace. Conventional means of machining encounter different types of difficulties. Electric discharge machining (EDM) is not a contest of hardness. Circular impressions of micro-depth are produced in Ti-6Al-4V using four different electrode materials including aluminum, brass, graphite and copper, each assigned positive and negative polarity. In order to get precise control over the geometry of micro-impressions dimensional accuracy and tool wear must be controlled. Thus, EDM performance has been evaluated in terms of axial dimensional error (D.E_Axi), radial dimensional error (D.E_Rad), tool length reduction (TLR), and surface roughness (SR). Since the EDM process is stochastic in nature therefore in addition to tool polarity only two factors are considered as variables, i.e. discharge current and pulse-time-ratio (ration of on-time to off-time). The behaviors of each of the four electrode materials are compared together under each of the two polarities and two variables for each of the four response characteristics. The search is carried out to select the most appropriate tool electrode polarity (common for all responses) and a single common electrode capable of minimizing all the four response measures simultaneously. Moreover, microstructures of the machined impressions are discussed. Without any compromise in the minimum values of response measures, no single polarity and a single electrode are found common. However, with a slight compromise over the machining measures negative tool polarity and copper electrode served the purpose of set objectives (minimum of D.E, TLR, and SR). The expanse of compromise is found to be ≤ 50 µm in axial and radial dimensional errors, 0.8 µm in surface roughness and no compromise in tool length reduction if the copper electrode is assigned with negative polarity.